P5268 一个简单的询问（莫队+容斥）

Description

State

Input

Output

Solution

Code

Description

给你一个长度为 $N$ 的序列 $a_i$，$1\le i\le N$，和 $q$ 组询问，每组询问读入 $l_1,r_1,l_2,r_2$，需输出

$$\sum _{x=0}^{\mathrm{\infty }}\text{get}(l_1,r_1,x)\times \text{get}(l_2,r_2,x)$$

$\text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中，数字 $x$ 出现了多少次。

State

\(n,m<=50000\)

\(1<=a[i]<=n\)

Input

5
1 1 1 1 1
2
1 2 3 4
1 1 4 4

Output

4
1

Solution

题目 \(r_1,l_2\) 的大小并不明确，需要另一种新颖的容斥方法

另 \([l,r]\) 为区间内 \(x\) 的个数，\(x\) 任意

之后 \([l1,r1]*[l2,r2]\) 可以转化为

\[[1,r1]*[1,r2]-[1,r1]*[1,l2-1]-[1,r2]*[1,l1-1]+[1,l1-1]*[1,l2-1] \]

每一个区间的左端点都为 \(1\)，所以可以将一个区间分为 \(4\) 个不同的区间，而他们的左端点都为 \(1\)；

也就是说对于每一个端点 \(l,r\) 对于 \(1\) 来说，都是右端点

\(hint:\) 区间大小是题目所给的 \(4\) 倍

Code

const int N = 5e4 * 4 + 5;
 
    int n, m;
    int a[N];
    struct Query
    {
        int l, r;
        int bel;
        int id, tag;
        bool operator<(Query o){
            return bel == o.bel ? r < o.r: l < o.l;
        }
        Query(int l = 0, int r = 0, int id = 0, int tag = 0, int bel = 0) : l(l), r(r), bel(bel), id(id), tag(tag){}
    }q[N];
    int block, pre[N], suf[N];
    int tot = 0;
    ll ans[N], now;

void add(int pos, int *on, int *nxt)
{
    int x = a[pos];
    now += nxt[x];
    on[x] ++;
}

void del(int pos, int *on, int *nxt)
{
    int x = a[pos];
    now -= nxt[x];
    on[x] --;
}

void mo()
{
    block = 3 * sqrt(n);
    for(int i = 1; i <= tot; i ++){
        if(q[i].l > q[i].r) swap(q[i].l, q[i].r);
        q[i].bel = q[i].l / block + 1;
    }
    sort(q + 1, q + 1 + tot);
}

signed main()
{
    while(~ sd(n)){
        rep(i, 1, n) sd(a[i]);
        sd(m);
        rep(i, 1, m){
            int x, y, nx, ny;
            sdd(x, y); sdd(nx, ny);
            q[++ tot] = Query(y, ny, i, 1);
            q[++ tot] = Query(x - 1, ny, i, -1);
            q[++ tot] = Query(nx - 1, y, i, -1);
            q[++ tot] = Query(x - 1, nx - 1, i, 1);
        }
        mo();
        int l = 0, r = 0;
        now = 0;
        for(int i = 1; i <= tot; i ++){
            while(l < q[i].l) add(++ l, pre, suf);
            while(l > q[i].l) del(l --, pre, suf);
            while(r < q[i].r) add(++ r, suf, pre);
            while(r > q[i].r) del(r --, suf, pre);
            ans[q[i].id] += now * q[i].tag;
        }
        rep(i, 1, m) pll(ans[i]);
    }
    return 0;
}