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
題意簡明。
題解：
使用莫隊(duì)算法
假設(shè)當(dāng)前左右指針分別為l和r，一共n個數(shù)
對于指針l,維護(hù)一個后綴[l,n],算這個后綴每個數(shù)出現(xiàn)次數(shù)。
對于指針r,維護(hù)一個后綴(r,n]算這個后綴每個數(shù)出現(xiàn)次數(shù)。
對區(qū)間[l,r)維護(hù)[l,n]和[r,n]中相等的數(shù)的對數(shù)。
假設(shè)區(qū)間[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;}