记录编号	360027	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[東方] 博丽灵梦 梦想妙珠	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	0.984 s
提交时间	2016-12-26 15:50:46	内存使用	10.61 MiB

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;
const int MAXN = 100002;
const int MAXQ = 100002;
const int MAXM = MAXN+(MAXQ<<1);
const int MAXC = 200001;

struct Query {
    int aid, idx, val, w; // aid == -1表示修改
    bool operator<( const Query &rhs ) const {
        return idx == rhs.idx ? aid < rhs.aid : idx < rhs.idx;
    }
}query[MAXM];
int qidx = 0;
void addq( int aid, int idx, int val, int w ) {
    query[qidx++] = (Query){aid,idx,val,w};
}

int ans[MAXQ], aidx = 0;

Query tmp[MAXM]; int cnt[MAXC];
void cdq( int L, int R ) {
    if( R-L <= 1 ) return;
    int M = (L+R)>>1; cdq(L,M); cdq(M,R);
    int p = L, q = M, o = L;
    while( p < M && q < R ) {
        if( query[p] < query[q] ) {
            if( query[p].aid == -1 ) cnt[query[p].val]++;
            tmp[o++] = query[p++];
        } else {
            if( query[q].aid != -1 ) ans[query[q].aid] += query[q].w * cnt[query[q].val];
            tmp[o++] = query[q++];
        }
    }
    while( p < M ) tmp[o++] = query[p++];
    while( q < R ) {
        if( query[p].aid != -1 ) ans[query[q].aid] += query[q].w * cnt[query[q].val];
        tmp[o++] = query[q++];
    }
    for( int i = L; i < R; ++i ) {
        cnt[tmp[i].val] = 0;
        query[i] = tmp[i];
    }
}

int n,q;
int main() {
    freopen( "mengxiangmiaozhu.in", "r", stdin );
    freopen( "mengxiangmiaozhu.out", "w", stdout );
    scanf( "%d", &n );
    for( int i = 1; i <= n; ++i ) {
        int num; scanf( "%d", &num );
        addq( -1, i, num, 0 );
    }
    scanf( "%d", &q );
    for( int i = 0; i < q; ++i ) {
        int l,r,c; scanf( "%d%d%d", &l, &r, &c );
        addq( aidx, l-1, c, -1 );
        addq( aidx++, r, c, 1 );
    }
    cdq(0,qidx);
    for( int i = 0; i < aidx; ++i ) printf( "%d\n", ans[i] );
    return 0;
}