题目
思路
\(ans=\sum_{x=0}^{\infty}get(l1,r1,x)*get(l2,r2,x)\)
设\(f(l,x)\)为从1~l的x的出现次数
\(ans=\sum_{x=0}^{\infty}(f(r1,x)-f(l1-1,x))*(f(r2,x)-f(l2-1,x))\)
\(ans=\sum_{x=0}^{\infty}f(r1,x)*f(r2,x)-f(r1,x)*f(l2-1,x)-f(l-1,x)*f(r2,x)+f(l1-1,x)*f(l2-1,x)\)
之后暴力莫队做就行了
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
void read(int &x)
{
x=0;
int f=1;
char c=getchar();
while('0'>c||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
x*=f;
}
void write(int x)
{
if(x<10)
putchar(x+'0');
else
{
write(x/10);
putchar(x%10+'0');
}
}
int n;
int cnt;
int l;
int r;
int q;
long long ans;
int t1[50005];
int t2[50005];
int a[50005];
map<int,long long> t[50005];
struct node
{
int l1;
int r1;
int l2;
int r2;
}b[50005];
struct node_solve
{
int l;
int r;
friend bool operator < (const node_solve &a,const node_solve &b)
{
if(a.l/cnt==b.l/cnt)
return a.r<b.r;
else
return a.l<b.l;
}
};
vector<node_solve> v;
int main()
{
read(n);
cnt=sqrt(n);
for(int i=1;i<=n;i++)
read(a[i]);
read(q);
for(int i=1;i<=q;i++)
{
read(b[i].l1);
read(b[i].r1);
read(b[i].l2);
read(b[i].r2);
v.push_back((node_solve){b[i].r1,b[i].r2});
v.push_back((node_solve){b[i].l1-1,b[i].r2});
v.push_back((node_solve){b[i].l1-1,b[i].l2-1});
v.push_back((node_solve){b[i].l2-1,b[i].r1});
}
sort(v.begin(),v.end());
l=r=0;
for(int i=0;i<v.size();i++)
{
node_solve u=v[i];
if(u.l<1||u.r<1)
continue;
while(l<u.l)
{
ans+=t2[a[++l]];
t1[a[l]]++;
}
while(r<u.r)
{
ans+=t1[a[++r]];
t2[a[r]]++;
}
while(l>u.l)
{
ans-=t2[a[l]];
t1[a[l--]]--;
}
while(r>u.r)
{
ans-=t1[a[r]];
t2[a[r--]]--;
}
t[u.l][u.r]=ans;
}
for(int i=1;i<=q;i++)
{
cout<<(t[b[i].r1][b[i].r2]-t[b[i].l1-1][b[i].r2]-t[b[i].l2-1][b[i].r1]+t[b[i].l1-1][b[i].l2-1]);
putchar('\n');
}
return 0;
}