[Ynoi2016] 掉進兔子洞

給出一個序列，和m個查詢。每一個查詢有3個區間，問3個區間去掉相同的數字後，一共有多少個數字。

利用bitset的集合交來查詢。b1&b2&b3可以統計3個區間一共有多少個相同數字。

對于某個數字i，在序列裡面出現了k次，那麼他就占了k位。這種可以通過離散化重新配置設定id來實作。

fr(i,1,n+1) a[i] = lower_bound(v+1,v+1+n,a[i])-(v+1);
           

是以一共需要n位來存儲。這樣就可以直接對m個查詢當成是m*3個query來做了。

對于每一個query，把答案&到對應的ans上。

ans[q[i].id] &= sum;
           

但是m有10^5，n*m就很大，需要對m進行分段處理。

對于每一個分段，用莫隊就好了。add的時候對應的位置1，del就置0.

void add(int idx){
	sum.set(idx + num[idx]++);
}

void del(int idx){
	sum.reset(idx+(--num[idx]));
}
           

代碼

int block_size;

struct query{
	int l,r,id;
	int block;
	int r_block;
	int t;
	bool operator<(const query &q) const{
		if(block != q.block) return block<q.block;
		return r<q.r;
	}
};

bitset<N> ans[N/3+10],sum;
int tot[N],num[N];
int a[N],v[N];

void add(int idx){
	sum.set(idx + num[idx]++);
}

void del(int idx){
	sum.reset(idx+(--num[idx]));
}

vector<query> q;
void sol(){
	sum.reset();
	clr(num);
	sort(q.begin(), q.end());
	fr(i,0,q.size()/3){
		tot[i] = 0;
		ans[i].set();
	}

	int l = 1, r = 1;
	add(a[1]);
	fr(i,0,q.size()){
		while(l>q[i].l) add(a[--l]);
		while(r<q[i].r) add(a[++r]);
		while(l<q[i].l) del(a[l++]);
		while(r>q[i].r) del(a[r--]);
		ans[q[i].id] &= sum;
		tot[q[i].id] += q[i].r - q[i].l + 1;
	}
	fr(i,0,q.size()/3){
		pf("%d\n",tot[i] - 3*ans[i].count());
	}
}

int main(){
	int n,m;
	sf("%d%d",&n,&m);
	block_size = sqrt(n);
	int process_num = max(1,m/3);
	fr(i,1,n+1){
		sf("%d",&a[i]);
		v[i] = a[i];
	}
	sort(v+1,v+1+n);
	fr(i,1,n+1) a[i] = lower_bound(v+1,v+1+n,a[i])-(v+1);
	fr(i,0,m){
		fr(j,0,3){
			query qy;
			sf("%d%d",&qy.l,&qy.r);
			qy.id = q.size()/3;
			qy.block = qy.l/block_size;
			q.pb(qy);
		}
		if((i == m-1) || (i+1)%process_num==0){
			sol();
			q.clear();
		}
	}
}