水题记录1.1

8/15

水题记录1.1

1.NOI.AC 模拟赛R3 T1 列队

题目大意 : 给你一个\(n \times m\)的矩阵\((n, m \le 10^3)\), 每次询问有多少个人在\(TA\)那一排是第\(x\)高, 在\(TA\)那一列是第\(y\)

题解 :

考虑到\(n, m\)都很小, 直接暴力把所有的情况都处理, 怎么搞呢?

对于每一个人在\(TA\)那一行二分一下, 那一列二分一下然后统计一下答案

复杂度\(O((nm)log(nm) + q)\)

代码 :

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 5;

int n, m, q, a[maxn][maxn], ans[maxn][maxn];
vector<int> X[maxn], Y[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
n = read(); m = read(); q = read();

for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= m; j++) {
a[i][j] = read();
X[i].push_back(a[i][j]);
Y[j].push_back(a[i][j]);
}

for(register int i = 1; i <= n; i++)
sort(X[i].begin(), X[i].end());
for(register int i = 1; i <= m; i++)
sort(Y[i].begin(), Y[i].end());

for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= m; j++) {
int posx = lower_bound(X[i].begin(), X[i].end(), a[i][j]) - X[i].begin() + 1;
int posy = lower_bound(Y[j].begin(), Y[j].end(), a[i][j]) - Y[j].begin() + 1;
ans[posx][posy]++;
}

for(register int i = 1; i <= q; i++) {
int x = read(), y = read();
printf("%d\n", ans[m - x + 1][n - y + 1]);
}
return 0;
}
/*
3 3 2
1 8 9
3 2 7
6 5 4
3 3
2 2

3 3 2
1 2 7
6 4 5
8 3 9
3 2
2 3

*/

2.NOI.AC 模拟赛R3 T2 染色

题目大意 : 现在有\(n\)个位置, \(m\)种颜色, 要求给\(n\)个位置染色, 要求求出满足任意一个长度为\(m\)子区间的颜色种类小于\(m\)的方案数

题解 : 设状态\(f[i][j]\)表示前\(i\)个位置, 后\(j\)个位置有\(j\)种颜色, 后\(j+1\)个位置也有\(j\)种颜色的方案数, 有转移 \[ f[i][j] += \begin{cases} f[i - 1][j - 1] \cdot (m - j + 1) \ \ \ \ if(j < m)\\ \sum_{v = j}^m f[i - 1][v]\end{cases} \] 就是如果颜色种类小于\(m\), 你可以在第\(i\)个位置上随便放上\(m - j + 1\)中的一种颜色

也可以从上个状态后缀颜色数大于\(j\)的任意一种状态转移过来, 如图 :

然后如果你直接暴力转移复杂度是\(O(n m^2)\)的, 考虑直接用后缀和维护一下复杂度便变成了\(O(nm)\), 可以通过此题

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 5e3 + 5;

int n, m, P, f[maxn][maxn], s[maxn], ans;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}
inline int mul(int x, int y) {LL rnt = 1ll * x * y; return (int)(rnt >= P ? rnt % P : rnt);}

int main() {
n = read(); m = read(); P = read();

f[1][1] = m;
for(register int i = 2; i <= n; i++) {
for(register int j = 1; j < m; j++)
f[i][j] = pls(f[i][j], mul(f[i - 1][j - 1], m - j + 1));
for(register int j = m; j >= 1; j--) s[j] = pls(f[i - 1][j], s[j + 1]);
for(register int j = 1; j <= m; j++) f[i][j] = pls(f[i][j], s[j]);
}

for(register int i = 1; i <= m; i++) ans = pls(ans, f[n][i]);
cout << ans;
return 0;
}
/*

*/

3.NOI.AC 模拟赛R3 T3 游戏

题目大意 : 你一开始有\(n\)个角色, 每个角色的初始经验为\(0\), 初始等级为\(0\), 现在有一个序列\(a\)(保证\(a\)递增), 定义每个角色的等级为满足\(当前经验 \ge a_i\)的最大的\(i\), (保证序列\(a\)的长度\(m\)小于等于\(10\))?

然后有三个操作 :

  1. 给区间\([l, r]\)中的角色的经验都加上\(x\)
  2. 将某一个角色的经验改为\(x\)
  3. 查询区间\([l, r]\)中所有角色的等级和

题解 : 前两个操作线段树都可以很好的解决, 但是该如何解决升级的问题呢?

  1. 对于第一个操作, 我们定义对于第\(i\)个玩家升级到下一个等级所需的经验为\(p_i\), 然后我们维护一个区间中\(p_i\)的最小值, 如果当前区间中\(p_i\)的最小值小于加上的经验\(x\), 我们直接在线段树上暴力改, 因为最多只有\(m\)级, 所以一个角色最多被改\(m\)次, 复杂度没有问题
  2. 对于第二个操作, 直接暴力修改, 复杂度\(O(m \cdot logn)\), 注意有可能修改的值比当前经验值还要小
  3. 直接线段树查询\(O(logn)\)

最终复杂度\(O(m \cdot nlogn)\)

代码 :

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
#include <bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;
const LL inf = 1ll << 60;

int n, m, q;
LL a[15];

struct Segment {
struct node {int s; LL minv, tag;} t[maxn << 2];

inline int pushup(int p) {
t[p].s = t[ls].s + t[rs].s;
t[p].minv = min(t[ls].minv, t[rs].minv);
}

inline void pushdown(int p) {
if(t[p].tag == 0) return;
int o = t[p].tag;
t[ls].minv -= o; t[ls].tag += o;
t[rs].minv -= o; t[rs].tag += o;
t[p].tag = 0;
}

inline void modifyz(int l, int r, int pos, int p, int x) {
if(l == r) {
t[p].s = 0; t[p].minv = a[1];
while(x >= t[p].minv) {
x -= t[p].minv; t[p].s++;
t[p].minv = a[t[p].s + 1] - a[t[p].s];
} t[p].minv -= x; return;
} pushdown(p);
if(pos <= mid) modifyz(l, mid, pos, ls, x);
else modifyz(mid + 1, r, pos, rs, x);
pushup(p);
}

inline void modifyp(int l, int r, int p, int x) {
if(t[p].minv > x) {
t[p].tag += x; t[p].minv -= x; return;
}
if(l == r) {
while(x >= t[p].minv) {
x -= t[p].minv; t[p].s++;
t[p].minv = a[t[p].s + 1] - a[t[p].s];
} t[p].minv -= x; return;
}
pushdown(p);
modifyp(l, mid, ls, x); modifyp(mid + 1, r, rs, x);
pushup(p);
}

inline void modify(int l, int r, int ql, int qr, int p, int x) {
if(l == ql && r == qr) return modifyp(l, r, p, x);
pushdown(p);
if(qr <= mid) modify(l, mid, ql, qr, ls, x);
else if(ql > mid) modify(mid + 1, r, ql, qr, rs, x);
else modify(l, mid, ql, mid, ls, x), modify(mid + 1, r, mid + 1, qr, rs, x);
pushup(p);
}

inline int query(int l, int r, int ql, int qr, int p) {
if(l == ql && r == qr) return t[p].s;
if(qr <= mid) return query(l, mid, ql, qr, ls);
else if(ql > mid) return query(mid + 1, r, ql, qr, rs);
else return query(l, mid, ql, mid, ls) + query(mid + 1, r, mid + 1, qr, rs);
}
} T;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
n = read(); m = read(); q = read(); a[m + 1] = inf;

for(register int i = 0; i < (n << 2); i++) T.t[i].minv = inf;
for(register int i = 1; i <= m; i++) a[i] = read();
for(register int i = 1; i <= n; i++) T.modifyz(1, n, i, 1, read());

while(q--) {
int opt = read(), l = read(), r = read();
if(opt == 1) T.modify(1, n, l, r, 1, read());
else if(opt == 2) T.modifyz(1, n, l, 1, r);
else printf("%d\n", T.query(1, n, l, r, 1));
}
return 0;
}

4.NOI.AC 模拟赛R5 T1 count

题目大意 : 长度为\(n+1\)的序列\(A\),其中的每个数都是不大于\(n\)的正整数,且\(n\)以内每个正整数至少出现一次。

对于每一个正整数\(k=1,..,n+1\),求出的本质不同的长度为\(k\)的子序列(不一定要连续)的数量。对\(10^9+7\)取模。

题解 : 我们先找出两个相同的数\(x\)的位置为\(p1, p2\), 定义\(Z = min(p1, p2) - 1, Q = n + 1 - max(p1, p2)\)

如图 :

如果不考虑重复答案就是\(\binom{n + 1}{i}\), 我们再考虑一下如何计算出重复的子序列

考虑对于一个\(k\), \(x\)可以是子序列第\(i\)\((1 \le i \le k)\)

重复的串的个数就是在前\(Z\)个选\(i - 1\)个的方案数乘上在后\(Q\)个选\(k - i\)的方案数, 然后答案就是下面那个式子 \[ \binom{n + 1}{k} - \sum_{i = 1}^{k} \binom{Z}{i - 1} \cdot \binom{Q}{k - i} \] 然后用一下恒等式 \[ \binom{n + 1}{k} - \binom {Z + Q}{k - 1} \] 就水完了

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;
const int P = 1e9 + 7;

int n, a[maxn], vis[maxn], rfac[maxn << 1], fac[maxn << 1];
int p[2], Z, Q;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}
inline int mul(int x, int y) {LL rnt = 1ll * x * y; return (int)(rnt >= P ? rnt % P : rnt);}
inline int dec(int x, int y) {x -= y; return x < 0 ? x + P : x;}

inline int ksm(int x, int k) {
int cnt = 1;
while(k) {
if(k & 1) cnt = mul(cnt, x);
x = mul(x, x); k >>= 1;
} return cnt;
}

inline int C(int n, int m) {
if(m > n) return 0;
return mul(fac[n], mul(ksm(fac[m], P - 2), ksm(fac[n - m], P - 2)));
}

int main() {
//freopen("count2.in", "r", stdin);
//freopen("count.out", "w", stdout);

n = read(); fac[0] = 1;

for(register int i = 1; i <= n + 1; i++) vis[a[i] = read()]++;

for(register int i = 1; i <= n + 1; i++)
if(vis[a[i]] > 1) p[(p[0] <= 0) ^ 1] = i;
Z = min(p[0], p[1]) - 1; Q = n + 1 - max(p[0], p[1]);

for(register int i = 1; i < maxn * 2; i++)
fac[i] = mul(fac[i - 1], i);

//cerr << Z << " " << Q << endl;

for(register int i = 1; i <= n + 1; i++) {
int ans = C(n + 1, i);
ans = dec(ans, C(Z + Q, i - 1));
printf("%d\n", ans);
}
return 0;
}

5.NOI.AC 模拟赛R5 T2 delete

题目大意 : 长度为\(n\)的序列\(A\),从中删去恰好\(k\)个元素(右边的元素往左边移动),记\(cnt\)为新序列中\(A_i=i\)的元素个数(即权值与下标相同的元素的个数)。求\(cnt\)的最大值。

题解 :

二维\(dp\)很显然, 当然也没有什么优化的余地

尝试转化成一维\(dp\), 设\(f[i]\)表示使得\(A_i = i\)的最大\(cnt\), 设\(p_i = i - A_i\)表示使这个数满足条件时, 这之前要删多少数

转移好想 \[ f[i] = max\{f[j] + 1, j < i, p[i] \ge p[j], i - j - 1 \ge p[i] - p[j]\} \] 等价于 \[ f[i] = max\{f[j] + 1, j < i, p[i] \ge p[j], a[i] > a[i]\} \]

很显然这个一个三维偏序问题, 但是如果直接搞三维偏序复杂度为\(O(nlog^2n)\), 尝试转化为二维偏序

我们可以发现当\(p[i] \ge p[j]\)\(a[i] > a[j]\)之后, \(i\)一定大于\(j\)

所以\(i > j\)这个条件可以直接丢掉, 然后随便怎么搞一搞二维偏序就好了

代码 :

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
#include <bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)

using namespace std;

typedef long long LL;

const int maxn = 1e6 + 5;
const int inf = 1e9 + 7;

int f[maxn], k, n, a[maxn], p[maxn], ans, M, id[maxn];

struct Segment {
int maxv[maxn << 2];

inline void insert(int l, int r, int pos, int p, int x) {
if(l == r) {maxv[p] = max(maxv[p], x); return;}
if(pos <= mid) insert(l, mid, pos, ls, x);
else insert(mid + 1, r, pos, rs, x);
maxv[p] = max(maxv[ls], maxv[rs]);
}

inline int query(int l, int r, int ql, int qr, int p) {
if(ql > qr) return 0;
if(l == ql && r == qr) return maxv[p];
if(qr <= mid) return query(l, mid, ql, qr, ls);
else if(ql > mid) return query(mid + 1, r, ql, qr, rs);
else return max(query(l, mid, ql, mid, ls), query(mid + 1, r, mid + 1, qr, rs));
}
}T;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline bool cmp(int x, int y) {return p[x] < p[y] || (p[x] == p[y] && a[x] < a[y]);}

int main() {
// 60pts

//freopen("delete.in", "r", stdin);
//freopen("count.out", "w", stdout);

//for(register int i = 0; i < maxn * 4; i++) T.maxv[i] = 0;

n = read(); k = read();

for(register int i = 1; i <= n; i++) {
a[i] = read(); id[i] = i;
if(i - a[i] >= 0) p[i] = i - a[i];
else p[i] = -inf;
}

//cerr << f[0] << endl;

sort(id + 1, id + 1 + n, cmp);

for(register int i = 1; i <= n; i++) {
int t = id[i];

if(p[t] == -inf || n - t < k - p[t] || p[t] > k) continue;

/*for(register int j = 0; j < i; j++)
if(a[t] > a[id[j]]) {
f[t] = max(f[t], f[id[j]] + 1);
}*/

//int p0 = 1;

int p0 = T.query(1, n, 1, a[t] - 1, 1) + 1;

T.insert(1, n, a[t], 1, f[t] = p0);

ans = max(ans, f[t]);
}

//for(register int i = 1; i <= n; i++)
// cout << f[i] << " ";

//cout << endl;

cout << ans;
return 0;
}

6.NOI.AC 模拟赛R4 T1 子图

题目大意 : 求最小生成树

题解 : 同题目大意

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 5e5 + 5;

int n, m, fa[maxn];

LL ans;

struct Graph {int x, y, w;} e[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int findx(int x) {return fa[x] == x ? fa[x] : fa[x] = findx(fa[x]);}

inline bool cmp(Graph x, Graph y) {return x.w > y.w;}

int main() {
n = read(); m = read();

for(register int i = 1; i <= n; i++) fa[i] = i;

for(register int i = 1; i <= m; i++) {
int x = read(), y = read(), w = read();
e[i] = (Graph){x, y, w};
}

sort(e + 1, e + 1 + m, cmp);

for(register int i = 1; i <= m; i++) {
int x = e[i].x, y = e[i].y, w = e[i].w;
int rtx = findx(x), rty = findx(y);
if(rtx == rty) {ans += w; continue;}
fa[rtx] = rty;
}
cout << ans;
return 0;
}

7.NOI.AC 模拟赛R6 T1 queen

题目大意 : 在一个\(n \times n\)的棋盘上,放有\(m\)个皇后,其中每一个皇后都可以向上、下、左、右、左上、左下、右上、右下这\(8\)个方向移动(就是可以沿对角线和水平竖直方向移动)。其中每一个皇后可以攻击这八个方向上离它最近的皇后。

我们现在考虑每一个皇后会被从几个方向攻击到,设为\(w\)。很显然\(w\)属于\([0,8]\)。最后要求出来\(t[0],t[1]……t[8]\)九个数,表示有多少皇后被攻击到\(0次,1次……8次\)。 数据保证\(m\)个皇后中任意两个不在同一个位置。

题解 : 对于每一个皇后分别加入到其对应的四条直线里去(斜向下, 斜向上, 竖直, 水平)

然后判断它是不是每条直线中最左或最右的那个点, 如果在最中间的话肯定会被两边的攻击到, 所以这样就很好统计答案了

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;

int n, m, x[maxn], y[maxn], t[10];
vector<int> X[maxn], Y[maxn], Up[maxn * 2], Down[maxn * 2];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
n = read(); m = read();

for(register int i = 1; i <= m; i++) {
x[i] = read(); y[i] = read();
X[x[i]].push_back(y[i]);
Y[y[i]].push_back(x[i]);
Up[y[i] - x[i] + n].push_back(x[i]);
Down[y[i] + x[i]].push_back(x[i]);
}

for(register int i = 1; i <= n; i++) {
sort(X[i].begin(), X[i].end());
sort(Y[i].begin(), Y[i].end());
}

for(register int i = 0; i <= n * 2; i++) {
sort(Up[i].begin(), Up[i].end());
sort(Down[i].begin(), Down[i].end());
}

for(register int i = 1; i <= m; i++) {
vector<int> :: iterator B, E; int tim = 0;
B = X[x[i]].begin(); E = X[x[i]].end(); E--;
tim += (y[i] > *B) + (y[i] < *E);

B = Y[y[i]].begin(), E = Y[y[i]].end(); E--;
tim += (x[i] > *B) + (x[i] < *E);

B = Up[y[i] - x[i] + n].begin(), E = Up[y[i] - x[i] + n].end(); E--;
tim += (x[i] > *B) + (x[i] < *E);

B = Down[x[i] + y[i]].begin(), E = Down[x[i] + y[i]].end(); E--;
tim += (x[i] > *B) + (x[i] < *E);

t[tim]++;
}

for(register int i = 0; i < 9; i++) cout << t[i] << " ";
return 0;
}

8.NOI.AC 模拟赛R6 T3 color

题目大意 : 给定一串\(n\)个珠子,其中每一个珠子的颜色为\(a_i\),总共有\(k\)类颜色珠子标号从\(1\)\(k\)

初始给定一个参数\(T\)。询问再给定\(m\)个区间\(l_i\)\(r_i\),每次询问这个区间有多少颜色的珠子出现了恰好\(T\)次。

\(n , m \le 5 \cdot 10^5\)

题解 : 正解不会

然后由于数据很水直接暴力莫队即可

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 5e5 + 5;
const int LOG = 30;

int n, m, k, T, ans[maxn], be[maxn], L, R, curAns, tim[maxn], col[maxn], unit;

struct Query {int l, r, id;} t[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline bool cmp(Query x, Query y){return be[x.l] == be[y.l] ? (be[x.l] & 1 ? x.r < y.r : x.r > y.r) : be[x.l] < be[y.l];}

inline void add(int pos) {
tim[col[pos]]++;
if(tim[col[pos]] == T) curAns++;
else if(tim[col[pos]] == T + 1) curAns--;
}

inline void del(int pos) {
tim[col[pos]]--;
if(tim[col[pos]] == T) curAns++;
else if(tim[col[pos]] == T - 1) curAns--;
}

int main() {
n = read(); m = read(); k = read(); T = read(); unit = sqrt(n);

for(register int i = 1; i <= n; i++) {
col[i] = read();
be[i] = (i - 1) / unit + 1;
}

for(register int i = 1; i <= m; i++) {
int l = read(), r = read();
t[i] = (Query) {l, r, i};
}
sort(t + 1, t + 1 + m, cmp);

L = 0, R = 1;
for(register int i = 1; i <= m; i++) {
while(R < t[i].r)R++, add(R);
while(R > t[i].r)del(R), R--;
while(L < t[i].l)del(L), L++;
while(L > t[i].l)L--, add(L);
ans[t[i].id] = curAns;
}

for(register int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}

咕咕咕