gym-101138D(后缀和,莫队算法,容斥原理,好题)

You are given an array with n integers a1, a2, ..., an, and q queries to answer.

Each query consists of four integers l1, r1, l2 and r2. Your task is to count the number of pairs of indices (i, j) satisfying the following conditions:

The first line of the input contains an integer n (1 ≤ n ≤ 50 000) — the size of the given array.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n).

The third line contains an integer q (1 ≤ q ≤ 50 000) — the number of queries.

Each of the next q lines contains four integers l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n), describing one query.

For each query count the number of sought pairs of indices (i, j) and PRint it in a separate line.

71 5 2 1 7 2 281 3 4 52 3 5 71 4 3 72 6 4 71 6 2 53 3 6 74 5 1 42 3 4 5output
12566220
题意简明。
题解：
使用莫队算法
假设当前左右指针分别为l和r，一共n个数
对于指针l,维护一个后缀[l,n],算这个后缀每个数出现次数。
对于指针r,维护一个后缀(r,n]算这个后缀每个数出现次数。
对区间[l,r)维护[l,n]和[r,n]中相等的数的对数。
假设区间[l,r)的答案为f(l,r).
那么，对于询问l1,r1,l2,r2, 答案是f(l1,l2)-f(l1,r2+1)-f(r1+1,l2)+f(r1+1,r2+1).
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>#include<cmath>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=50000+100;int unit;struct node{    int l,r,id,k;    bool Operator <(const node&b) const{        if(l/unit==b.l/unit) return r<b.r;        else return l/unit<b.l/unit;    }    node(int x=0,int y=0):l(x),r(y) {}}a[maxn*4];int m=0,n;ll ans[maxn];int num[maxn];ll cnt[2][maxn];ll res;void solve(){    sort(a,a+m);    memset(cnt,0,sizeof(cnt));    memset(ans,0,sizeof(ans));    int l=n+1,r=n+1;   //    res=0;    rep(i,0,m)    {        while(l<a[i].l)        {            res-=1ll*cnt[0][num[l]]*cnt[1][num[l]];            cnt[0][num[l]]--;            res+=1ll*cnt[0][num[l]]*cnt[1][num[l]];            l++;        }        while(l>a[i].l)        {            l--;            res-=1ll*cnt[0][num[l]]*cnt[1][num[l]];            cnt[0][num[l]]++;            res+=1ll*cnt[0][num[l]]*cnt[1][num[l]];        }        while(r<a[i].r)        {            res-=1ll*cnt[1][num[r]]*cnt[0][num[r]];            cnt[1][num[r]]--;            res+=1ll*cnt[1][num[r]]*cnt[0][num[r]];            r++;        }        while(r>a[i].r)        {            r--;            res-=1ll*cnt[1][num[r]]*cnt[0][num[r]];            cnt[1][num[r]]++;            res+=1ll*cnt[1][num[r]]*cnt[0][num[r]];        }        ans[a[i].id]+=a[i].k*res;    }}int main(){    scanf("%d",&n);    unit=(int)sqrt(n);    rep(i,1,n+1) scanf("%d",&num[i]);    int q;    scanf("%d",&q);    rep(i,0,q)    {        int l1,r1,l2,r2;        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);        r1++,r2++;        a[m]=node(l1,l2),a[m].id=i,a[m].k=1;        a[++m]=node(l1,r2),a[m].id=i,a[m].k=-1;        a[++m]=node(r1,l2),a[m].id=i,a[m].k=-1;        a[++m]=node(r1,r2),a[m].id=i,a[m].k=1;        m++;    }    solve();    rep(i,0,q)    printf("%lld/n",ans[i]);    return 0;}