Luogu P5268 [SNOI2017]一个简单的询问

Link
简记(f(i,x)=get(1,i,x))。
首先拆询问，答案就变成了(sumlimits_xf(r_1,x)f(r_2,x)+f(l_1-1,x)f(l_2-1,x)-f(l_1-1,x)f(r_2,x)-f(l_2-1,x)f(r_1,x))。
然后我们用类似于莫队的套路搞搞就行了。

#pragma GCC optimize(3)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
namespace IO
{
    char ibuf[(1<<21)+1],*iS,*iT;
    char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
    int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
}using IO::read;
using std::sort;
using std::swap;
using i64=long long;
const int N=50007;
int n,Q,m,a[N],bel[N],t1[N],t2[N];i64 ans[N];
struct query{int l,r,id,x;}q[N<<2];
int operator<(const query&a,const query&b){return bel[a.l]==bel[b.l]? (bel[a.l]&1? a.r<b.r:a.r>b.r):a.l<b.l;}
int main()
{
    n=read();int B=sqrt(n)+rand()%5;i64 Ans=0;
    for(int i=1;i<=n;++i) a[i]=read(),bel[i]=(i-1)/B+1;
    Q=read();
    for(int i=1,l1,l2,r1,r2;i<=Q;++i) l1=read()-1,r1=read(),l2=read()-1,r2=read(),q[++m]={r1,r2,i,1},q[++m]={l1,l2,i,1},q[++m]={l1,r2,i,-1},q[++m]={l2,r1,i,-1};
    for(int i=1;i<=m;++i) if(q[i].l>q[i].r) swap(q[i].l,q[i].r);
    sort(q+1,q+m+1);
    for(int i=1,L=0,R=0;i<=m;++i)
    {
	int l=q[i].l,r=q[i].r;
	while(L<l) ++L,Ans+=t2[a[L]],++t1[a[L]];
	while(R<r) ++R,Ans+=t1[a[R]],++t2[a[R]];
	while(l<L) Ans-=t2[a[L]],--t1[a[L]],--L;
	while(r<R) Ans-=t1[a[R]],--t2[a[R]],--R;
	ans[q[i].id]+=Ans*q[i].x;
    }
    for(int i=1;i<=Q;++i) printf("%lld
",ans[i]);
}