传送门
解题思路
刚开始想到了莫队 +\(bitset\) 去维护信息, 结果发现空间不太够.. 试了各种奇技淫巧都 \(MLE\), 最后 \(\%\) 了发题解发现似乎可以分段做.. 这道题做法具体来说就是开 \(3\) 个 \(bitset\), 然后对原序列离散化之后给每个值规定一个开始的位置, 之后就可以莫队搞, 计算答案是用总的元素个数减去扔掉的, 而扔掉的其实就是三个 \(bitset\) 做与运算后 \(1\) 的个数, 时间复杂度 \(O(n\sqrt n+\frac{n^2}{w})\).\(bzoj\) 上时限 \(80s\) 跑了 \(80s\), 荣获倒一.
代码
- #include<bits/stdc++.h>
- 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.l;
- if((A.l/siz)&1) return A.r>B.r;
- return A.r<B.r;
- }
- Data(int _l=0,int _r=0,int _id=0,int _type=0){
- l=_l; r=_r; id=_id; type=_type;
- }
- }q[N*3];
- bitset<N> 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) R++,Add(R);
- while(L<q[i].l) Del(L),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;
- }
来源: http://www.bubuko.com/infodetail-2988687.html