题解

执行用时：122ms
内存消耗：17.38MB
击败了100.00%的用户
击败了100.00%的用户

#include <unistd.h>
#include <algorithm>
using namespace std;

static char inBuf[1 << 16];
static int inLen = 0, inPos = 0;

inline int readChar() {
if (inPos == inLen) {
inLen = read(0, inBuf, sizeof(inBuf));
inPos = 0;
if (inLen <= 0) return -1;
}
return inBuf[inPos++];
}

inline int readInt() {
int c = readChar();
while (c <= ' ') { if (c == -1) return 0; c = readChar(); }
int x = 0;
while (c > ' ') { x = (x << 3) + (x << 1) + (c - '0'); c = readChar(); }
return x;
}

static char outBuf[1 << 16];
static int outLen = 0;

inline void flushOut() {
if (outLen > 0) { write(1, outBuf, outLen); outLen = 0; }
}

inline void outChar(char c) {
if (outLen == (int)sizeof(outBuf)) flushOut();
outBuf[outLen++] = c;
}

inline void outInt(int v) {
if (v == 0) { outChar('0'); return; }
char tmp[12]; int tl = 0;
while (v) { tmp[tl++] = '0' + v % 10; v /= 10; }
while (tl) outChar(tmp[--tl]);
}

static int a[2000005];
static int tree[2000005];
static int ans[2000005];

struct Question {
int l;
int x;
int id;
int val;
} q[4000005];

inline int lowbit(int x) {
return x & -x;
}

inline void update(int x) {
while (x <= 2000000) {
tree[x]++;
x += lowbit(x);
}
}

inline int query(int x) {
int sum = 0;
while (x > 0) {
sum += tree[x];
x -= lowbit(x);
}
return sum;
}

bool cmp(const Question &a, const Question &b) {
return a.l < b.l;
}

int main() {
int n = readInt();
int m = readInt();
for (int i = 1; i <= n; i++) a[i] = readInt();

int cnt = 0;
for (int i = 1; i <= m; i++) {
    int l = readInt();
    int r = readInt();
    int x = readInt();
    q[++cnt].l = l - 1; q[cnt].x = x; q[cnt].id = i; q[cnt].val = -1;
    q[++cnt].l = r;     q[cnt].x = x; q[cnt].id = i; q[cnt].val = 1;
}

sort(q + 1, q + cnt + 1, cmp);

int j = 1;
for (int i = 1; i <= cnt; i++) {
    while (j <= q[i].l) {
        update(a[j]);
        j++;
    }
    ans[q[i].id] += q[i].val * query(q[i].x);
}

for (int i = 1; i <= m; i++) {
    outInt(ans[i]);
    outChar('\n');
}
flushOut();
return 0;

}