【Ynoi2016】【bzoj4939】掉进兔子洞 题解

题目大意

  一个长为 $n$ 的序列 $a$。
  有 $m$ 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。
  注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，
  比如三个区间是 $[1,2,2,3,3,3,3]$，$[1,2,2,3,3,3,3]$ 与 $[1,1,2,3,3]$，就一起扔掉了 1 个 $1$，1 个 $2$，2 个 $3$。

  $n,m \leq 10^5,~1 \leq a_i \leq 10^9$
  3s，512M

$$\\$$ $$\\$$ $$\\$$

题解

  这题的 bitset 技巧很妙的。

  每个询问有三个区间，如果 $a$ 序列的数两两不同，那么把每个区间内包含的数做成 bitset，则每个询问的三个区间 and 起来就好了。
  求每个区间的 bitset，就用莫队。（其他方法似乎空间都不大好。。

  现在 $a$ 序列的数可以相同，则可以这样：离散化的时候为每个数留出它出现次数那么多的空位，比如 $[10,10,20,20,20,30,30,30,30]$ 离散化成 $[1,1,3,3,3,5,5,5,5]$，这样的话在莫队加入删除一个数 $x$ 时修改 bitset 的 $x+cnt_x-1$ 这一位（$cnt_x$ 表示莫队过程中 $x$ 的出现次数）。

  还有一个问题是如果为每一个询问存一个 bitset 的话空间不够。所以可以把询问分 3 段，即当成有 3 个 case 的多测来做。

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=1e5+5;

struct QST{
	int l,r,i,k;
};
bool cmpQ(const QST &a,const QST &b) {return a.k<b.k || a.k==b.k && a.r<b.r;}

int n,m,sqrtn,a[maxn],l1[maxn],r1[maxn],l2[maxn],r2[maxn],l3[maxn],r3[maxn];

struct B{int val,i;} b[maxn];
bool cmpB(const B &a,const B &b) {return a.val<b.val;}
int maxr;
void discretize()
{
	fo(i,1,n) b[i]=(B){a[i],i};
	sort(b+1,b+1+n,cmpB);
	int cnt=1;
	fo(i,1,n)
	{
		if (i==1 || b[i].val>b[i-1].val) maxr+=cnt, cnt=1;
			else cnt++;
		a[b[i].i]=maxr;
	}
}

int Ans[maxn],q0,tong[maxn];
QST q[2*maxn];
bitset<maxn> bs[maxn/3],nowbs;
void add(int x) { nowbs[x+(++tong[x])-1]=1; }
void del(int x) { nowbs[x+(tong[x]--)-1]=0; }
void solve(int ql,int qr)
{
	int qnum=qr-ql+1;
	q0=0;
	fo(i,ql,qr)
	{
		q[++q0]=(QST){l1[i],r1[i],i-ql+1,l1[i]/sqrtn};
		q[++q0]=(QST){l2[i],r2[i],i-ql+1,l2[i]/sqrtn};
		q[++q0]=(QST){l3[i],r3[i],i-ql+1,l3[i]/sqrtn};
	}
	sort(q+1,q+1+q0,cmpQ);
	
	fo(i,1,qnum) bs[i].set();
	nowbs.reset();
	memset(tong,0,sizeof(tong));
	memset(Ans,0,sizeof(Ans));
	fo(i,1,q0) Ans[q[i].i]+=q[i].r-q[i].l+1;
	
	int nowl,nowr;
	fo(i,1,q0) if (i==1)
	{
		fo(j,q[i].l,q[i].r) add(a[j]);
		bs[q[i].i]&=nowbs;
		nowl=q[i].l, nowr=q[i].r;
	} else
	{
		for(; q[i].l<nowl; nowl--) add(a[nowl-1]);
		for(; nowr<q[i].r; nowr++) add(a[nowr+1]);
		for(; nowl<q[i].l; nowl++) del(a[nowl]);
		for(; q[i].r<nowr; nowr--) del(a[nowr]);
		bs[q[i].i]&=nowbs;
	}
	
	fo(i,1,qnum)
	{
		Ans[i]-=bs[i].count()*3;
		printf("%d\n",Ans[i]);
	}
}

int main()
{
	scanf("%d %d",&n,&m);
	fo(i,1,n) scanf("%d",&a[i]);
	fo(i,1,m) scanf("%d %d %d %d %d %d",&l1[i],&r1[i],&l2[i],&r2[i],&l3[i],&r3[i]);
	
	discretize();
	
	sqrtn=sqrt(n);
	int m1=m/3, m2=m1<<1;
	if (1<=m1) solve(1,m1);
	if (m1<m2) solve(m1+1,m2);
	if (m2<m) solve(m2+1,m);
}