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);
}
}
}
|