BZOJ-5016: [Snoi2017]一个简单的询问

Description

给你一个长度为N的序列ai，1≤i≤N和q组询问，每组询问读入l1,r1,l2,r2，需输出get(l,r,x)表示计算区间[l,r]中，数字x出现了多少次,N,Q≤50000

把每个询问拆成关于前缀的四个询问，之后莫队处理所有询问即可。

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50100 
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int re=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
    return re;
}
int n,m,c,bl,w[N],t1[N],t2[N];
long long ans[N],now;
struct node
{
    int l,r,b,id,f;
}a[N<<2];
bool cmp(node x,node y){return x.b==y.b ? x.r<y.r : x.b<y.b;}
int main()
{
    n=read(); int i; bl=(int)sqrt(double(n))+1;
    for(i=1;i<=n;++i) w[i]=read();
    m=read(); int l1,l2,r1,r2;
    for(i=1;i<=m;++i)
    {
        l1=read()-1; r1=read();
        l2=read()-1; r2=read();
        a[++c].l=r1; a[c].r=r2; a[c].id=i; a[c].f=1;
        if(a[c].l>a[c].r) swap(a[c].l,a[c].r); a[c].b=a[c].l/bl;
        a[++c].l=l1; a[c].r=r2; a[c].id=i; a[c].f=-1;
        if(a[c].l>a[c].r) swap(a[c].l,a[c].r); a[c].b=a[c].l/bl;
        a[++c].l=r1; a[c].r=l2; a[c].id=i; a[c].f=-1;
        if(a[c].l>a[c].r) swap(a[c].l,a[c].r); a[c].b=a[c].l/bl;
        a[++c].l=l1; a[c].r=l2; a[c].id=i; a[c].f=1;
        if(a[c].l>a[c].r) swap(a[c].l,a[c].r); a[c].b=a[c].l/bl;
    }
    sort(a+1,a+c+1,cmp);
    int l=0,r=0;
    for(i=1;i<=c;++i)
    {
        while(l<a[i].l) ++l,t1[w[l]]++,now+=t2[w[l]];
        while(r<a[i].r) ++r,t2[w[r]]++,now+=t1[w[r]];
        while(l>a[i].l) t1[w[l]]--,now-=t2[w[l]],--l;
        while(r>a[i].r) t2[w[r]]--,now-=t1[w[r]],--r;
        ans[a[i].id]+=now*a[i].f;
    }
    for(i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}