【 Gym - 101138D 】Strange Queries （莫队算法）---饶文津

题意

a数组大小为n。(1 ≤ n ≤ 50 000) (1 ≤ q ≤ 50 000)(1 ≤ ai ≤ n) q个查询，询问两个区间相同的数有多少对。

题解

代码#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> #define N 50005 #define ll long long using namespace std; int n,m,a[N],qs,pos[N]; ll ans[N],s[N]; struct node{int l,r,d;}p[N<<2]; bool cmp(node a,node b){ return pos[a.l]<pos[b.l]||pos[a.l]==pos[b.l]&&a.r<b.r; } void add(int p,ll &f){ f+=s[a[p]]++; } void sub(int p,ll &f){ f-=--s[a[p]]; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1,j=1;i<=n;i++){ if(i%(int)sqrt(n)==0)j++; pos[i]=j; } scanf("%d",&qs); for(int i=1;i<=qs;i++){ int sl,sr,tl,tr; scanf("%d%d%d%d",&sl,&sr,&tl,&tr); sr++;tl--; //[sl,tr]-[sl,tl-1]-[sr+1,tr]+[sr+1,tl-1] p[m++]=(node){sl,tr,i};p[m++]=(node){sl,tl,-i}; p[m++]=(node){sr,tr,-i};p[m++]=(node){sr,tl,i}; } sort(p,p+m,cmp); int L=n+1,R=n; ll num=0; for(int i=0;i<m;i++){ while(L<p[i].l) sub(L++,num); while(L>p[i].l) add(--L,num); while(R>p[i].r) sub(R--,num); while(R<p[i].r) add(++R,num); if(p[i].d>0)ans[p[i].d]+=num; else ans[-p[i].d]-=num; } for(int i=1;i<=qs;i++)printf("%lldn",ans[i]); return 0; } ---来自腾讯云社区的---饶文津