在WA了好多發之後，終于找到了我不小心寫錯的bug……我是SB
我的寫法與網絡上很多人的差異較大，但是個人覺得比其他人的更容易了解
第一次寫動态開點的線段樹，直接稍微改動了一下原本自己習慣的線段樹闆子，是以可能與其他闆子不同。
同時因為是改了線段樹的闆子，是以反而更容易看懂。
其次就是個人感覺我的寫法比題解要簡單很多，而且碼量很小
題意
對于一個可重複集合，進行Q次操作。集合起始的時候為空，操作類型如下
- 往集合中加入一個元素
- 從集合中删除一個元素（保證其存在）
- 給定一個元素 x x x ，問集合中是否存在另外兩個元素 a , b a, b a,b（允許值相同但是不允許元素相同），使得 a , b , x a, b, x a,b,x三條邊可以組成一個非退化三角形（即滿足任意兩邊之和大于第三邊，或任意兩邊之差小于第三邊）。
分析
分析三角形公式
首先根據公式 a + b > c a + b > c a+b>c 轉為 c − b < a c - b<a c−b<a （假定 a ≤ b ≤ c a \leq b \leq c a≤b≤c）
那麼我們可以得到，下面的結論：
假定存在 a ≤ b a \leq b a≤b 滿足 a , b , c a, b, c a,b,c 三邊能夠組成三角形，那麼對于 a ≤ a ′ ≤ b a \leq a' \leq b a≤a′≤b 必定存在 a ′ , b , c a', b, c a′,b,c 可以組成三角形（由 c − b < a ≤ a ′ c - b<a \leq a' c−b<a≤a′ 證得）
那麼我們可以指定如下規定：
- 對于輸入的 x x x ，我們找到兩條長度分别為 a , b a, b a,b 的邊，使得 a , b , x a, b, x a,b,x 能夠組成三角形，且不存在 a ′ a' a′ 滿足 a < a ′ ≤ b a < a' \leq b a<a′≤b，這裡我們暫時稱 a , b a, b a,b 相鄰（這點非常重要！！！）
即 a , b a, b a,b 在整個集合排序後，在數組中的下标差為 1 1 1
接下來考慮如何找到 a , b a, b a,b。題解中提到類似分類讨論，但是我覺得沒有必要。我們僅考慮通過 a , b a, b a,b 的運算後的結果與 x x x 來比較，最終得到我們的結果是否符合。
根據 a , b , x a, b, x a,b,x 的大小關系讨論三種情況：（前提 a ≤ b a \leq b a≤b）
- x x x 為最大值時，我們隻需要保證 a + b > x a + b > x a+b>x 即可
- a ≤ x ≤ b a \leq x \leq b a≤x≤b 時，我們需要保證 a + x > b a + x > b a+x>b ，轉換後得到 b − a < x b - a < x b−a<x
- x ≤ a ≤ b x \leq a \leq b x≤a≤b 時，我們需要保證 x + a > b x + a > b x+a>b ，轉換後得到 b − a < x b - a < x b−a<x
總結：我們隻需要保證我們選出來的 a , b a, b a,b 保證 a + b > x a n d b − a < x a + b > x \space and \space b - a < x a+b>x and b−a<x
由于 a ≤ b a \leq b a≤b 是以 b ≥ x / 2 b \geq x / 2 b≥x/2（請先記住這個結論，将會在之後用到）
接下來是解決 a + b a + b a+b 和 b − a b - a b−a 的資料存儲和更新問題（由于詢問是線上詢問，而 a , b a, b a,b 相鄰，是以随着插入新的資料，這兩個值都會發生變化）。
對于 a + b a + b a+b 的處理：
我們将所有目前在集合中的資料進行排序，可以使用
multiset
來實作，但是我個人不太喜歡
multi
的資料結構，是以我選擇了
map
，
first
儲存資料的值，
second
儲存了資料重複的個數。從此開始，我們暫時不讨論重複值的情況。
對于排序好的資料，我們可以通過二分數值來得到 x / 2 x / 2 x/2 在數組中的哪個位置。由于 a ≤ b a \leq b a≤b ，是以隻有兩種可能
- a < x / 2 a n d b > x / 2 a < x/2 \space and \space b > x / 2 a<x/2 and b>x/2
- a , b ≥ x / 2 a, b \geq x / 2 a,b≥x/2
後者很好解決，隻需要取值的時候，數組下标大于 x / 2 x/2 x/2 所在的下标位置即可
而前者因為 a , b a, b a,b 相鄰，是以我們可以使用
upper_bound
輕松解決（
b = *map.upper_bound(x / 2), a = *(map.upper_bound(x / 2) - 1)
）
至此，在保證資料有序的情況下，我們已經第一步縮小了資料範圍，得到了一個數組下标範圍
[map.upper_bound(x / 2), map.end()]
。注意，這裡的右區間始終為最大值（ I N F INF INF）
對于 b − a b - a b−a 的處理
由于求算 b − a b - a b−a 的過程本身需要排序，而上面對 a + b a + b a+b 的處理的時候已經排完序了。是以我們能夠較快的得到 b − a b - a b−a 的值（ a , b a, b a,b 相鄰）但是此時的更新的操作過于複雜，而且我們并不需要知道哪個區間的值能夠滿足條件（即小于 x x x ），我們可以隻需要知道我們已經縮小後的區間内，是否存在 a , b a, b a,b 滿足 b − a < x b - a < x b−a<x，即 m i n ( b − a ) < x min(b - a) < x min(b−a)<x。
區間最小值，單點更新，此時我們想到了線段樹（主要是我不知道有沒有動态樹狀數組這個感覺不太可能存在的東西，于是就寫了線段樹，實際上需要将線段樹的空間動态化，不然空間會爆炸）。
對于整個集合，假如有 n n n 個不同的元素，則隻會産生 n − 1 n - 1 n−1 個不同的插值（由于 a , b a, b a,b 相鄰，每個元素隻會産生一個，假定最後一個元素不産生）
那麼我們建立一棵長度為 1 e 9 1e9 1e9 的線段樹，對于每個不同的值（x），将其産生的內插補點儲存在節點 x − x x -x x−x 下，其他沒有值的節點，則保持 I N F INF INF
舉一個例子，假如我們有如下值在集合中
1, 3, 4, 10, 123, 423
則此時得到的內插補點為
2, 1, 6, 113, 300
則我們對如下數組
a
建立線段樹
a[1] = 2;
a[3] = 1;
a[4] = 6;
a[10] = 113;
a[123] = 300;
由于輸入的 1 ≤ x ≤ 1 e 9 1 \leq x \leq 1e9 1≤x≤1e9，是以我們開不起這麼大的線段樹，而實際上最多隻會有 1 e 5 1e5 1e5 個葉子節點，是以線段樹最多的節點個數為 1 e 5 l g 1 e 5 < 1 e 7 1e5 \space lg 1e5 < 1e7 1e5 lg1e5<1e7，是以隻需要準備 1 e 7 1e7 1e7 個節點，然後動态開點即可滿足整個線段樹的需要。
至于這裡為什麼選擇将每個內插補點産生的較小者（即 a a a ）作為下标的存儲位置。由于之後會遇到前面 a + b a + b a+b 得到的區間恰好從 a , b a, b a,b 中間穿過，如果儲存的是在 b b b 下，則會出現 a + b < x a + b < x a+b<x 但是仍然被選出來作為 m i n ( b − a ) min(b - a) min(b−a)。
接下來是線段樹的更新操作。
插入
由于值儲存在較小值處，是以需要更新較小值的值，和目前新插入的節點的下的值
删除
由于删除操作難以實作，不如直接把被删除的點的值設定為 I N F INF INF，以及，被删掉的點前面一個點的值需要更新
注意一下各種邊界情況。
查詢的操作
首先從已經排序好的數組中，得到 x / 2 x / 2 x/2 所在數組中的區間，然後拿着這個區間去找線段樹，詢問區間最小值，将最小值與 x x x 比較，如果最小值比 x x x 小，則輸出
Yes
，否則輸出
No
處理重複的資料
這裡就相當簡單了，對于相同的資料，隻需要保證 a + a > x a + a > x a+a>x 即可滿足 a , a , x a, a, x a,a,x 能夠組成三角形。我選擇再建立了一個
set
将所有滿足個數大于等于 2 2 2 的值均儲存在數組中，然後去尋找是否存在
set
中是否存在 a a a 滿足 a > x / 2 a > x / 2 a>x/2，則可以得到解
AC code
#include <bits/stdc++.h>
using namespace std;
#define MAXN 8000000
const int maxn = 1e9;
struct SegTree {
int tot;
int sub[MAXN]; // 儲存了內插補點
int lson[MAXN], rson[MAXN];
void init() {
for (int i = 0; i < MAXN; ++i)
sub[i] = INT_MAX;
memset(lson, 0xff, sizeof(int) * MAXN);
memset(rson, 0xff, sizeof(int) * MAXN);
tot = 1;
}
inline void up(int cur) {
if (lson[cur] == -1 && rson[cur] == -1) sub[cur] = INT_MAX;
else if (lson[cur] == -1) sub[cur] = sub[rson[cur]];
else if (rson[cur] == -1) sub[cur] = sub[lson[cur]];
else sub[cur] = min(sub[lson[cur]], sub[rson[cur]]);
}
inline int getLson(int cur) {
assert(tot < MAXN);
if (lson[cur] == -1)
lson[cur] = tot++;
return lson[cur];
}
inline int getRson(int cur) {
assert(tot < MAXN);
if (rson[cur] == -1)
rson[cur] = tot++;
return rson[cur];
}
void update(int x, int value, int cur = 0, int l = 1, int r = maxn) {
if (x == l && l == r) {
sub[cur] = value;
return;
}
int mid = (l + r) >> 1u;
if (x <= mid) {
update(x, value, getLson(cur), l, mid);
} else {
update(x, value, getRson(cur), mid + 1, r);
}
up(cur);
}
int query(int x, int y, int cur = 0, int l = 1, int r = maxn) {
if (x == l && y == r) return sub[cur];
int mid = (l + r) >> 1u;
if (y <= mid) {
return query(x, y, getLson(cur), l, mid);
} else if (x > mid) {
return query(x, y, getRson(cur), mid + 1, r);
} else {
return min(query(x, mid, getLson(cur), l, mid),
query(mid + 1, y, getRson(cur), mid + 1, r));
}
}
} segTree;
void solve() {
int q;
cin >> q;
segTree.init();
map<int, int> pool; // 目前集合中的資料
set<int> multi; // 用于處理重複資料
for (int i = 0; i < q; ++i) {
int op, x;
cin >> op >> x;
switch (op) {
case 1: {
auto iter = pool.find(x);
if (iter != pool.end()) {
iter->second++;
if (iter->second == 2)
multi.insert(x);
} else {
pool.insert({x, 1});
auto cur = pool.find(x);
auto lower = cur, up = cur;
up++;
if (lower != pool.begin()) {
lower--;
segTree.update(lower->first, x - lower->first);
}
if (up != pool.end()) {
segTree.update(x, up->first - x);
}
}
}
break;
case 2: {
auto cur = pool.find(x);
if (cur == pool.end()) break;
cur->second--;
if (cur->second == 1) {
multi.erase(x);
} else if (cur->second == 0) {
auto lower = cur, up = cur;
up++;
segTree.update(x, INT_MAX);
if (lower != pool.begin()) {
lower--;
if (up != pool.end())
segTree.update(lower->first, up->first - lower->first);
else
segTree.update(lower->first, INT_MAX);
}
pool.erase(cur);
}
}
break;
case 3: {
auto iter = pool.upper_bound(x / 2);
if (iter == pool.end()) { // 沒有值比 x / 2 更大了，則不存在 a + b > x 了
cout << "No" << endl;
break;
}
auto lower = iter;
if (lower != pool.begin()) {
lower--;
if (lower->first + iter->first <= x) {
lower++;
}
}
auto mu = multi.lower_bound(iter->first);
if (mu != multi.end()) {
cout << "Yes" << endl;
} else {
int res = segTree.query(lower->first, maxn);
if (res < x)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
break;
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int test_index_for_debug = 1;
char acm_local_for_debug;
while (cin >> acm_local_for_debug) {
if (acm_local_for_debug == '$') exit(0);
cin.putback(acm_local_for_debug);
if (test_index_for_debug > 20) {
throw runtime_error("Check the stdin!!!");
}
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
}
#else
solve();
#endif
return 0;
}
![POJ 1284 Primitive Roots (歐拉函數&原根定理)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)