【SNOI2017】【莫队】一个简单的询问

【描述】

【思路】

这道题似乎没有什么难度。$n<=50000$，然后要维护的式子又相当地骚，这挺莫队的。唯一就是这个询问是对于一个四元组的询问，莫队并不支持。所以我们就可以用二维前缀和的思想容斥一下，把一个询问拆成四个询问，就可以使用莫队了。 代码：

#include<bits/stdc++.h> #define re register using namespace std; const int N=1e5+5; int n,m,l1,r1,l2,r2,x; inline int red(){ int data=0;int w=1; char ch=0; ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar(); return data*w; } int col[N],cnt[N][2],a[N],tot=0,l=1,r=0; long long ans[N]; long long now=0; struct node{ int id,s,l,r; friend inline bool operator<(const node&a,const node&b){return col[a.l]<col[b.l]||(col[a.l]==col[b.l]&&a.r<b.r);} }q[N<<2|1]; inline void add(int pos,int floor){now+=cnt[a[pos]][floor^1];cnt[a[pos]][floor]++;} inline void del(int pos,int floor){now-=cnt[a[pos]][floor^1];cnt[a[pos]][floor]--;} int main(){n=red();x=sqrt(n); for(int re i=1;i<=n;i++)a[i]=red(),col[i]=(i-1)/x+1;m=red(); for(int re i=1;i<=m;i++){ l1=red(),r1=red(); l2=red(),r2=red(); q[++tot]=(node){i,1,r1,r2}; q[++tot]=(node){i,1,l1-1,l2-1}; q[++tot]=(node){i,-1,l1-1,r2}; q[++tot]=(node){i,-1,r1,l2-1}; }sort(q+1,q+tot+1); for(int re i=1;i<=tot;i++){ while(r<q[i].r)add(++r,1);while(r>q[i].r)del(r--,1); while(l<q[i].l)add(++l,0);while(l>q[i].l)del(l--,0); ans[q[i].id]+=q[i].s*now; }for(int re i=1;i<=m;i++)cout<<ans[i]<<"\n"; }