题面：[AHOI2013] 作业
题目描述
此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。
这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 $n$ 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 $l$ 个数到第 $r$ 个数)，首先你要统计该区间内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数。
小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。
输入格式
第一行两个整数 $n,m$
接下来 $n$ 个不超过 $10^5$ 的正整数表示数列
接下来 $m$ 行，每行四个整数 $l,r,a,b$，具体含义参见题意。
输出格式
输出 $m$ 行，分别对应每个询问，输出两个数，分别为在 $l$ 到 $r$ 这段区间中大小在 $[a,b]$ 中的数的个数，以及大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数（具体可以参考样例）。
样例 #1
样例输入 #1
1
2
3
4
5
6
| 3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3
|
样例输出 #1
提示
$N\leq 100000,M\leq 100000$，读入的数字均为 $[1,10^5]$ 内的正整数。
思路
这次的询问比较有意思，我们如何处理可以在 $O(n\sqrt n)$ 的复杂度内搞定呢？（虽然说多一个log应该问题不大）
这次要查询的是两个区间的内容，且一个要求查询这个区间内在一个数值范围内的数字个数，让人莫名想到权值线段树……但是这样的话，复杂度就会多出来一个 log ，而且还是大常数的 log 这题只有 1s 时限完全吃不消。这就让人莫名想到，有什么 $O(1)$ 单点修改，但是查询我们没有时间要求（当然也是 $O(\sqrt n)$ 以内）的数据结构呢？你别说，还真有，不难想到莫队的亲戚分块，既然有权值线段树，为什么我们不可以做一个权值分块呢？并且这样的复杂度单点修改仍然没有问题，查询的时候有 $O(\sqrt n)$ 的时间复杂度对于我们来说完全足够！
接下来就要看看第二个询问，不难发现其实也是可以用分块敲定的，那么这题的代码也不难构想，其实就是扩大区间的时候用分块单点修，查询的时候 $O(\sqrt n)$ 直接处理出两个答案，总时间复杂度 $O(n\sqrt n)$ 非常完美。
代码
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 1e5 + 10;
const int BN = 316;
int n, Q;
int a[N];
int pos[N];
struct Qiz {
int l, r, a, b, id;
inline bool operator < (const Qiz & x) const {
if(pos[l] != pos[x.l]) return l < x.l;
return r < x.r;
}
}qs[N];
int B, res[N][2], cnt[N];
int ds[N], base[N], tot[N];
inline void Input() {
read(n, Q);
for(int i = 1; i <= n; i++) {
read(a[i]);
}
for(int i = 1; i <= Q; i++) {
read(qs[i].l, qs[i].r, qs[i].a, qs[i].b);
qs[i].id = i;
}
}
inline void Upd(int x, int f) {
x = a[x];
ds[x / BN] += f, base[x] += f;
cnt[x] += f;
if(cnt[x] == 1 && f == 1) tot[x / BN]++;
else if(cnt[x] == 0 && f == -1) tot[x / BN]--;
}
inline void Calc(int l, int r, int id) {
int idl = l / BN, idr = r / BN;
if(idl == idr) {
for(int i = l; i <= r; i++) {
if(base[i]) res[id][0] += base[i], res[id][1]++;
}
}
else {
for(int i = l; i < (idl + 1) * BN; i++) {
if(base[i]) res[id][0] += base[i], res[id][1]++;
}
for(int i = idl + 1; i < idr; i++) {
if(ds[i]) res[id][0] += ds[i], res[id][1] += tot[i];
}
for(int i = idr * BN; i <= r; i++) {
if(base[i]) res[id][0] += base[i], res[id][1]++;
}
}
}
inline void Work() {
B = sqrt(n);
for(int i = 1; i <= n; i++) pos[i] = i / B;
sort(qs + 1, qs + Q + 1);
int l = 1, r = 0;
for(int i = 1; i <= Q; i++) {
while(l > qs[i].l) Upd(--l, +1);
while(r < qs[i].r) Upd(++r, +1);
while(l < qs[i].l) Upd(l++, -1);
while(r > qs[i].r) Upd(r--, -1);
Calc(qs[i].a, qs[i].b, qs[i].id);
}
for(int i = 1; i <= Q; i++) {
printf("%d %d\n", res[i][0], res[i][1]);
}
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
