P4396 [AHOI2013]作业

思路

因为每次a和b不相同
用莫队+分块或者莫队+树状数组即可维护
不过分块单点修改是O(1)的，更优
我用树状数组维护了一下，只能开O2通过

代码

#include 
#include 
#include 
#include 
using namespace std;
struct BIT{
    int tr[10000000],MAXW;
    int lowbit(int x){
        return x&(-x);
    }
    void add(int pos,int c){
        pos++;
        while(pos<=MAXW){
            tr[pos]+=c;
            pos+=lowbit(pos);
        }
    }
    int query(int pos){
        pos++;
        int ans=0;
        while(pos){
            ans+=tr[pos];
            pos-=lowbit(pos);
        }
        return ans;
    }
}times,nums;
int color[10000000],a[100100],n,m,L,R,sz,num,belong[100100],ans1[100100],ans2[100100];
struct Query{
    int l,r,a,b,id;
    bool operator < (const Query &b) const{
        return (belong[l]==belong[b.l])?rQ[i].l)
            moveL(-1);
        while(RQ[i].r)
            moveR(-1);
        ans1[Q[i].id]=times.query(Q[i].b)-times.query(Q[i].a-1);
        ans2[Q[i].id]=nums.query(Q[i].b)-nums.query(Q[i].a-1);
    }
    for(int i=1;i<=m;i++)
        printf("%d %d\n",ans1[i],ans2[i]);
    return 0;
}