莫队

回滚莫队

++L一定要独立出来

inline void Q(){
    k=pow(n,0.66);
    for(int i=1;i<=max(n,m);++i)  block[i]=(i-1)/k+1;
    for(int i=1;i<=q;++i)  qwe[i]={read(),read(),read(),read(),i,0};
    sort(qwe+1,qwe+q+1,cmp);
    int L=1,R=0,las=0,_l;
    for(int i=1;i<=q;++i){
        if(block[qwe[i].l]==block[qwe[i].r]){
            for(int j=qwe[i].l;j<=qwe[i].r;++j){
                sum1[a[j]]+=b[j];
                if(a[j]>=qwe[i].vl&&a[j]<=qwe[i].vr)
                    qwe[i].A=max(qwe[i].A,sum1[a[j]]);
            }for(int j=qwe[i].l;j<=qwe[i].r;++j)  sum1[a[j]]-=b[j];
            continue;
        }if(block[qwe[i].l]!=las){
            int rr=min(block[qwe[i].l]*k,n);
            while(R>rr)  c[block[a[R]]]=d[block[a[R]]]=0,sum[a[R]]-=b[R],--R;
            while(L<rr+1)  c[block[a[L]]]=d[block[a[L]]]=0,sum[a[L]]-=b[L];++L;
            las=block[qwe[i].l];
        }while(R<qwe[i].r)  ++R,add(R,c);_l=L;
        while(_l>qwe[i].l)  --_l,add(_l,d);
        qwe[i].A=ask(qwe[i].vl,qwe[i].vr);
        while(_l<L)  d[block[a[_l]]]=c[block[a[_l]]],sum[a[_l]]-=b[_l],++_l;
    }sort(qwe+1,qwe+q+1,CMP);
    for(int i=1;i<=q;++i)  printf("%lld\n",qwe[i].A);
}