「SNOI2017」一个简单的询问

发表于 | 分类于 | | 浏览量： 次

嗯哼？这不是赤裸裸的莫队吗QwQ？

传送门

BZOJ5016

题解

首先拐一道弯，令$F(L1,R1,L2,R2)=\sum_{x=0}^{\infty}{get(L1,R1,x)\cdot get(L2,R2,x)}​$。

那么根据容斥的原理，可以得到$F(L1,R1,L2,R2)=F(1,R1,1,R2)-F(1,L1,1,R2)-F(1,R1,1,L2)+F(1,L1,1,L2)$。

那么就把一个询问先拆成四个询问。

然后只要想办法求出$F(1,x,1,y)$。裸的莫队啊啊啊！！！注意细节即可。

然后就没有然后了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=50005;
int n,q,A[maxn],S,Area[maxn],tot,cnt1[maxn],cnt2[maxn],p1,p2;LL ans[maxn],now;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct Interval
{
	int R1,R2,f,id;
	void Init(){if(R1>R2)swap(R1,R2);}
	bool operator < (const Interval& b)const{return Area[R1]<Area[b.R1]||(Area[R1]==Area[b.R1]&&((Area[R1]&1)?R2<b.R2:R2>b.R2));}
}Q[maxn*4];
int main()
{
	n=read();S=sqrt(n)+1e-10;
	for(int i=1;i<=n;i++) A[i]=read();
	for(int i=1;i<=n;i++) Area[i]=(i-1)/S+1;
	q=read();
	for(int i=1;i<=q;i++)
	{
		int L1=read(),R1=read(),L2=read(),R2=read();
		tot++;Q[tot].R1=R1;Q[tot].R2=R2;Q[tot].f=1;Q[tot].Init();Q[tot].id=i;
		tot++;Q[tot].R1=L1-1;Q[tot].R2=R2;Q[tot].f=-1;Q[tot].Init();Q[tot].id=i;
		tot++;Q[tot].R1=R1;Q[tot].R2=L2-1;Q[tot].f=-1;Q[tot].Init();Q[tot].id=i;
		tot++;Q[tot].R1=L1-1;Q[tot].R2=L2-1;Q[tot].f=1;Q[tot].Init();Q[tot].id=i;
	}
	sort(Q+1,Q+1+tot);
	for(int i=1;i<=tot;i++)
	{
		while(p2<Q[i].R2){p2++;cnt2[A[p2]]++;now+=cnt1[A[p2]];}
		while(p1>Q[i].R1){cnt1[A[p1]]--;now-=cnt2[A[p1]];p1--;}
		while(p2>Q[i].R2){cnt2[A[p2]]--;now-=cnt1[A[p2]];p2--;}
		while(p1<Q[i].R1){p1++;cnt1[A[p1]]++;now+=cnt2[A[p1]];}
		ans[Q[i].id]+=now*Q[i].f;
	}
	for(int i=1;i<=q;i++)
		printf("%lld\n",ans[i]);
	return 0;
}