传送门
给你一个序列{ai},和四个数l1,r1,l2,r2,求区间[l1,r1],[l2,r2]中相同的数有多少对。
当然你不能维护四个指针,考虑容斥原理,我们不妨设f(x,y)为下标为[1,x]和下标为[1,y]中相同的ai有多少对,这样我们可以开心地容斥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; 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]); } }
|