BZOJ 4939: [Ynoi2016]掉进兔子洞(莫队+bitset)

解题思路

　　刚开始想到了莫队+\(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;

}