江西医院网站建设,建设企业银行怎么转账,seo网站优化论文,wordpress页头正题
题目链接:https://www.luogu.com.cn/problem/P5268 题目大意 nnn个数的一个序列#xff0c;定义get(l1,r1,x)get(l_1,r_1,x)get(l1,r1,x)表示区间[l1,r1][l_1,r_1][l1,r1]中有多少个xxx。
每次询问(l1,r1,l2,r2)(l_1,r_1,l_2,r_2)(l1,r1,l2,r2)求∑x∞…正题
题目链接:https://www.luogu.com.cn/problem/P5268 题目大意
nnn个数的一个序列定义get(l1,r1,x)get(l_1,r_1,x)get(l1,r1,x)表示区间[l1,r1][l_1,r_1][l1,r1]中有多少个xxx。
每次询问(l1,r1,l2,r2)(l_1,r_1,l_2,r_2)(l1,r1,l2,r2)求∑x∞get(l1,r1,x)∗get(l2,r2,x)\sum_{x}^{\infty}get(l_1,r_1,x)*get(l_2,r_2,x)x∑∞get(l1,r1,x)∗get(l2,r2,x) 解题思路
考虑莫队有get(l1,r1,x)∗get(l2,r2,x)get(l_1,r_1,x)*get(l_2,r_2,x)get(l1,r1,x)∗get(l2,r2,x) get(1,r1,x)∗get(1,r2,x)−get(1,l1−1,x)∗get(1,r2,x)get(1,r_1,x)*get(1,r_2,x)-get(1,l_1-1,x)*get(1,r_2,x)get(1,r1,x)∗get(1,r2,x)−get(1,l1−1,x)∗get(1,r2,x)−get(1,r1,x)∗get(1,l2−1,x)get(1,l1−1,x)∗get(1,l2−1,x)-get(1,r_1,x)*get(1,l_2-1,x)get(1,l_1-1,x)*get(1,l_2-1,x)−get(1,r1,x)∗get(1,l2−1,x)get(1,l1−1,x)∗get(1,l2−1,x)
然后分成四次莫队就好了 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N5e410;
struct node{int l,r,id,w;
}q[N*4];
int n,cnt,T,Q,a[N],ans[N],v1[N],v2[N];
bool cmp(node x,node y)
{return x.l/Ty.l/T||(x.l/Ty.l/Tx.ry.r);}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);Tsqrt(n);scanf(%d,Q);for(int i1;iQ;i){int l1,r1,l2,r2;scanf(%d%d%d%d,l1,r1,l2,r2);q[cnt](node){r1,r2,i,1};q[cnt](node){r1,l2-1,i,-1};q[cnt](node){l1-1,r2,i,-1};q[cnt](node){l1-1,l2-1,i,1};}sort(q1,q1cnt,cmp);int l0,r0,val0;for(int i1;icnt;i){while(rq[i].r)r,v2[a[r]],valv1[a[r]];while(rq[i].r)v2[a[r]]--,val-v1[a[r]],r--;while(lq[i].l)l,v1[a[l]],valv2[a[l]];while(lq[i].l)v1[a[l]]--,val-v2[a[l]],l--;ans[q[i].id]q[i].w*val;}for(int i1;iQ;i)printf(%d\n,ans[i]);}
