LuoguP5268「SNOI2017」题解

发表于 更新于

对式子进行简化然后莫队

Description

维护一个长度为 $N$的序列$a_n$, $q$次询问，求

$$\sum_{x = 0} ^ \infty {\rm get} (l_1, r_1, x) \times {\rm get} (l_2, r_2, x)$$

${\rm get} (l, r, x)$ 表示区间 $[l,r]$ 中 $x$ 的出现次数。

$n, q \leq 5 \times 10^4$.

Samples

Input #1

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

Output #1

1
2
4
1

Solution

容易发现, 题目中给的式子并不好求, 那么考虑我们在学习前缀和求区间和的时候用到的技巧

首先, 显然:
$${\rm get} (l, r, x) = {\rm get} (1, r, x) - {\rm get} (1, l - 1, x)$$

那么我们把原式子拆开:

$$\text{设} g(r, x) = {\rm get} (1, r, x)$$

$$\text {原式} = \sum_{x = 0} ^ \infty \left[ g(r_1, x) g(r_2, x) - g(r_1, x) g(l_2 - 1, x) - g(r_2, x)g(l_2 - 1, x) + g(l_1 - 1, x) g(l_2 - 1, x)\right]$$

一种理解方式就是$(A - C) (B - D) = AB - BC - AD + CD$

这样我们就可以把询问拆成了四个部分:

$$q_1 = \sum_{x = 0} ^ \infty g(r_1, x) g(r_2, x)$$
$$q_2 = \sum_{x = 0} ^ \infty g(r_1, x) g(l_2 - 1, x)$$
$$q_3 = \sum_{x = 0} ^ \infty g(r_2, x) g(l_1 - 1, x)$$
$$q_4 = \sum_{x = 0} ^ \infty g(l_1 - 1, x) g(l_2 - 1, x)$$

那么最终答案就是$q_1 - q_2 - q_3 + q_4$, 这样直接莫队做就好了.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* Headers */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <stack>
#include <map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define RevEdge(x) x^1
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE], *is = ibuf, *its = ibuf;
    char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE;
    inline char getch() {
        if(is == its)
            its = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
        return (is == its) ? EOF : *is++;
    }
    inline int getint() {
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-') {neg = 1;ch = getch();}
        while(isdigit(ch)) {
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg ? -res : res;
    }
    inline void flush(){
        fwrite(obuf, 1, os - obuf, stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot) flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--) putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 5e4 + 10;
int a[MAXN], n, block, cntl[MAXN], cntr[MAXN];
int m, ans[MAXN], ql, qr, now, tot;
struct Query {
    int l, r, type, ser;
    bool operator < (const Query x) {
        return l / block == x.l / block ? r / block < x.r / block : l / block < x.l / block;
    }
} q[MAXN << 2];
/* functions */
inline void ADD(int pos, int type) {
    now += (type == 1) ? cntl[a[pos]] : cntr[a[pos]];
    (type == 1) ? cntr[a[pos]]++ : cntl[a[pos]]++;
}
inline void DEL(int pos, int type) {
    now -= (type == 1) ? cntl[a[pos]] : cntr[a[pos]];
    (type == 1) ? cntr[a[pos]]-- : cntl[a[pos]]--;
}
int main(int argc, char *argv[]) {
    //FILE_IN("data.in");
    scanf("%d", &n); block = std::sqrt(n);
    FOR(i, 1, n, 1) scanf("%d", &a[i]);
    scanf("%d", &m);
    FOR(i, 1, m, 1) {
        int l1, r1, l2, r2;
        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
        q[(i - 1) << 2] = (Query) {r1, r2, 1, i};
        q[(i - 1) << 2 | 1] = (Query) {l2 - 1, r1, -1, i};
        q[(i - 1) << 2 | 2] = (Query) {l1 - 1, r2, -1, i};
        q[(i - 1) << 2 | 3] = (Query) {l1 - 1, l2 - 1, 1, i};
    }
    std::sort(q + 1, q + (m << 2));
    FOR(i, 0, (m << 2) - 1, 1) {
        if(q[i].l < 1 || q[i].r < 1) continue;
        int L = q[i].l, R = q[i].r;
        while(ql < L) ADD(++ql, 0);
        while(qr < R) ADD(++qr, 1);
        while(ql > L) DEL(ql--, 0);
        while(qr > R) DEL(qr--, 1);
        ans[q[i].ser] += now * q[i].type;
    } FOR(i, 1, m, 1) printf("%d\n", ans[i]);
    return 0;
}

THE END