显然这个询问并不简单
如果做过莫比乌斯反演入门题problem b就会想到利用容斥将询问拆成四个
那么我们现在的问题变成如何求
[1,l]
[1,r]
两个区间之间的答案，那么也是直接用莫队即可，只是维护的是两个区间的右端点，和原来的莫队有一些不一样，但是大体相同。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
const int N=5e4+5;
int S;
struct node{
int l,r,id,op;
bool operator < (const node&x) const {
if (l/S != x.l/S) return l<x.l;
return (l/S)&1 ? r<x.r : r>x.r;
}
};
node q[N*8];
int c[N],n,m,tot,l,r;
ll a[N],b[N],sum,ans[N];
void add1(int x){
sum+=b[x];
a[x]++;
}
void add2(int x){
sum+=a[x];
b[x]++;
}
void sub1(int x){
sum-=b[x];
a[x]--;
}
void sub2(int x){
sum-=a[x];
b[x]--;
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d",&n);
fo(i,1,n) scanf("%d",&c[i]);
S=(int)pow(n,0.5);
scanf("%d",&m);
fo(p,1,m) {
int x,y,z,w;
scanf("%d %d %d %d",&x,&y, &z,&w);
q[++tot]=(node){y,w,p,1};
if ((x-1)>0) q[++tot]=(node){x-1,w,p,-1};
if ((z-1)>0) q[++tot]=(node){y,z-1,p,-1};
if ((x-1)>0 && (z-1)>0) q[++tot]=(node){x-1,z-1,p,1};
}
fo(i,1,tot) if (q[i].l>q[i].r) swap(q[i].l, q[i].r);
sort(q+1,q+tot+1);
// fo(i,1,tot) {
// printf("%d %d %d %d\n",q[i].l,q[i].r, q[i].id, q[i].op);
// }
l=0; r=0;
while (l<q[1].l) ++a[c[++l]];
while (r<q[1].r) {
sum+=a[c[++r]];
b[c[r]]++;
}
ans[q[1].id]+=(ll)q[1].op*sum;
fo(i,2,tot) {
while (l>q[i].l) sub1(c[l--]);
while (r<q[i].r) add2(c[++r]);
while (l<q[i].l) add1(c[++l]);
while (r>q[i].r) sub2(c[r--]);
ans[q[i].id]+=(ll)q[i].op*sum;
// printf("%lld\n",sum);
}
fo(i,1,m) printf("%lld\n",ans[i]);
return 0;
}