[Ynoi2003] 铃原露露（分块解决区间二维偏序）

· · 题解

到底学 OI 不到两年，想了半天才得到了一种 O((n+q)\sqrt{n\log_2n}) 的做法。

将序列分块，块长为 \sqrt{n\log_2n}。

将值域分块，块数为 \sqrt{n\log_2n}

对于修改操作 [l,r]，所有的 x\in[l,r]，区间 [l,x] 会对 x 产生贡献，差分一下变成 [1,x]-[1,l-1]。

对于 [1,x]，只需要在修改时记录 x\in[l,r] 的次数，区间加即可。

对于 [1,l-1]，要在序列上分类讨论：

  1. 在散块上，直接初始化时对序列做可持久化 \sqrt{n\log_2n} 修改，O(1) 查询的值域分块，
  2. 在整块上，不同值域块的贡献，可以将所有值域块外产生的贡献对这些序列块差分，注意每一个值域块都要差分，这样修改是 \sqrt{n\log_2n}，由于查询时只有一个值域块，所以查询是 O(\sqrt{\frac{n}{\log_2n}})。
  3. 在整块上，同值域块的贡献，发现查询时与 a_x 同值域块的的数字只有 \sqrt{\frac{n}{\log_2n}} 个，对于每一个数字，我们希望能得到它对 x 所在的序列块的贡献次数，这样，可以每一个序列块维护一个树状数组，修改时区间加，查询时单点查，都是 \sqrt{n\log_2n} 的。

其实代码很好写，甚至不需要调试：

#include<bits/stdc++.h>
using namespace std;
const int N=202719,K=202,B=1026;
using ll=long long;
namespace fast_io{
    char bf[N+5],ob[N+38];
    int it,ed,f,c,ot,t,stk[38],x;
#define gc (it==ed&&(ed=(it=0)+fread(bf,1,N,stdin),it==ed)?EOF:bf[it++])
    inline int read(){
        for(c=gc;c<48;c=gc);
        for(x=0;c>47;x=x*10+(48^c),c=gc);
        return x;
    }inline void fls(){
        fwrite(ob,1,ot,stdout),ot=0;
    }inline void write(ll x){
        if(x<0)ob[ot++]='-',x=-x;
        for(t=0;x>9;stk[++t]=48^(x%10),x/=10);
        for(ob[ot++]=48^x;t;ob[ot++]=stk[t--]);
        ob[ot++]='\n';if(ot>N)fls();
    }
}using fast_io::read;
using fast_io::write;
int n,q,p,a[N];
int ct[B][N],b[N],da[N];
unsigned short k1[B][N];
ll nw[N],cf[K][K],ans;
struct ku_sq_1{
    int hv[K],ad[K];
    inline void add(int x){
        int i,d=x>>10;++hv[d];
        for(i=d+1;i<=p;++i)++ad[i];
        for(i=d<<10;i>>10==d;++i)
            k1[hv[d]][i]=k1[hv[d]-1][i]+(i>=x);
    }inline int qry(int x){
        return k1[hv[x>>10]][x]+ad[x>>10];
    }
}ka[N];
int main(){
    n=read(),q=read(),p=n>>10;
    int i,op,l,r,j,l_,kl,kr;
    for(i=1;i<=n;++i){
        b[a[i]=read()]=i;
        ka[i]=ka[i-1],ka[i].add(a[i]);
        da[i]=ka[i].qry(a[i]);
    }
    while(q--){
        op=read(),l=read(),kl=l>>10;
        if(op==1){
            r=read();l_=l-1;kr=r>>10;
            for(i=r;i;i-=i&-i)++ct[p+2][i];
            for(i=l-1;i;i-=i&-i)--ct[p+2][i];
            if(kl==kr){
                for(i=l;i<=r;++i)
                    nw[i]-=ka[l_].qry(a[i]);
            }else{
                for(i=l;i>>10==kl;++i)   
                    nw[i]-=ka[l_].qry(a[i]);
                for(i=kr<<10;i<=r;++i)
                    nw[i]-=ka[l_].qry(a[i]);
                if(kl+1<=kr-1){
                    for(i=1;i<=p;++i){
                        cf[kl+1][i]-=ka[l_].ad[i];
                        cf[kr][i]+=ka[l_].ad[i];
                    }for(i=kl+1;i<kr;++i)
                        for(j=l_;j;j-=j&-j)--ct[i][j];
                }
            }
        }else{
            for(i=l,ans=0;i<=n;i+=i&-i)ans+=ct[p+2][i];
            ans*=da[l],r=a[l]>>10,ans+=nw[l];
            for(i=1;i<=kl;++i)ans+=cf[i][r];
            for(i=r<<10;i<=a[l];++i)
                if(i)
                    for(j=b[i];j<=n;j+=j&-j)
                        ans+=ct[kl][j];
            write(ans);
        }
    }fast_io::fls();return 0;
}