Steven_MengのBlog

传送门

给你一个序列${a_i}$,和四个数$l1,r1,l2,r2$,求区间$[l1,r1],[l2,r2]$中相同的数有多少对。

当然你不能维护四个指针,考虑容斥原理,我们不妨设$f(x,y)$为下标为$[1,x]$和下标为$[1,y]$中相同的$a_i$有多少对,这样我们可以开心地容斥$Query(l1,r1,l2,r2)=f(l2,r2)-f(l1-1,r2)-f(r1,l2-1)+f(l1-1,l2-1)$。

具体实现的时候,$Query$结构体里面存一个$f$代表符号即可。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],Ans[MAXN],cnt1[MAXN],cnt2[MAXN],qcnt,pos[MAXN];
struct Query{
int pos1,pos2;//代表的是[1,pos1],[1,pos2]
int id,f;//容斥的符号
}Q[MAXN*4];
inline bool operator < (const Query &a,const Query &b){
return pos[a.pos1]<pos[b.pos1]||(pos[a.pos1]==pos[b.pos1]&&((pos[a.pos1]&1)?a.pos2<b.pos2:a.pos2>b.pos2));
}
inline void AddQuery(int pos1,int pos2,int id,int f){
Q[++qcnt].f=f,Q[qcnt].id=id,Q[qcnt].pos1=pos1,Q[qcnt].pos2=pos2;
}
int main(){
int n=read(),m=read();
int Size=sqrt(n);
for (register int i=1;i<=n;++i){
a[i]=read();
pos[i]=(i-1)/Size+1;
}
for (register int i=1;i<=m;++i){
int l1=read(),r1=read(),l2=read(),r2=read();
AddQuery(r1,r2,i,1);
AddQuery(l1-1,r2,i,-1);
AddQuery(r1,l2-1,i,-1);
AddQuery(l1-1,l2-1,i,1);
}
sort(Q+1,Q+1+qcnt);
int r1=0,r2=0,ans=0;
for (register int i=1;i<=qcnt;++i){
while (r1<Q[i].pos1){
++cnt1[a[++r1]];
ans+=cnt2[a[r1]];
}
while (r1>Q[i].pos1){
--cnt1[a[r1]];
ans-=cnt2[a[r1--]];
}
while (r2<Q[i].pos2){
++cnt2[a[++r2]];
ans+=cnt1[a[r2]];
}
while (r2>Q[i].pos2){
--cnt2[a[r2]];
ans-=cnt1[a[r2--]];
}
Ans[Q[i].id]+=Q[i].f*ans;
}
for (register int i=1;i<=m;++i){
printf("%d\n",Ans[i]);
}
}

 评论