P5268 [SNOI2017] 一个简单的询问

一个简单的询问

显然这个询问并不简单
如果做过莫比乌斯反演入门题problem b就会想到利用容斥将询问拆成四个

那么我们现在的问题变成如何求
[1,l]
[1,r]
两个区间之间的答案，那么也是直接用莫队即可，只是维护的是两个区间的右端点，和原来的莫队有一些不一样，但是大体相同。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
const int N=5e4+5;
int S;
struct node{
	int l,r,id,op;
	bool operator < (const node&x) const {
		if (l/S != x.l/S) return l<x.l;
		return (l/S)&1 ? r<x.r : r>x.r;
	}
};
node q[N*8];
int c[N],n,m,tot,l,r;
ll a[N],b[N],sum,ans[N];
void add1(int x){
	sum+=b[x];
	a[x]++;
}
void add2(int x){
	sum+=a[x];
	b[x]++;
}
void sub1(int x){
	sum-=b[x];
	a[x]--;
}
void sub2(int x){
	sum-=a[x];
	b[x]--;
}
int main(){
	
//	freopen("data.in","r",stdin);    
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&c[i]);
	
	S=(int)pow(n,0.5);
	scanf("%d",&m);
	fo(p,1,m) {
		int x,y,z,w;
		scanf("%d %d %d %d",&x,&y, &z,&w);
		
		q[++tot]=(node){y,w,p,1};
		if ((x-1)>0) q[++tot]=(node){x-1,w,p,-1};
		if ((z-1)>0) q[++tot]=(node){y,z-1,p,-1};
		if ((x-1)>0 && (z-1)>0)	q[++tot]=(node){x-1,z-1,p,1};
	}
	fo(i,1,tot) if (q[i].l>q[i].r) swap(q[i].l, q[i].r);
	
	sort(q+1,q+tot+1);
	
//	fo(i,1,tot) {
//		printf("%d %d %d %d\n",q[i].l,q[i].r, q[i].id, q[i].op);
//	}

	
	l=0; r=0;
	while (l<q[1].l) ++a[c[++l]];
	while (r<q[1].r) {
		sum+=a[c[++r]];
		b[c[r]]++;
	}
	
	ans[q[1].id]+=(ll)q[1].op*sum;
	
	
	fo(i,2,tot) {
		while (l>q[i].l) sub1(c[l--]);
		while (r<q[i].r) add2(c[++r]);
	
		while (l<q[i].l) add1(c[++l]);
		while (r>q[i].r) sub2(c[r--]);
		
		ans[q[i].id]+=(ll)q[i].op*sum;
		
//		printf("%lld\n",sum);
	}
	
	fo(i,1,m) printf("%lld\n",ans[i]);
	return 0;
	
}