bzoj 5016 [Snoi 2017] 간단 한 질문

제목.
우선, 확실한 것 은 이것 은 반드시 데이터 구조의 문제 일 것 이다. 그러나 문제 가 묻 는 형식 이 너무 복잡 하 므 로 우 리 는 먼저 간략하게 고려 해 야 한다.
우선, get (l, r, x) 이 get (r, x) - get (l - 1, x) 으로 변 하 는 것 은 매우 분명 하 다. 새로운 get (n, x) 은 1... n 에 몇 개의 x 가 있다 는 것 을 나타 낸다.
get (l1, r1, x) get (l2, r2, x) = (get (r1, x) - get (l1 - 1, x) (get (r2, x) - get (l2 - 1, x) 은 ans (l, r, x) 로 get (l, x) get (r, x) 을 표시 한 다음 에 우 리 는 이 물건 을 모 팀 으로 풀 수 있다 는 것 을 알 수 있다. 그러면 우 리 는 모든 질문 을 네 개 로 뜯 은 후에 그만 둘 수 있다.

#include
#define N 50000
using namespace std;
typedef long long ll;
int n,m,siz,v[N+5],cl[N+5],cr[N+5],tot;
ll ans[N+5],now;
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0,b=1;
    char c=nc();
    for(;!(c<='9'&&c>='0');c=nc())if(c=='-')b=-1;
    for(;c<='9'&&c>='0';c=nc())x=x*10+c-'0';
    return x*b;
}
inline void write(ll x)
{
    if(x==0)putchar('0');
    else
    {
        char buf[25];
        int len=0;
        if(x<0)putchar('-'),x=-x;
        while(x)buf[++len]=x%10+'0',x/=10;
        for(int i=len;i>=1;i--)putchar(buf[i]);
    }
    putchar('
');
}
struct data{
    int l,r,id,flg;
    data(){}
    data(int a,int b,int c,int d){l=min(a,b),r=max(a,b),flg=c,id=d;};
    bool operator const data & A)const{
        return ((l-1)/siz==(A.l-1)/siz?r1)/siz1)/siz);
    }
}a[N*4+5];
int main()
{
    freopen("in.txt","r",stdin);
    int x1,x2,y1,y2,l,r;
    n=read();siz=sqrt(n);
    for(int i=1;i<=n;i++)v[i]=read();
    m=read();l=r=0;
    for(int i=1;i<=m;i++)
    {
        x1=read(),y1=read(),x2=read(),y2=read();
        a[++tot]=data(y1,y2,1,i);
        if(x1>1)a[++tot]=data(x1-1,y2,-1,i);
        if(x2>1)a[++tot]=data(y1,x2-1,-1,i);
        if(x1>1&&x2>1)a[++tot]=data(x1-1,x2-1,1,i);
    }
    sort(a+1,a+tot+1);
    for(int i=1;i<=tot;i++)
    {
        while(lwhile(rwhile(l>a[i].l)cl[v[l]]--,now-=cr[v[l]],l--;
while(r>a[i].r)cr[v[r]]--,now-=cl[v[r]],r--;
ans[a[i].id]+=(ll)a[i].flg*now;
}
for(int i=1;i<=m;i++)write(ans[i]);
return 0;
}