将权值排序，设权值x排序后在[l,r]出现，x在区间中出现k次，则用[l,l+k-1]为1，[l+k,r]为0来表示x的出现次数
用bitset表示可重集中每个元素的出现次数，用莫队处理出询问区间对应的bitset，通过取and后求1的个数得到答案
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> typedef unsigned int u32; typedef u32 bits[3155]; const int N1=34007,N=N1*3; int _(){ int x=0,c=getchar(); while(c<48)c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x; } int n,m,v[N],vs[N]; struct Q{ int l,r,id; }qs[N]; int pos[N],ps[N]; bool operator<(Q a,Q b){ if(pos[a.l]!=pos[b.l])return pos[a.l]<pos[b.l]; if(a.r!=b.r)return (a.r<b.r)^(pos[a.l]&1); return 0; } int qp=0; int qt[N],ans[N]; bits now,xs[N1]; void _flip(bits a,int x){a[x>>5]^=1<<(x&31);} void _clr(bits a){memset(a,0,sizeof(int)*(n/32+2));} void ins(int x){_flip(now,ps[x]++);} void del(int x){_flip(now,--ps[x]);} void _and(bits a,bits b){ int mx=n/32+2; for(int i=0;i<mx;i+=8){ a[0]&=b[0]; a[1]&=b[1]; a[2]&=b[2]; a[3]&=b[3]; a[4]&=b[4]; a[5]&=b[5]; a[6]&=b[6]; a[7]&=b[7]; a+=8,b+=8; } } int c1[67777]; int _and_c1(bits a,bits b){ int mx=n/32+2,s1=0,s2=0,s3=0; for(int i=0;i<mx;++i){ u32 x=a[i]&b[i]; s1+=c1[x>>22]; s2+=c1[x>>11&2047]; s3+=c1[x&2047]; } return s1+s2+s3; } void calc(){ int B=n/sqrt(qp)+1; for(int i=0;i<n;++i)pos[i]=i/B,ps[v[i]]=v[i]; _clr(now); for(int i=0;i<qp/3;++i)qt[i]=0; std::sort(qs,qs+qp); int L=1,R=0; for(int i=0;i<qp;++i){ int l=qs[i].l,r=qs[i].r,id=qs[i].id; while(R<r)ins(v[++R]); while(L>l)ins(v[--L]); while(R>r)del(v[R--]); while(L<l)del(v[L++]); int t=++qt[id]; if(t==1)memcpy(xs[id],now,sizeof(int)*(n/32+2)); else if(t==2)_and(xs[id],now); else ans[id]-=_and_c1(xs[id],now)*3; } for(int i=0;i<qp/3;++i)printf("%d ",ans[i]); qp=0; } int main(){ for(int i=1;i<65536;++i)c1[i]=c1[i>>1]+(i&1); n=_(),m=_(); for(int i=0;i<n;++i)v[i]=vs[i]=_(); std::sort(vs,vs+n); for(int i=0;i<n;++i)v[i]=std::lower_bound(vs,vs+n,v[i])-vs; for(int i=0;i<m;++i){ ans[qp/3]=0; for(int j=0;j<3;++j){ qs[qp].l=_()-1; qs[qp].r=_()-1; qs[qp].id=qp/3; ans[qs[qp].id]+=qs[qp].r-qs[qp].l+1; ++qp; } if(qp>=(N1-7)*3||i+1==m)calc(); } return 0; }