洛谷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;
}