正题

题目链接:https://www.luogu.com.cn/problem/P4688

题目大意

给出一个长度为\(n\)的序列\(a\)。

然后\(m\)次询问给出三个区间，求这三个区间构成的可重集删去交集后剩下的数字个数和。

\(1\leq n,m\leq 10^5,1\leq a_i\leq 10^9\)

解题思路

考虑用总个数减去重复的个数。

那么现在问题是怎么求三个区间的交集。

假设不考虑重复的数的情况下我们可以莫队处理出三个区间的\(bitset\)然后或起来。

但是现在需要考虑重复的怎么处理，其实也很简单，因为我们是莫队，求出每个数字在序列中小于它的数字个数\(x\)，如果这个数字是第\(i\)次出现就标号为\(x+i\)就好了，这样就不会重复了。

然后会发现空间不够大，直接把所有询问分成若干小组来处理就好了。

时间复杂度：\(O(\frac{nm}{\omega}+m\sqrt n)\)

话说bitset的count竟然是\(O(\frac{n}{\omega})\)的/xia。

code

#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10,M=2e4+10;
struct node{
	int l,r,t;
}q[N];
int n,m,k,T,d[N],b[N],c[N],ans[M];
bool v[M];bitsetbst[M],now;
bool cmp(node x,node y)
{return (x.l/T==y.l/T)?(x.rq[i].r)Del(b[r]),r--;
		while(lq[i].l)l--,Add(b[l]);
		if(!v[q[i].t])
			bst[q[i].t]=now,v[q[i].t]=1;
		else bst[q[i].t]&=now;
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]-bst[i].count()*3);
	return;
}
int main()
{
//	freopen("xp1.in","r",stdin);
//	freopen("xp1.out","w",stdout);
	scanf("%d%d",&n,&m);
	T=sqrt(n);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]),d[i]=c[i];
	sort(d+1,d+1+n);
	for(int i=1;i<=n;i++){
		int l=1,r=n;
		while(l<=r){
			int mid=(l+r)>>1;
			if(d[mid]>=c[i])r=mid-1;
			else l=mid+1;
		}
		b[i]=l;
	}
	for(int i=0;i