https://acm.uestc.edu.cn/problem/fang-chai
（请先看 n题）
这题也是一道线段树的题目，题目中的方差可以拆成和、平方和两个数据来维护，这样合并就很方便。而数据变化有加、乘、抹平两种操作。根据乘法的分配率等定理，多次加乘最后可以化简为一次乘和一次加，为避免出现分数，整合为先乘后加比较方便。而抹平操作则可理解为乘 0再加。这样则有两个标记。这题与 n题相比最关键的区别在于，该题先乘后加的二项式操作不具有结合律，须在更新下层元素之前 pushdown。
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1000000007;
inline ll M(ll n) { return (n + mod) % mod; }
int num[100000];
ll ans_sum, ans_s2;
struct tnode {//对节点需要赋初值、更新值、清除标记合并等操作，其中平方和的更新比 n题稍复杂，还有乘标记的默认值为 1，标记的合并也值得注意。
int l, r;
ll sum, s2, mark1 = 1, mark2 = 0;
inline tnode() {}
inline tnode(int l, int r) {
this->l = l, this->r = r;
if (l == r) {
this->sum = num[l - 1];
this->s2 = M(this->sum * this->sum);
}
}
void change(int multipie, int add) {
this->s2 = M(M(this->s2 * M((ll)multipie * multipie)) +
2 * M(M((ll)add * multipie) * this->sum) +
M(M((ll)add * add) * this->len()));
this->sum = M(this->sum * multipie + (ll)add * this->len());
this->mark1 = M(this->mark1 * multipie);
this->mark2 = M(this->mark2 * multipie + add);
}
inline void markdel() {
this->mark1 = 1;
this->mark2 = 0;
}
inline int mid() { return (this->l + this->r) >> 1; }
inline void merge(tnode lc, tnode rc) {
this->sum = M(lc.sum + rc.sum);
this->s2 = M(lc.s2 + rc.s2);
}
inline int len() { return r - l + 1; }
};
tnode node[400000];
void buildtree(int l, int r, int pos = 1) {//由于特殊点都写进了成员函数，后面按标准的线段树写就好
tnode &n = node[pos];
n = tnode(l, r);
if (l == r) return;
int lc = pos << 1, rc = pos << 1 | 1;
buildtree(l, n.mid(), lc);
buildtree(n.mid() + 1, r, rc);
n.merge(node[lc], node[rc]);
}
inline void pushdown(int pos) {
tnode &n = node[pos];
node[pos << 1].change(n.mark1, n.mark2);
node[pos << 1 | 1].change(n.mark1, n.mark2);
n.markdel();
}
void query(int l, int r, int pos = 1) {
tnode &n = node[pos];
if (l > n.r || r < n.l) return;
if (l <= n.l && r >= n.r) {
ans_sum = M(ans_sum + n.sum);
ans_s2 = M(ans_s2 + n.s2);
} else {
if (n.mark1 != 1 || n.mark2 != 0) pushdown(pos);
query(l, r, pos << 1);
query(l, r, pos << 1 | 1);
}
}
void update(int op, int l, int r, int k, int pos = 1) {
tnode &n = node[pos];
if (l > n.r || r < n.l) return;
if (l <= n.l && r >= n.r) switch (op) {//三种操作，加可以认为是先乘 1，乘可以认为加 0，抹平则是先乘 0
case 1:
n.change(1, k);
break;
case 2:
n.change(k, 0);
break;
case 3:
n.change(0, k);
}
else {
int lc = pos << 1, rc = pos << 1 | 1;
pushdown(pos);//更新子节点前先处理标记
update(op, l, r, k, lc);
update(op, l, r, k, rc);
n.merge(node[lc], node[rc]);
}
}
int main() {
int n, q;
scanf("%d%d", &n, &q);
for (int i = 0; i < n; ++i) scanf("%d", num + i);
buildtree(1, n);
while (q--) {
int op;
int l, r;
scanf("%d%d%d", &op, &l, &r);
if (op == 4) {
ans_sum = ans_s2 = 0;
query(l, r);
printf("%lld\n", M(ans_s2 * (r - l + 1) - M(ans_sum * ans_sum)));
} else {
int k;
scanf("%d", &k);
update(op, l, r, k);
}
}
}
|
https://acm.uestc.edu.cn/problem/tun-tu-liang
这是一道典型的 LCA，另外建树部分使用邻接表（邻接矩阵内存爆炸，边读边建树想了很久也没想到可行方法）。查阅一些资料后，本来对 Tarjan 比较有想法，但是写代码的时候出了一些问题，后来就去写倍增了。
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
int num, l;
};
list<edge> path[100001];
int dep[100001], U[100001][18], L[100001][18];
void buildtree(int pos = 1) {//根节点为 1，从根开始对每个节点遍历相邻的边，遇到未加入树的就添加，并且递归操作。遍历结束后 clear()释放无用内存
for (edge p : path[pos])
if (!U[p.num][0]) {
U[p.num][0] = pos;
dep[p.num] = dep[pos] + 1;
L[p.num][0] = p.l;
buildtree(p.num);
}
path[pos].clear();
}
int find(int u, int v) {//核心思路就是类似于二分的方法，通过指数的变化逼近取值，将复杂度降到 O(logn)
if (u == v) return 0;
int ans = INT_MAX;
if (dep[u] < dep[v]) swap(u, v);
while (dep[u] - dep[v] > 1) {//把两者的深度调至相同，由于有已知的深度差，通过对数计算确定跳的步数，理论上效率应该比像后面那样从最大值开始循环略高
int lo = log(dep[u] - dep[v]) / log(2);
ans = min(ans, L[u][lo]), u = U[u][lo];
}
if (dep[u] != dep[v]) ans = min(ans, L[u][0]), u = U[u][0];
if (u == v) return ans;
for (int i = 17; i >= 0; --i) {//目标深度未知，只能循环判断了
if (i && U[u][i] == U[v][i]) {
continue;
}
ans = min(ans, min(L[u][i], L[v][i]));
u = U[u][i], v = U[v][i];
}
if (u == v) return ans;
return min(ans, min(L[u][0], L[v][0]));
}
int main() {
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i < n; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
path[u].push_back({v, w});
path[v].push_back({u, w});
}
U[1][0] = 1;//建树前用邻接表添加边，并把根节点 1加入树，
buildtree();
for (int i = 1; 1 << i < n; ++i)//递推预处理
for (int j = 1; j <= n; ++j)
U[j][i] = U[U[j][i - 1]]
[i - 1],
L[j][i] = min(L[j][i - 1], L[U[j][i - 1]]
[i - 1]);
while (q--) {
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", find(u, v));
}
}
|
https://acm.uestc.edu.cn/problem/ren-zai-di-shang-zou-guo-cong-tian-shang-lai
这道题处理一条线段上面联通块的个数，并且是动态的。我们可以把各个联通块按顺序排列起来，这样查找更新都比较方便，而 set 容器很好地提供了排列和去重的功能，优先队列虽然效率不错但不提供删除功能。
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
|
#include <bits/stdc++.h>
using namespace std;
struct guo {//每个黑锅的左右端点作为一个节点
int l, r;
guo(int l, int r) { this->l = l, this->r = r; }
bool operator<(guo ans) const { return this->r < ans.l; }//不加 const 过不了编译，重载运算符。当 a<b、b<a 均为假时，系统会认为 a==b，因此只需重载一个比较运算符。
};
inline guo merge(guo a, guo b) { return guo(min(a.l, b.l), max(a.r, b.r)); }//合并两个黑锅
int main() {
int n;
scanf("%d", &n);
set<guo> a;
while (n--) {
int l, r;
scanf("%d%d", &l, &r);
guo hei = guo(l, r);
auto it = a.find(hei);
while (it != a.end()) {//找到所有和新的黑锅联通的黑锅，合并，删除
hei = merge(hei, *it);
a.erase(it);
it = a.find(hei);
}
a.insert(hei);
printf("%lu", a.size());
if (n) putchar(' ');
}
}
|
https://acm.uestc.edu.cn/problem/mi-ma-1
这是我做的最憋屈的一题，因为k==0的情况WA了十多次。。。好在最后善良的出题人在note里给了提示。
首先这题中要求输出各元素的相对位置不变，这符合队列的性质，而同时又要求代表的十六进制值最大，所以使用单调队列来解决这个问题。我在找到WA的原因之前，想了很久，改了不少次，折腾了很久。好像也可以线段树，就是会多个log，也应该不会卡。
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
|
#include <deque>
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n, k;
while (cin >> n >> k) {
deque<char> nums;
char tmp;
if (!k) {//k 为0 时直接读完输入进入下一组数据，最后 AC 的关键，其实 getline 可能更好，但是影响很小，所以不重交了
while (n--) cin >> tmp;
//这里有无 cout<<endl;均可
continue;
}
cin >> tmp;
nums.push_front(tmp);
for (int i = 0; i < n - k; ++i) {//前半部分直接按单调队列的规则来
cin >> tmp;
while (!nums.empty() && nums.front() < tmp) nums.pop_front();
nums.push_front(tmp);
}
for (int i = 1; i < k; ++i) {//后半部分一边读取新元素，一边输出并删除最优元素，可确保个数足够。把两个循环拆开，常数应该比循环内加判断小 1（其实是因为我之前写错误代码的时候拆了，然后就不想改了）
cout << nums.back();
cin >> tmp;
nums.pop_back();
while (!nums.empty() && nums.front() < tmp) nums.pop_front();
};
cout << nums.back() << endl;//第二个循环少输出了一个字符，现在补上，导致 k为 0时也会输出一个字符，从而 WA
}
}
|
https://acm.uestc.edu.cn/problem/dong-ma-he-sha-tian-xia-di-yi/description
首先，任意个不同的数都可以构成一个单调序列，因此，这题实际上是要求区间中出现最多的数出现的次数，即区间众数。区间众数是一个很经典的难题，常见的做法有分块、莫队（离线）等等。这道题要用上一个询问的答案来处理下一次询问，因此离线做法不可行。
不管是那种做法，我们首先都可以把数列离散化一下，然后考虑分块做法，把数列分为$\sqrt{n}$大小的块，然后我们可以求一个前缀和，即从第一块到每一块的每个元素的总出现次数，对每个块都暴力遍历一遍即可，$O(n\sqrt{n})$。然后再以块为单位枚举起点和终点，从第i块到第j块的区间众数要么是从第i块到第j-1块的众数，要么就是出现在第j块中的数，这样利用前缀和可以在$O(\sqrt{n})$内求出每两个块的值，这样复杂度为$O((\sqrt{n})^2 \sqrt{n})$预处理就结束了，然后查询就很方便，我们可以直接得到区间中整块部分的众数，再在两端的不完整的块中一个一个地暴力统计即可，复杂度也是$O(n\sqrt{n})$。
还有一些别的写法，比如预处理各块自己的众数，然后用n个vector存各点的出现位置，然后用lowerbound差分找答案，这种写法常数非常小，对于随机数据比较快，但是复杂度多了一个$O(log(众数出现次数))$，数据大量重复时就会很慢。
参考代码：
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
const int INF = 0x3f3f3f3f;
int n, m, Size;
int a[40001], pos[40001];
int sum[201][40001];
int res[201][201];
int S[201];
void init() {
int bs = n / Size;
FOR(i, 0, bs) {
S[i] = Size;
FOR(j, 0, Size * (i + 1))
++sum[i][a[j]];
}
if (n % Size) {
S[bs] = n % Size;
FOR(j, 0, n)
++sum[bs][a[j]];
}
FOR(i, 0, S[0])
res[0][0] = max(res[0][0], sum[0][a[i]]);
FOR(rblock, 1, bs) {
res[0][rblock] = res[0][rblock - 1];
FOR(i, rblock * Size, rblock * Size + S[rblock])
res[0][rblock] = max(res[0][rblock], sum[rblock][a[i]]);
}
FOR(lblock, 1, bs) FOR(rblock, lblock, bs) {
res[lblock][rblock] = res[lblock][rblock - 1];
FOR(i, rblock * Size, rblock * Size + S[rblock])
res[lblock][rblock] =
max(res[lblock][rblock], sum[rblock][a[i]] - sum[lblock - 1][a[i]]);
}
}
int in_int() {
char c = getchar();
int ans = 0;
while (c > '9' || c < '0') c = getchar();
while (c >= '0' && c <= '9') {
ans = (ans << 3) + (ans << 1) + c - '0';
c = getchar();
}
return ans;
}
int cnt[40001];
int query(int l, int r) {
RST(cnt);
int maxc = 0;
int lblock = l / Size, rblock = r / Size;
if (lblock == rblock) FOR(i, l, r + 1) {
++cnt[a[i]];
maxc = max(maxc, cnt[a[i]]);
}
else {
// if (l % Size == 0) --lblock;
// if ((r + 1) % Size == 0) ++rblock;
FOR(i, l, Size * (lblock + 1)) {
if (!cnt[a[i]]) cnt[a[i]] = sum[rblock - 1][a[i]] - sum[lblock][a[i]];
++cnt[a[i]];
maxc = max(maxc, cnt[a[i]]);
}
FOR(i, Size * rblock, r + 1) {
if (!cnt[a[i]]) cnt[a[i]] = sum[rblock - 1][a[i]] - sum[lblock][a[i]];
++cnt[a[i]];
maxc = max(maxc, cnt[a[i]]);
}
if (lblock + 1 < rblock) maxc = max(maxc, res[lblock + 1][rblock - 1]);
}
return maxc;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
n = in_int();
m = in_int();
Size = sqrt(n);
FOR(i, 0, n) a[i] = in_int();
memcpy(pos, a, sizeof(int) * n);
sort(pos, pos + n);
auto lst = unique(pos, pos + n);
FOR(i, 0, n) a[i] = lower_bound(pos, lst, a[i]) - pos;
init();
int result = 0;
FOR(i, 0, m) {
int l = in_int(), r = in_int();
l = (l + result - 1) % n;
r = (r + result - 1) % n;
if (l > r) swap(l, r);
printf("%d\n", result = query(l, r));
}
}
|
https://acm.uestc.edu.cn/problem/wo-yong-yuan-xi-huan-dong-ma-he-sha/description
这题在上题的基础上，可以使用离线算法，但是对复杂度、常数的要求都较高。上题的思路无法满足本题的要求，本题可以使用莫队算法来解决问题。我们已知一个区间的状态（各数出现的次数，众数出现的次数，以及出现次数为任意值的元素各有多少个），可以很快地得出其一个端点加一（或减一）后的状态，根据增加或减少的数维护上面三个变量都是$O(1)$的。然后我们就要考虑一个顺序，依次得到各个询问的区间结果，而且复杂度较低。如果简单地以主次关键字排序，次要的端点可能会反复来回长距离移动，复杂度最坏可到$O(n^2)$。这里我们可以对一个端点进行分块，同一块内的询问按另一个端点排序，这样该端点只会在$\sqrt{n}$范围内来回移动（跨块移动是单调的），另一个端点只会来回移动$\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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
const int INF = 0x3f3f3f3f;
int n, m, Size;
int a[200001], pos[200001];
int in_int() {
char c = getchar();
int ans = 0;
while (c > '9' || c < '0') c = getchar();
while (c >= '0' && c <= '9') {
ans = (ans << 3) + (ans << 1) + c - '0';
c = getchar();
}
return ans;
}
int pp = 0, result[200001];
struct Q {
int l, r, p, b;
void get() {
l = in_int() - 1;
r = in_int() - 1;
p = pp++;
b = l / Size;
}
bool operator<(const Q& x) {
return b ^ x.b ? b < x.b : b & 1 ? r > x.r : r < x.r;
}
} query[200001];
int cnt[200001], sum[200001], res = 0;
inline void addr(int& R) {
--sum[cnt[a[++R]]++];
++sum[cnt[a[R]]];
res = max(res, cnt[a[R]]);
}
inline void eraser(int& R) {
--sum[cnt[a[R]]];
if (cnt[a[R]] == res && !sum[cnt[a[R]]]) --res;
++sum[--cnt[a[R--]]];
}
inline void addl(int& L) {
--sum[cnt[a[--L]]++];
++sum[cnt[a[L]]];
res = max(res, cnt[a[L]]);
}
inline void erasel(int& L) {
--sum[cnt[a[L]]];
if (cnt[a[L]] == res && !sum[cnt[a[L]]]) --res;
++sum[--cnt[a[L++]]];
}
void solve() {
int L = 0, R = -1;
FOR(i, 0, m) {
auto& q = query[i];
while (R < q.r) addr(R);
while (L > q.l) addl(L);
while (R > q.r) eraser(R);
while (L < q.l) erasel(L);
result[q.p] = res;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
n = in_int();
m = in_int();
Size = sqrt(n);
FOR(i, 0, n) a[i] = in_int();
memcpy(pos, a, sizeof(int) * n);
sort(pos, pos + n);
auto lst = unique(pos, pos + n);
FOR(i, 0, n) a[i] = lower_bound(pos, lst, a[i]) - pos;
FOR(i, 0, m) query[i].get();
sort(query, query + m);
solve();
FOR(i, 0, m) printf("%d\n", result[i]);
}
|
：
https://acm.uestc.edu.cn/problem/pai-zhao
这题输入时进行一遍求和预处理，然后就可以直接做差得子序列和，也可以判断最优解也只需根据前缀和，可用单调队列的思想找最优解，线性复杂度内解决问题（这题时限应该是有意没卡暴力）。由于只需要一个最优值，所以可以直接把多余的值pop（stl的priority_queue无此功能），保持队列内元素的单调性，超出长度限制的元素也要pop掉。可以两端pop的容器有list和deque，本来当时想由于不需要随机访问，用链表应该比较好的，但是对比了一下时间就打脸了。
（注：该方法也可以求矩形范围的最值，对每行求一次，得到一个最值矩阵，再对其每列求一次即可，参考codeforces-1195E）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
scanf("%d%d", &n, &m);
long long sum[n + 1];
for (int i = 1; i <= n; ++i) {//初始化求和，保留 sum[0]，可以直接使用 sum[i]-sum[0]表示从第一个到第 i个的和，无需单独加代码
scanf("%lld", &sum[i]);
sum[i] += sum[i - 1];
}
deque<int> begin;
long long result = LLONG_MIN;
begin.push_front(0);
for (int i = 1; i <= n; ++i) {
int t = begin.size();//避免多次调用 begin.size()，讲道理 deque 的size()复杂度为 1，但是加了这句之后还是快了一丢丢
while ( --t && sum[begin.front()] > sum[i]) begin.pop_front();//排出 sum 值大的元素，至少保留一个元素
if (i - begin.back() > m) begin.pop_back();//如果长度超限，pop 末尾元素
long long dsum = sum[i] - sum[begin.back()];
if (dsum > result) result = dsum;//计算并更新最大值
if (sum[begin.front()] > sum[i]) begin.pop_front();//在之前保留的元素和 i之间选择下一步的最优解
begin.push_front(i);
}
printf("%lld\n", result);
}
|
https://acm.uestc.edu.cn/problem/pai-ming
这是一个动态计算排名的题。各队成绩放数组里就好，但是排名，在堆里面反复find队1肯定复杂度肯定是过大的。不过，好在我们只关心队1的名次，因此可以只排序成绩比队1好的队伍，不断增删维护，使的队1一直在排序的末尾，名次可直接用size读取。STL中multiset是最合适的容器，priority_queue虽然更快但是功能不足。
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;
using ll = long long;
struct T {//存储过题数与罚时，重载运算符以比较成绩
ll pe = 0;
int so = 0;
inline void add(int n) { ++this->so, this->pe += n; }
bool friend operator<(T a, T b) {
return a.so == b.so ? a.pe < b.pe : a.so > b.so;
}
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
T team[n + 1];
multiset<T> trank;
trank.insert(team[1]);//默认加入队 1
while (m--) {
int t, p;
scanf("%d%d", &t, &p);
T tmp = team[t];
team[t].add(p);
auto itend = trank.end();
if (t == 1) {
auto it = trank.lower_bound(team[t]);
do trank.erase(it++);
while (it != trank.end());//队 1名次上升后，删除后面的队伍
trank.insert(team[t]);
} else if (team[t] < team[1]) {
trank.insert(team[t]);
if (tmp < team[1]) {
trank.erase(trank.lower_bound(tmp));//删除过期的数据
}
}
printf("%lu\n", trank.size());
}
}
|
https://acm.uestc.edu.cn/problem/chong-hai-dai
这题是在一个环中取互不相邻的数，求其最大值。如果直接采用贪心的策略，取最大值a[tmp]后删除a[tmp]、a[a[tmp].l]和a[a[tmp].r]，则可能存在为了一个最大的元素放弃两个稍小元素的情况，并不能得到最优解。因此我们需要在贪心的过程中有“反悔”，选择之前元素的两个相邻元素的机会。因此，我们可以加入a[a[tmp].l].value+a[a[tmp].r].value-a[tmp].value，下一次选择该元素即相当于反悔选择a[tmp]，改为选择a[a[tmp].l]和a[a[tmp].r]，按这个策略贪心，取完m元素求和即可。找最大值可以使用priority_queue。
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
|
#include <bits/stdc++.h>
using namespace std;
const int visited = 10001;//取范围外的值作为已删去的标记
struct node {
int value, l, r;
node() {}
node(int value, int pos) {
this->value = value;
this->l = pos - 1, this->r = pos + 1;
}
};
struct q {
int value, pos;
bool operator<(q m) const { return this->value < m.value; }
};//数组存储各点的值和左右元素下标，队列存储值和对应的下标
int main() {
int m, n;
scanf("%d%d", &n, &m);
if (n < m * 2) {//为了取 m个不相邻元素，至少需要 2 * m 个元素
puts("Error!");
return 0;
}
node a[n];
priority_queue<q> pq;
for (int i = 0; i < n; ++i) {
int tmp;
scanf("%d", &tmp);
a[i] = node(tmp, i);
pq.push({tmp, i});
}
a[0].l = n - 1, a[n - 1].r = 0;
int ans = 0;
while (m--) {
q tmp;
do {
tmp = pq.top();
pq.pop();
} while (a[tmp.pos].value == visited);//在队列中跳过已删除的元素
ans += tmp.value;
tmp.value = a[tmp.pos].value =
a[a[tmp.pos].l].value + a[a[tmp.pos].r].value - a[tmp.pos].value;
pq.push(tmp);
a[a[tmp.pos].l].value = a[a[tmp.pos].r].value = visited;
a[tmp.pos].l = a[a[tmp.pos].l].l, a[tmp.pos].r = a[a[tmp.pos].r].r;
a[a[tmp.pos].l].r = a[a[tmp.pos].r].l = tmp.pos;//删除元素，调整相关元素的左右元素下标，形成新的环
}
printf("%d", ans);
}
|
https://acm.uestc.edu.cn/problem/dui-da-an
该题是在线地判断一些数之间的关系是否矛盾，判断条件为奇偶。每个数有两种可能，每行数据也对应两种可能。对此可以把每个数的两种可能作为两个点，显然该两点是矛盾的。然后根据每行数据成立的两种可能，对并查集进行两次连接操作，再检查矛盾的两点是否被连在同一个并查集中，如果在，则说明条件存在矛盾。
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
|
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
int fa[2 * maxn];
int dep[2 * maxn];
//简单的秩优化并查集
int find(int x) {
if (fa[x] == x)
return x;
return fa[x] = find(fa[x]);
}
void connect(int x, int y) {//函数名 union 被stdc++.h 占了。。
x = find(x), y = find(y);
if (dep[x] > dep[y])
fa[y] = x;
else {
fa[x] = y;
if (dep[x] == dep[y])
++dep[y];
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < 2 * maxn; ++i)//初始化父节点数组
fa[i] = i;
int i;
for (i = 0; i < m; ++i) {
int a, b;
char l[5];
scanf("%d%d%s", &a, &b, l);
if (*l == 'e') {//判断字符串，为偶说明相同，同侧相连即可，为奇则两侧交叉相连。
connect(a - 1, b);
connect(a - 1 + maxn, b + maxn);
if (find(a - 1) == find(a - 1 + maxn)) {
printf("%d", i);
return 0;
}
} else {
connect(a - 1, b + maxn);
connect(a - 1 + maxn, b);
if (find(a - 1) == find(a - 1 + maxn)) {
printf("%d", i);
return 0;
}
}
}
puts("ORZQHQH");
}
|
https://acm.uestc.edu.cn/problem/wo-de-ti-mian-zui-jian-dan-kuai-lai-zuo
这题是一道比较复杂的线段树题目。要求求最长等差数列的长度，既然是等差，我们就可以维护各数之间的差，这样询问区间l到r的最长等差序列长度，也就是询问l+1到r的最长等值序列长度+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
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
|
#include <bits/stdc++.h>
using namespace std;
struct tnode {//除了最长相等序列长度之外，还要保存节点两端的值以及两端的相等序列长度，以便在合并时判断两边的等值序列是否会相连形成更长的等值数列
int l, r, ll = 1, rl = 1, ml = 1;
long long lv = 0, rv = 0, mark=0;
inline tnode() {}
inline tnode(int l, int r) { this->l = l, this->r = r; }
inline void change(int add) {
this->lv += add;
this->rv += add;
this->mark += (long long)add;
}
inline void markdel() { this->mark = 0; }
inline int mid() { return (this->l + this->r) >> 1; }
void merge(tnode lc, tnode rc) {//关键步骤，要考虑各种情况，确保得到的各变量正确（除了 l=1 的节点的左端点，因为查询时找的是 l＋1 到r 的最长等值序列，不会涉及到该值）
this->lv = lc.lv, this->rv = rc.rv;
this->ll = lc.ll, this->rl = rc.rl;
this->ml = max(lc.ml, rc.ml);
if (lc.rv == rc.lv) {
if (this->ml < lc.rl + rc.ll) this->ml = lc.rl + rc.ll;
if (lc.len() == lc.ll) this->ll += rc.ll;
if (rc.len() == rc.rl) this->rl += lc.rl;
}
}
inline int len() { return r - l + 1; }
};
tnode node[400000];
tnode ans;
bool ans_add;
void buildtree(int l, int r, int pos = 1) {
tnode &n = node[pos];
n = tnode(l, r);
if (l == r) return;
int lc = pos << 1, rc = pos << 1 | 1;
buildtree(l, n.mid(), lc);
buildtree(n.mid() + 1, r, rc);
n.merge(node[lc], node[rc]);
}
inline void pushdown(int pos) {
tnode &n = node[pos];
node[pos << 1].change(n.mark);
node[pos << 1 | 1].change(n.mark);
n.markdel();
}
void query(int l, int r, int pos = 1) {
tnode &n = node[pos];
int lc = pos << 1, rc = pos << 1 | 1;
if (l > n.r || r < n.l) return;
if (l <= n.l && r >= n.r) {//递归查找过程中左边的点一定先被找到，所以可以把找到的第一个点存下来，后面找到的节点依次并上去，得到最终结果
if (ans_add)
ans.merge(ans, n);
else {
ans = n;
ans_add = 1;
}
} else {
if (n.mark) pushdown(pos);
query(l, r, pos << 1);
query(l, r, pos << 1 | 1);
}
}
void update(int l, int r, int add, int pos = 1) {
tnode &n = node[pos];
if (l > n.r || r < n.l) return;
if (l <= n.l && r >= n.r)
n.change(add);
else {
int lc = pos << 1, rc = pos << 1 | 1;
if (n.mark) pushdown(pos);
update(l, r, add, lc);
update(l, r, add, rc);
n.merge(node[lc], node[rc]);
}
}
int main() {
int n, q;
scanf("%d%d", &n, &q);
buildtree(1, n);
while (q--) {
int op;
int l, r;
scanf("%d%d%d", &op, &l, &r);
if (op) {
if (l == r) {
printf("1\n");
continue;
}
ans_add = 0;//重置标记
query(l + 1, r);
printf("%d\n", ans.ml + 1);
} else {//区间 l~r+1 会受到影响，各段受到的影响不同，为了方便，分多次调用 update
int a, k, p;
scanf("%d%d%d", &a, &k, &p);
update(l, l, a);
if (p > l) update(l + 1, p, k);
if (p < r) update(p + 1, r, -k);
update(r + 1, r + 1, -a - (2 * p - l - r) * k);
}
}
}
|
https://acm.uestc.edu.cn/problem/shu-li-tong-ji
这题是最基本的带标记线段树，基本的加法操作，维护和与最值（极差为最值之差）。由于基础比较差，之前对基本的树形结构都没有动手完整地写过，对递归和DFS的理解也不深。这次线段树写得非常难受。反复看过很多教程，又重新仔细看了一下基本的二叉树，踩了很多坑才动手把这题写出来。
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
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans_sum, ans_max, ans_min;
struct tnode {//对于节点的基本操作：初始化，更新，删除标记，合并等。出于方便还写了区间长度和中点。延迟更新标记是比较一个有些抽象的概念，但是在优化复杂度的过程中不可或缺，当操作施加于整个区间时，由于加法完全满足结合律，如果后面不会查询到其子区间，就不用把更新往下传，一组数据中往往大部分的节点更新都是可以不用传到底的。但是如果查询到子节点，就必须传递更新信息，否则结果将错误。于是在不知道是否会查询子节点的情况下，暂时先保存更新信息，后面查询的时候再按需传递更新
ll l, r, sum = 0, max = 0, min = 0, mark = 0;
inline tnode() {}
inline tnode(ll l, ll r) { this->l = l, this->r = r; }
inline tnode(ll sum, ll max, ll min) {
this->sum = sum, this->max = max, this->min = min;
}
inline void add(ll add) {
this->sum += add * (this->r - this->l + 1);
this->max += add;
this->min += add;
this->mark += add;
}
inline void markdel() { this->mark = 0; }
inline ll mid() { return (this->l + this->r) >> 1; }
inline void merge(tnode lc, tnode rc) {
this->sum = lc.sum + rc.sum + this->mark * (this->r - this->l + 1);
this->max = std::max<ll>(lc.max, rc.max) + this->mark;
this->min = std::min<ll>(lc.min, rc.min) + this->mark;
}
};
tnode node[4000000];
inline void buildtree(ll l, ll r, ll pos = 1) {//递归建树，以 1为根节点
tnode &n = node[pos];
n = tnode(l, r);
if (l == r) return;
ll lc = pos << 1, rc = pos << 1 | 1;
buildtree(l, n.mid(), lc);
buildtree(n.mid() + 1, r, rc);
}
inline void pushdown(ll pos) {//把当前节点的标记推送到下层节点，然后清除标记，在查询时调用
tnode &n = node[pos];
node[pos << 1].add(n.mark);
node[pos << 1 | 1].add(n.mark);
n.markdel();
}
void query(ll l, ll r, ll pos = 1) {//容易写错的一步。查询操作，从大区间逐层向下递归，最终得出结果
tnode &n = node[pos];
if (l > n.r || r < n.l) return;
if (l <= n.l && r >= n.r) {
ans_sum += n.sum;
ans_max = max<ll>(ans_max, n.max);
ans_min = min<ll>(ans_min, n.min);
} else {
if (n.mark) pushdown(pos);
query(l, r, pos << 1);
query(l, r, pos << 1 | 1);
}
}
void update(ll l, ll r, ll add, ll pos = 1) {//加法操作有结合律，更新时不需要 pushdown
tnode &n = node[pos];
if (l > n.r || r < n.l) return;
if (l <= n.l && r >= n.r)
n.add(add);
else {
ll lc = pos << 1, rc = pos << 1 | 1;
update(l, r, add, lc);
update(l, r, add, rc);
n.merge(node[lc], node[rc]);
}
}
int main() {
ll n, q;
scanf("%lld%lld", &n, &q);
buildtree(1, n);
while (q--) {
int op;
ll l, r;
scanf("%d%lld%lld", &op, &l, &r);
if (op == 1) {
ll k;
scanf("%lld", &k);
update(l, r, k);
} else {
ans_sum = 0;
ans_max = LLONG_MIN;
ans_min = LLONG_MAX;
query(l, r);
if (op == 2)
printf("%lld\n", ans_sum);
else
printf("%lld\n", ans_max - ans_min);
}
}
}
|
https://acm.uestc.edu.cn/problem/zhan-zheng
这是一个典型的用01字典树解决抑或最值问题的题目。我们把所需的数字的二进制从高到低位地保存在字典树中，查询最值的时候根据贪心思想，即可轻松地找到最值。01字典树可以是一棵二叉树，但是这样写要占用n个int的内存，超出了允许的范围，因此我们只添加存在的节点
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
|
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int poi[30 * MAXN], ch[30 * MAXN][2], co[30 * MAXN][2], num = 0;//按照最大需求量开数组，另开一个数组记录每个节点下数字的个数，还有一个数组记录最后的节点对应的整个数字（这个数组不要也行，可在查询函数中边查边算）
void insert(int x) {//插入数，从高到低
int u = 0;
for (int i = 29; i >= 0; --i) {
int tmp = x >> i & 1;
++co[u][tmp];
if (!ch[u][tmp]) {
ch[u][tmp] = ++num;
}
u = ch[u][tmp];
}
poi[u] = x;
}
void erase(int x) {//这里只操作记录个数的数组，并以该数组作为判断是否有数的依据
int u = 0;
for (int i = 29; i >= 0; --i) {
int tmp = x >> i & 1;
--co[u][tmp];
u = ch[u][tmp];
}
}
int find_max(int x) {//贪心，优先不同值
int u = 0;
for (int i = 29; i >= 0; --i) {
int tmp = x >> i & 1;
if (co[u][tmp ^ 1])
u = ch[u][tmp ^ 1];
else
u = ch[u][tmp];
}
return poi[u];
}
int find_min(int x) {//贪心，优先相同值
int u = 0;
for (int i = 29; i >= 0; --i) {
int tmp = x >> i & 1;
if (co[u][tmp])
u = ch[u][tmp];
else
u = ch[u][tmp ^ 1];
}
return poi[u];
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
int o, v;
scanf("%d%d", &o, &v);
switch (o) {
case 1:
insert(v);
break;
case 2:
erase(v);
break;
case 3:
printf("%d %d\n", find_min(v) ^ v, find_max(v) ^ v);
}
}
}
|