P4867 Gty的二逼妹子序列

思路

和作业那题类似，但是询问有1e6次，也就是说移动次数更多
用所以上莫队+分块更稳，因为分块的单点修改是O(1)的
然后注意
分块计算属于哪个块的时候要这样
belong[i]=(i-1)/sz+1
不能
belong[i]=i/sz+1
后面这种每块右端点的数据是错的

代码

#include 
#include 
#include 
#include 
using namespace std;
struct Blocks{
    int block_sum[100100],belong[100100],num[100100],sz,numx;
    void init(int n){
        sz=sqrt(n);
        numx=n/sz;
        if(n%sz)
            numx++;
        for(int i=1;i<=n;i++)
            belong[i]=(i-1)/sz+1;
    }
    void add(int pos,int c){
        num[pos]+=c;
        block_sum[belong[pos]]+=c;
    }
    int query(int l,int r){
        int ans=0;
        int xl=belong[l],xr=belong[r];
        for(int i=l;i<=min(r,xl*sz);i++)
            ans+=num[i];
        if(xl!=xr)
            for(int i=(xr-1)*sz+1;i<=r;i++)
                ans+=num[i];
        for(int i=xl+1;i<=xr-1;i++)
            ans+=block_sum[i];
        return ans;
    }
}nums;
int n,m,a[100100],belong[100100],ans[1000100],sz,num,L,R,barrel[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(LQ[i].r)
            moveR(-1);
        ans[Q[i].id]=nums.query(Q[i].a,Q[i].b);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}