#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int MAXN=50005;
int a,b,c,tot=0,len;
int num[MAXN],cntl[MAXN],cntr[MAXN];
ll res=0,ans[MAXN];
struct asks
{
    int ls,rs,lct,op;
    #define ls(k) ask[k].ls
    #define rs(k) ask[k].rs
    #define lct(k) ask[k].lct
    #define op(k) ask[k].op
}ask[MAXN<<2];
bool cmp(asks x,asks y)
{
    return x.ls/len==y.ls/len?x.rs<y.rs:x.ls/len<y.ls/len;
}
void addl(int x){cntl[x]++,res+=cntr[x];}
void addr(int x){cntr[x]++,res+=cntl[x];}
void reml(int x){cntl[x]--,res-=cntr[x];}
void remr(int x){cntr[x]--,res-=cntl[x];}
inline int read()
{
    char x=getchar();int t=0;
    while(!isdigit(x))x=getchar();
    while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
    return t;
}
int main()
{
    a=read();len=pow(a,0.5);
    for(int i=1;i<=a;++i)num[i]=read();
    b=read();
    for(int i=1;i<=b;++i)
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        ask[++tot]={y1,y2,i,1};
        ask[++tot]={x1-1,x2-1,i,1};
        ask[++tot]={x1-1,y2,i,-1};
        ask[++tot]={y1,x2-1,i,-1};
    }
    for(int i=1;i<=tot;++i)
        if(ls(i)>rs(i))swap(ls(i),rs(i));
    //for(int i=1;i<=a;++i)printf("[%d,%d],%d(%d)\n",ls(i),rs(i),lct(i),op(i));
    sort(ask+1,ask+tot+1,cmp);
    int l=0,r=-1;
    for(int i=1;i<=tot;++i)
    {
        while(l>ls(i))addl(num[l--]);
        while(r<rs(i))addr(num[++r]);
        while(l<ls(i))reml(num[++l]);
        while(r>rs(i))remr(num[r--]);
        //cout<<res;
        ans[lct(i)]-=op(i)*res;
    }
    for(int i=1;i<=b;++i)cout<<ans[i]<<endl;
}

如题，对着样例和 hack 调居然过了。

主要是在存 ans 的时候不是很理解，为什么正着存会存出来负数？

明明我赋的正负关系看起来都是没问题的。