洛谷4688 BZOJ4939 YNOI2016 掉进兔子洞 位运算 bitset 莫队

题目链接

题意：

有一个长为 n 的序列 a。有 m 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。 注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完。

题解：

对于每次询问，我们设三个数组中都出现的数的总个数为x，那么相当于求 r 1 − l 1 + 1 + r 2 − l 2 + 1 + r 3 − l 3 + 1 − 3 ∗ x r1-l1+1+r2-l2+1+r3-l3+1-3*x r1−l1+1+r2−l2+1+r3−l3+1−3∗x。我们发现这个式子只有x比较难维护。

我们先把所有的 a i a_i ai​离散化，但是并不去重，原因是我们对于每一个相同的数字，我们用bitset中相邻的一段维护，去重之后不好维护。

举个例子（引用别人的例子）：

例如对样例数据：1 2 2 3 3 ，离散化后应为：1 2 2 4 4，在bitset中用第2位表示出现的第1个2，第3位表示第二个2，以此类推。

我们考虑用状压的思想，把每个数在不在这个区间出现过用一个二进制表示，但是我们发现这个数太大了，即使用long long也压不下，于是考虑用bitset。这样的话三个区间的答案就是三个区间的bitset&之后1的个数。但是我们每次暴力地对每个询问用bitset复杂度还是会爆炸，所以我们考虑用数据结构维护。这个题并没有什么可合并的性质，所以似乎不能用线段树等树形数据结构来维护。于是我们考虑更加暴力功能更强的莫队来维护。

还有一点就是这题直接开bitset会MLE，也就是开不下10w个长度为10w的bitset，于是我们把询问分成4组，每组2.5w个询问，这样就不会MLE了。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,a[100010],b[100010],l1[100010],r1[100010],l2[100010],r2[100010],l3[100010],r3[100010];
bitset<100010> bi[25010],cur;
const int del=25000;
int vis[25010],ans[100010],cnt,num[100010],bl[100010],sz;
struct qwq
{
	int l,r,id,pos;
}q[100010];
inline int read()
{
	int x=0;
	char s=getchar();
	while(s>'9'||s<'0')
	s=getchar();
	while(s>='0'&&s<='9')
	{
		x=x*10+s-'0';
		s=getchar();
	}
	return x;
}
inline int cmp(qwq x,qwq y)
{
	if(x.pos<y.pos)
	return x.pos<y.pos;
	if(x.pos==y.pos&&x.r<y.r)
	return x.r<y.r;
	return 0;
}
inline void cal(int x,int opt)
{
	x=a[x];
	if(opt==1)
	cur[x+num[x]]=1;
	else
	cur[x+num[x]-1]=0;
	num[x]+=opt;
}
inline void solve(int x,int y)
{
	memset(num,0,sizeof(num));
	memset(vis,0,sizeof(vis));
	cur.reset();
	int l=1,r=0;
	cnt=0;
	for(int i=x;i<=y;++i)
	{
		q[++cnt].l=l1[i];
		q[cnt].r=r1[i];
		q[cnt].id=i;
		q[cnt].pos=bl[l1[i]];
		ans[i]+=r1[i]-l1[i]+1;
		q[++cnt].l=l2[i];
		q[cnt].r=r2[i];
		q[cnt].id=i;
		q[cnt].pos=bl[l2[i]];
		ans[i]+=r2[i]-l2[i]+1;
		q[++cnt].l=l3[i];
		q[cnt].r=r3[i];
		q[cnt].id=i;
		q[cnt].pos=bl[l3[i]];
		ans[i]+=r3[i]-l3[i]+1;
	}
	sort(q+1,q+cnt+1,cmp);
	for(int i=1;i<=cnt;++i)
	{
		while(q[i].r>r)
		{
			++r;
			cal(r,1);
		}
		while(q[i].l<l)
		{
			--l;
			cal(l,1);
		}
		while(q[i].r<r)
		{
			cal(r,-1);
			--r;
		}
		while(q[i].l>l)
		{
			cal(l,-1);
			++l;
		}
		if(!vis[q[i].id-x+1])
		{
			vis[q[i].id-x+1]=1;
			bi[q[i].id-x+1]=cur;
		}
		else
		bi[q[i].id-x+1]&=cur;
	}
	for(int i=x;i<=y;++i)
	ans[i]-=bi[i-x+1].count()*3;
}
int main()
{
	n=read();
	m=read();
	sz=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		b[i]=a[i];
		bl[i]=(i-1)/sz+1;
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;++i)
	a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	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();		
	}
	for(int i=1;i<=m;i+=del)
	solve(i,min(m,i+del-1));
	for(int i=1;i<=m;++i)
	printf("%d\n",ans[i]);
	return 0;
}