解题思路

　　刚开始想到了莫队+\(bitset\)去维护信息，结果发现空间不太够。。试了各种奇技淫巧都\(MLE\)，最后\(\%\)了发题解发现似乎可以分段做。。这道题做法具体来说就是开\(3\)个\(bitset\)，然后对原序列离散化之后给每个值规定一个开始的位置，之后就可以莫队搞，计算答案是用总的元素个数减去扔掉的，而扔掉的其实就是三个\(bitset\)做与运算后\(1\)的个数，时间复杂度\(O(n\sqrt n+\frac{n^2}{w})\)。\(bzoj\)上时限\(80s\)跑了\(80s\)，荣获倒一。

代码

#include
    
     using namespace std;const int N=100005;const int M=10000;inline int rd(){    int x=0,f=1; char ch=getchar();    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();    return f?x:-x;}int n,m,a[N],cpy[N],pos[N],u,b[N],siz,num,slen[N];int ll[N][4],rr[N][4];struct Data{    int l,r,id,type;    friend bool operator<(const Data A,const Data B){        if(A.l/siz!=B.l/siz) return A.l
     
      B.r;        return A.r
      
        f[3][10010],g;#define Add(x) g.set(pos[a[(x)]]++)#define Del(x) g.reset(--pos[a[(x)]])void solve(int l,int r){    int tot=0;    for(int i=1;i<=n;i++)        if(b[i]!=b[i-1]) pos[b[i]]=i;    for(int i=l;i<=r;i++){        q[++tot]=Data(ll[i][0],rr[i][0],i-l+1,0);        q[++tot]=Data(ll[i][1],rr[i][1],i-l+1,1);        q[++tot]=Data(ll[i][2],rr[i][2],i-l+1,2);    }    sort(q+1,q+1+tot);    int L=1,R=0; g.reset();    for(int i=1;i<=tot;i++){        while(L>q[i].l) L--,Add(L);        while(R
       
        q[i].r) Del(R),R--;        f[q[i].type][q[i].id]=g;    }       for(int i=1;i<=r-l+1;i++){        printf("%d\n",(slen[i+l-1]-3*((f[0][i]&f[1][i]&f[2][i]).count())));         f[0][i].reset(); f[1][i].reset(); f[2][i].reset();    }}int main(){    n=rd(),m=rd(); int l1,r1,l2,r2,l3,r3;    for(int i=1;i<=n;i++) a[i]=cpy[i]=rd();    sort(cpy+1,cpy+1+n); siz=sqrt(n);     u=unique(cpy+1,cpy+1+n)-cpy-1;    for(int i=1;i<=n;i++)        a[i]=lower_bound(cpy+1,cpy+1+u,a[i])-cpy;    memcpy(b,a,sizeof(b)); sort(b+1,b+1+n);    for(int i=1;i<=m;i++){        l1=rd(),r1=rd(),l2=rd(),r2=rd(),l3=rd(),r3=rd();        ll[i][0]=l1,ll[i][1]=l2,ll[i][2]=l3;        rr[i][0]=r1,rr[i][1]=r2,rr[i][2]=r3;        slen[i]=r1-l1+1+r2-l2+1+r3-l3+1;    }    for(int i=1;i<=m;i+=M)        solve(i,min(m,i+M-1));    return 0;}