一道比较简单的莫队……
用bitset维护三个区间的交元素。
#include<bits/stdc++.h> const int N=150010; const int wy=33334; #define UI unsigned int #define rep(i,_x,_y) for (register int i=(_x);i<=(_y);i++) #define rdp(i,_x,_y) for (register int i=(_x);i>=(_y);i--) #define debug(x) cerr<<#x<<" = "<<x<<endl; #define sqr(x) (x)*(x) using namespace std; int n,m,len,qaq,size,l1[N],r1[N],l2[N],r2[N],l3[N],r3[N],cal[(1<<16)+10],A[N],b[N]; int block[N],pos[N],head[N],h[N]; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } struct Data{ int x;int v; bool operator <(const Data &f)const{return x<f.x;} }a[N]; struct bs{ UI S[3125]; inline void update(int x){S[x>>5]^=(1U<<(x&31));} inline int count(){int tot=0; rep(i,0,3124) tot+=cal[S[i]>>16]+cal[S[i]&65535]; return tot; } void clear(){memset(S,0,sizeof(S));} }now,c[34000]; inline bs operator ^ (bs &x,bs &y){ bs z;rep(i,0,3124) z.S[i]=x.S[i]^y.S[i]; return z; } inline bs operator & (bs &x,bs &y){ bs z;rep(i,0,3124) z.S[i]=x.S[i]&y.S[i]; return z; } struct Node{ int l,r,id; Node(int l=0,int r=0,int id=0):l(l),r(r),id(id){} bool operator<(const Node &tmp)const{return block[l]==block[tmp.l]?(block[l]&1)?r>tmp.r:r<tmp.r:l<tmp.l;} }q[N]; inline void add(int x){h[x]++;now.update(head[x]+h[x]-2);} inline void del(int x){now.update(head[x]+h[x]-2);h[x]--;} inline void solve(){ now.clear();memset(h,0,sizeof(h));memset(c,255,sizeof(c)); int l=1,r=0; sort(q+1,q+len+1); for(int i=1;i<=len;i++){ int lx=q[i].l,rx=q[i].r,id=q[i].id; while(lx<l)add(A[--l]); while(lx>l)del(A[l++]); while(rx<r)del(A[r--]); while(rx>r)add(A[++r]); c[id]=c[id]&now; } } int main(){ //freopen("xp1.in","r",stdin); //freopen("xwd.out","w",stdout); n=read();m=read();size=(int)sqrt(n+.5); rep(i,0,(1<<16)-1) cal[i]=cal[i>>1]+(i&1); for(int i=1;i<=n;i++)block[i]=(i-1)/size+1; for(int i=1;i<=n;i++)a[i].x=read(),a[i].v=i; sort(a+1,a+n+1); for(int i=1;i<=n;i++)A[a[i].v]=a[i].x==a[i-1].x?A[a[i-1].v]:++qaq; for(int i=1;i<=n;i++)b[i]=A[i]; sort(b+1,b+n+1); for(int i=1;i<=n;i++)if(b[i]!=b[i-1])head[b[i]]=i; for(int i=1;i<=m;i++){ l1[i]=read();r1[i]=read();l2[i]=read();r2[i]=read();l3[i]=read();r3[i]=read(); pos[i]=r1[i]+r2[i]+r3[i]-l1[i]-l2[i]-l3[i]+3; } for(int i=1;i<=m;i+=wy){ len=0; for(int j=i;j<=i+wy-1;j++){ if(j>m)break; q[++len]=Node{l1[j],r1[j],j-i+1}; q[++len]=Node{l2[j],r2[j],j-i+1}; q[++len]=Node{l3[j],r3[j],j-i+1}; } solve(); for(int j=i;j<=i+wy-1;j++){ if(j>m)break; printf("%d ",pos[j]-3*c[j-i+1].count()); } } }