原题呈现

数组询问#

题目描述#

有一个由 $n$ 个整数组成的数组，你需要回答一些关于这个数组的询问．

输入格式#

第一行输入两个整数 $n, Q$ ，表示数组长度和询问次数．

第二行输入 $n$ 个整数 $a_1 \sim a_n$ ，表示数组中的数字．

接下来 $Q$ 行，每行输入两个整数 $opt, x$ ，表示一次询问：

如果 $opt=1$ ，表示询问数组中 $> x$ 数字的数量．
如果 $opt=2$ ，表示询问数组中字典序 $> x$ 数字的数量．
如果 $opt=3$ ，表示询问数组中 $> x$ ，且字典序也 $> x$ 数字的数量．

其中“字典序比较”指把整数当成十进制字符串比较．例如：

$123 < 9$ ，因为字典序先比较首字符， $1 < 9$ ．
$870 > 8099$ ，因为首位同为 $8$ ，第二位 $7 > 0$ ．
$12 < 123$ ，如果一个字符串是另一个字符串的真前缀，那么长度更长的字符串字典序更大．

输出格式#

对于每次询问输出一行一个整数，表示答案．

样例#

输入 #1#

1
8 5
2
9 88 777 6666 55555 114514 321 1234
3
1 222
4
2 222
5
3 222
6
1 114514
7
2 114514

输出 #1#

数据范围#

本题采用捆绑评测，对于一个子任务，你必须通过其中的所有数据才能得到相应分数．

子任务编号	分数	$n, Q$	$a_i, x$	特殊性质
1	25	$\le 5000$	$< 10^9$	无
2	10	$\le 10^5$	$10^9$	无
3	10	$\le 3\times10^5$	$< 100$	无
4	10	$\le 3\times10^5$	$< 10^6$	无
5	10	$\le 3\times10^5$	$\ge 10^8$	无
6	10	$\le 3\times10^5$	$10^9$	$opt=1$
7	10	$\le 3\times10^5$	$10^9$	$opt=2$
8	15	$\le 3\times10^5$	$10^9$	无

全部数据范围#

$1 \le n, Q \le 3\times10^5$
$1 \le a_i, x < 10^9$
$opt \in \{1, 2, 3\}$

显然，对于操作 1，只要将数组排序，然后使用 lower_bound 进行查询，复杂度 $O(n\log n)$ ．对于操作 2，只要将数组按字典序排序，然后使用字典序的 lower_bound 进行查询，复杂度 $O(n\log n)$ ．

重点看操作 3．如果将所有的数字按数学顺序排序，每一个值 $a_i$ 得到一个排名 $\operatorname{rkv}{a_i}$ ，再按字典序排序，所有数字又得到一个排名 $\operatorname{rkd}{a_i}$ ，那么，原问题转换为，对于给定值 $x$ ，查找所有的 $i$ 满足 $\operatorname{rkv}{a_i} > \operatorname{rkv}{x}$ 且 $\operatorname{rkd}{a_i} > \operatorname{rkd}{x}$ ．满足条件的所有方案数可以使用容斥，即所有的 $n$ 个点，减去所有 $\operatorname{rkv}{a_i} \leq \operatorname{rkv}{x}$ 的点（设为 $A_1$ ），减去所有 $\operatorname{rkd}{a_i} \leq \operatorname{rkd}{x}$ 的点（设为 $A_2$ ），再加上被重复减去的的 $\operatorname{rkv}{a_i} \leq \operatorname{rkv}{x}$ 且 $\operatorname{rkd}{a_i} \leq \operatorname{rkd}{x}$ 的点（设为 $B_{12}$ ）， $A_1$ 可以使用 n 减去操作 1 的结果， $A_2$ 可以使用 n 减去操作 2 的结果，而求解 $B_{12}$ 问题为二维偏序．

具体的，将所有操作中的参数 $x_i$ 离线，并将这些参数依照上面的标准获得两个排名 $\operatorname{rkd}{x_i}$ 和 $\operatorname{rkv}{x_i}$ （由于 $x_i$ 不参与排序，于是这个排名就相当于所有小于 $x_i$ 的数的数量 +1），将所有 $a_i$ 和 $x_i$ 的两个排名视作一个二维平面上的两个坐标，于是所有 $a_i$ 和 $x_i$ 就可以视作 1 个点．

此时参数 $x_i$ 对应询问的答案即为以 $x_i$ 为右下角，原点为左上角的矩形内，原始点的数量．将所有点按照横坐标排序（相同则原始点排在查询点之前），这样就省去了一维，只需考虑纵坐标的大小．依照排序顺序从小到大进行遍历，遍历到每一个点：

若该点为原始点：将该点的纵坐标加入树状数组．
若该点为查询点：查询树状数组中处于 1 和该点纵坐标之间的区间和，该和即为该查询的答案．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int N = 3e5 + 100;
5
int n, Q, a[N], b[N], rkv[N], rkd[N], opt[N], x[N], ans[N], lenV, lenD;
6

7
// 按字典序排序的结构体
8
struct DictInt {
9
    int v, id;
10
    friend bool operator<(const DictInt x, const DictInt y) {
11
        int vx = x.v, vy = y.v, size1 = 0, size2 = 0;
12
        int ka[20], kb[20];
13
        while (vx > 0) {
14
            int xx = vx % 10;
15
            ka[++size1] = xx;
16
            vx /= 10;
17
        }
18
        while (vy > 0) {
19
            int yy = vy % 10;
20
            kb[++size2] = yy;
21
            vy /= 10;
22
        }
23
        for (int i = 1; i <= min(size1, size2); i++) {
24
            int ptr1 = size1 - i + 1, ptr2 = size2 - i + 1;
25
            if (ka[ptr1] < kb[ptr2])
26
                return true;
27
            if (ka[ptr1] > kb[ptr2])
28
                return false;
29
        }
30
        return size1 < size2;
31
    }
32
} d[N];
33

34
int calLessV(int x) { return upper_bound(b + 1, b + lenV + 1, x) - b - 1; }
35

36
int calLessD(int x) {
37
    DictInt di;
38
    di.v = x;
39
    di.id = 0;
40
    return upper_bound(d + 1, d + lenD + 1, di) - d - 1;
41
}
42

43
// 树状数组
44
struct BIT {
45
    int f[N];
46
    int size;
47
    BIT() {}
48
    void init(int size) { this->size = size; }
49
    int lowbit(int x) { return x & (-x); }
50
    void upd(int p, int v) {
51
        for (int i = p; i <= size; i += lowbit(i)) {
52
            f[i] += v;
53
        }
54
    }
55
    int qry(int p) {
56
        int ans = 0;
57
        for (int i = p; i >= 1; i -= lowbit(i)) {
58
            ans += f[i];
59
        }
60
        return ans;
61
    }
62
    int qry(int l, int r) { return qry(r) - qry(l - 1); }
63
} bit;
64

65
struct Point {
66
    int x, y, qid;
67
    friend bool operator<(const Point a, const Point b) {
68
        if (a.x == b.x) {
69
            if (a.qid == -1 && b.qid == -1) {
70
                return a.y < b.y;
71
            }
72
            if (a.qid == -1)
73
                return true;
74
            if (b.qid == -1)
75
                return false;
76
            return a.y < b.y;
77
        }
78
        return a.x < b.x;
79
    }
80
};
81
vector<Point> pt;
82

83
signed main() {
84
#ifdef ONLINE_JUDGE
85
    freopen("dichrome.in", "r", stdin);
86
    freopen("dichrome.out", "w", stdout);
87
#endif
88
    ios::sync_with_stdio(false);
89
    cin.tie(0);
90
    cout.tie(0);
91
    cin >> n >> Q;
92
    for (int i = 1; i <= n; i++) {
93
        int x;
94
        cin >> x;
95
        d[i] = {x, i};
96
        a[i] = x;
97
        b[i] = x;
98
    }
99
    sort(b + 1, b + n + 1);
100
    lenV = n;
101
    for (int i = 1; i <= n; i++) {
102
        rkv[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
103
    }
104
    sort(d + 1, d + n + 1);
105
    lenD = n;
106
    for (int i = 1; i <= n; i++) {
107
        DictInt di = {a[i], i};
108
        rkd[i] = lower_bound(d + 1, d + n + 1, di) - d;
109
        pt.push_back({rkv[i], rkd[i], -1});
110
    }
111

112
    for (int i = 1; i <= Q; i++) {
113
        int op, xx;
114
        cin >> op >> xx;
115
        opt[i] = op;
116
        x[i] = xx;
117
        if (op == 3) {
118
            pt.push_back({calLessV(x[i]), calLessD(x[i]), i});
119
        }
120
    }
121

122
    sort(pt.begin(), pt.end());
123

124
    bit.init(n);
125
    for (int i = 0; i < pt.size(); i++) {
126
        if (pt[i].qid == -1) {
127
            bit.upd(pt[i].y, 1);
128
        } else {
129
            ans[pt[i].qid] = bit.qry(pt[i].y);
130
        }
131
    }
132

133
    for (int i = 1; i <= Q; i++) {
134
        if (opt[i] == 1) {
135
            ans[i] = n - calLessV(x[i]);
136
        }
137
        if (opt[i] == 2) {
138
            ans[i] = n - calLessD(x[i]);
139
        }
140
        if (opt[i] == 3) {
141
            ans[i] = n - calLessD(x[i]) - calLessV(x[i]) + ans[i];
142
        }
143
        cout << ans[i] << endl;
144
    }
145
    return 0;
146
}

音乐

音乐

数组询问#

题目描述#

输入格式#

输出格式#

样例#

输入 #1#

输出 #1#

数据范围#

全部数据范围#

文章分享

音乐

安吉D6-T1

数组询问#

题目描述#

输入格式#

输出格式#

样例#

输入 #1#

输出 #1#

数据范围#

全部数据范围#

文章分享