loj #2254. 「SNOI2017」一个简单的询问 #2254. 「SNOI2017」一个简单的询问
题目描述
给你一个长度为 NNN 的序列 aia_iai，1≤i≤N1leq ileq N1≤i≤N，和 qqq 组询问，每组询问读入 l1,r1,l2,r2l_1,r_1,l_2,r_2l1,r1,l2,r2，需输出
∑x=0∞get(l1,r1,x)⋅get(l2,r2,x) sumlimits_{x=0}^infty ext{get}(l_1,r_1,x)cdot ext{get}(l_2,r_2,x)x=0∑∞get(l1,r1,x)⋅get(l2,r2,x)get(l,r,x) ext{get}(l,r,x)get(l,r,x) 表示计算区间 [l,r][l,r][l,r] 中，数字 xxx 出现了多少次。
输入格式
第一行，一个数字 NNN，表示序列长度。
第二行，NNN 个数字，表示 a1∼aNa_1sim a_Na1∼aN。
第三行，一个数字 QQQ，表示询问个数。
第 4∼Q+34sim Q+34∼Q+3 行，每行四个数字 l1,r1,l2,r2l_1,r_1,l_2,r_2l1,r1,l2,r2，表示询问。
输出格式
对于每组询问，输出一行一个数字，表示答案。
样例
样例输入
5
1 1 1 1 1
2
1 2 3 4
1 1 4 4样例输出
4
1数据范围与提示
对于 20%20\%20% 的数据，1≤N,Q≤10001leq N,Qleq 10001≤N,Q≤1000；
对于另外 30%30\%30% 的数据，1≤ai≤501leq a_ileq 501≤ai≤50；
对于 100%100\%100% 的数据，N,Q≤50000N,Qleq 50000N,Q≤50000，1≤ai≤N1leq a_ileq N1≤ai≤N，1≤l1≤r1≤N1leq l_1leq r_1leq N1≤l1≤r1≤N，1≤l2≤r2≤N1leq l_2leq r_2leq N1≤l2≤r2≤N。
数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000 ms，省选评测时调整为 4000 ms，这里按 4000 ms 调整。
注意：答案有可能超过 int 的最大值。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 50010 using namespace std; int n,a[maxn],b[maxn],l1,r1,l2,r2,mx,cnt[maxn][2],num; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); num=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+num+1,a[i])-b; int T;scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&l1,&r1,&l2,&r2); memset(cnt,0,sizeof(cnt)); for(int i=l1;i<=r1;i++)cnt[a[i]][0]++; for(int i=l2;i<=r2;i++)cnt[a[i]][1]++; long long ans=0; for(int i=1;i<=num;i++)ans+=1LL*cnt[i][0]*cnt[i][1]; cout<<ans<<endl; } return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 50010 using namespace std; int n,block[maxn],sz,a[maxn],num1[maxn],num2[maxn],m,tot,L,R; long long res=0,Ans[maxn]; struct node{ int l,r,id,ad; bool operator < (const node &b)const{ if(block[l]==block[b.l])return r<b.r; return l<b.l; } }q[maxn*4]; int main(){ scanf("%d",&n);sz=sqrt(n); for(int i=1;i<=n;i++)block[i]=(i-1)/sz+1; for(int i=1;i<=n;i++)scanf("%d",&a[i]); scanf("%d",&m); int l1,l2,r1,r2; for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&l1,&r1,&l2,&r2); q[++tot]=(node){r1,r2,i,1}; q[++tot]=(node){r1,l2-1,i,-1}; q[++tot]=(node){l1-1,r2,i,-1}; q[++tot]=(node){l1-1,l2-1,i,1}; } sort(q+1,q+tot+1); for(int i=1;i<=tot;i++){ while(L<q[i].l)L++,res+=num2[a[L]],++num1[a[L]]; while(L>q[i].l)res-=num2[a[L]],--num1[a[L]],--L; while(R<q[i].r)++R,res+=num1[a[R]],++num2[a[R]]; while(R>q[i].r)res-=num1[a[R]],--num2[a[R]],--R; Ans[q[i].id]+=q[i].ad*res; } for(int i=1;i<=m;i++)cout<<Ans[i]<<endl; return 0; }