题解 P6617 【查找 Search】
Clever_Jimmy
·
·
题解
查找 Search 题解
upd: fixed a typo
题目思路很比较直观，抽象出来的模型如下：
你需要写一个数据结构来维护一个序列 a，支持以下操作：
-
1 pos val 表示将 a_{pos} 的值设为 val；
-
2 l r 询问是否 \exists j, k \in [l, r], j < k, a_j + a_k = w。
对于每个操作 2，若存在请输出 Yes，不存在请输出 No。
Subtask 1
算法一：O(nm) 模拟。
对于每个修改直接保留修改数组 a；
注意到值域不超过 3 \cdot 10^5，那么每次查询的时候从左往右记录区间内是否出现了某个值。
最后统计一下就好了。
需要注意的是，如果 w 是偶数，可能会出现 \dfrac{w}{2} + \dfrac{w}{2} = w 的情况。
期望得分：7 分。
#include <bits/stdc++.h>
const int N = 1e5 + 10;
int n, m, w, a[N], to[N];
void clear() { memset(to, 0, sizeof(to)); }
int main() {
scanf("%d %d %d", &n, &m, &w);
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
for(int i = 1; i <= m; ++i) {
int op, x, y;
scanf("%d %d %d", &op, &x, &y);
if(op == 1) a[x] = y;
else if(op == 2) {
int flag = 0;
for(int j = x, half = 0; j <= y; ++j) {
if(a[j] * 2 == w) half++; // 这里是 w / 2 的情况
else to[w - a[j]]++;
if(half >= 2) { flag = 1; break; }
}
if(flag) { puts("Yes"), clear(); continue; }
for(int j = x; j <= y; ++j)
if(to[a[j]]) { flag = 1; break; }
if(flag) { puts("Yes"), clear(); continue; }
puts("No"), clear();
}
}
return 0;
}
Subtask 2
这档部分分是不带修的。
算法二：对于序列中的每个数，维护一个值 A_i：
A_i =
\begin{cases}
\inf & \exists i' \in(i, j), a_i = a_{i'}
\\
\min\limits_{i < j \le n \bigwedge a_i +a_j = w}j & \text{otherwise}
\end{cases}
查询的时候直接查 \min\limits_{l \le i \le r} A_i 是否小于等于 r 即可。
时间复杂度为 $O(n \log n)$。
这里给出如何在 $O(n)$ 的时间复杂度内求出 $A$ 数组的代码：
```cpp
for(int i = n; i >= 1; --i) {
if(pr[ I(a[i]) ]) {
if(pr[a[i]] && pr[a[i]] < pr[ I(a[i]) ]) A[i] = oo;
else A[i] = pr[ I(a[i]) ];
}
else A[i] = oo;
pr[a[i]] = i;
}
```
期望得分：$20$ 分。
结合算法一可得到 $27$ 分。
#### Subtask 3
算法三：正解。
在算法二的基础上，我们考虑怎么对 $A$ 进行单点修改。
考虑维护一个以 $A_i$ 的值域为下标的结构体数组，
每个位置都存一个 `std::set`，来维护 $A_i$ 这个值出现的下标。
- 定义 $a_i$ 的同值前驱为 $\max\limits_{j < i \bigwedge a_j = a_i} j$，补前驱为 $\max\limits_{j < i \bigwedge a_j + a_i = w} j$；
- 定义 $a_i$ 的同值后继为 $\min\limits_{j > i \bigwedge a_j = a_i} j$，补后继为 $\min\limits_{j > i \bigwedge a_j + a_i = w} j$。
每次修改一个 $a_i := x$，有哪些值变了呢？
1. $a_i$ 的同值前驱 $j$，
若 $a_i$不存在补前驱，或补前驱的位置在 $j$ 之前，则$A_j$ 为 $A_i$；
否则不变。
2. $a_i$ 的补前驱 $j$，
若 $a_i$ 不存在同值前驱，或同值前驱的位置在 $j$ 之前，
若 $a_i$ 存在同值后继，那么就是 $a_i$ 的同值后继的位置；
否则为 $\inf$；
否则不变。
3. $x$ 的同值前驱 $j$，
若 $a_i$不存在补前驱，或补前驱的位置在 $j$ 之前，则$A_j$ 为 $\inf$；
否则 $A_j$ 为 $\inf$。
4. $x$ 的补前驱 $j$，
若 $x$ 不存在同值前驱，或同值前驱的位置在 $j$ 之前，那么 $A_j$ 为 $i$；
否则不变。
5. $i$，
若 $x$ 不存在补后继，那么 $A_i$ 为 $\inf$；
否则，
若 $x$ 存在同值后继，且同值后继的位置在补后继之前，那么 $A_j$ 为 $\inf$；
否则 $A_i$ 为补后继的位置。
这些位置都可以用 `std::set` 来维护。
有个技巧，可以同时维护升降序的两个 `std::set`，插入时同时插入，删除时同时删除，
查找前驱时可以在升序的 `std::set` 里 `std::upper_bound`；
查找后继时可以在降序的 `std::set` 里 `std::upper_bound`。
至此，我们在 $O((m + n) \log n)$ 的时间复杂度内解决了这道题。
代码如下：
```cpp
#include <bits/stdc++.h>
#define LL long long
#define SET std::set <int>::iterator
#define I(x) (w - x)
const int N = 5e5 + 10;
const int oo = 0x3f3f3f3f;
int n, m, w;
int a[N], pr[N], A[N];
struct SEGNODE {
int lc, rc, min_val;
};
struct SEGTREE {
static const int MAXSIZE = N << 2;
SEGNODE t[MAXSIZE];
void pushup(int p) { t[p].min_val = std::min(t[p << 1].min_val, t[p << 1 | 1].min_val); }
void build(int p, int l, int r) {
t[p].lc = l, t[p].rc = r;
if(l == r) {
t[p].min_val = A[l];
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
}
void modify(int p, int x, int v) {
if(t[p].lc == t[p].rc) {
t[p].min_val = v;
return;
}
int mid = t[p].lc + t[p].rc >> 1;
if(x <= mid) modify(p << 1, x, v);
else modify(p << 1 | 1, x, v);
pushup(p);
}
int query(int p, int l, int r) {
if(l <= t[p].lc && t[p].rc <= r) return t[p].min_val;
int mid = t[p].lc + t[p].rc >> 1, res = oo;
if(l <= mid) res = std::min(res, query(p << 1, l, r));
if(mid < r) res = std::min(res, query(p << 1 | 1, l, r));
return res;
}
} t1;
struct SETTREE {
static const int MAXSIZE = N;
std::set <int> pos1[MAXSIZE]; // for succ
std::set <int, std::greater <int> > pos2[MAXSIZE]; // for pred
void insert(int pos, int v) {
pos1[v].insert(pos);
pos2[v].insert(pos);
}
int pred(int pos, int v) {
SET it = pos2[v].upper_bound(pos);
if(it == pos2[v].end()) return 0;
else return *it;
}
int succ(int pos, int v) {
SET it = pos1[v].upper_bound(pos);
if(it == pos1[v].end()) return 0;
else return *it;
}
void remove(int pos, int v) {
if(pos1[v].find(pos) != pos1[v].end()) pos1[v].erase(pos);
if(pos2[v].find(pos) != pos2[v].end()) pos2[v].erase(pos);
}
} t2;
void modify(int pos, int val) { // in seg_tree: A[pos]->val
t1.modify(1, pos, val);
}
void Modify1(int x, int y) { // x->pos, y->val
int v = a[x];
int A_val = t1.query(1, x, x);
int pre_v = t2.pred(x, v);
int nxt_v = t2.succ(x, v);
int pre_iv = t2.pred(x, I(v) );
if(pre_v) {
if(!pre_iv || pre_iv < pre_v) modify(pre_v, A_val);
}
if(pre_iv) {
if(!pre_v || pre_v < pre_iv) {
if(!nxt_v) modify(pre_iv, oo);
else modify(pre_iv, nxt_v);
}
}
}
void Modify2(int x, int y) { // x->pos, y->val
int pre_y = t2.pred(x, y);
int nxt_y = t2.succ(x, y);
int pre_iy = t2.pred(x, I(y) );
int nxt_iy = t2.succ(x, I(y) );
if(pre_y) {
if(!pre_iy || pre_iy < pre_y) modify(pre_y, oo);
}
if(nxt_iy) {
if(nxt_y && nxt_y < nxt_iy) modify(x, oo);
else modify(x, nxt_iy);
}
else modify(x, oo);
if(pre_iy) {
if(!pre_y || pre_y < pre_iy) modify(pre_iy, x);
}
}
void Modify(int x, int y) {
Modify1(x, y);
Modify2(x, y);
t2.remove(x, a[x]); // remove by (pos, val)
t2.insert(x, y); // val->y at pos->x
a[x] = y;
}
int Query(int l, int r) {
return t1.query(1, l, r) <= r;
}
int main() {
scanf("%d %d %d", &n, &m, &w);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = n; i >= 1; --i) {
if(pr[ I(a[i]) ]) {
if(pr[a[i]] && pr[a[i]] < pr[ I(a[i]) ]) A[i] = oo;
else A[i] = pr[ I(a[i]) ];
}
else A[i] = oo;
pr[a[i]] = i;
}
t1.build(1, 1, n);
for(int i = 1; i <= n; ++i) t2.insert(i, a[i]);
for(int i = 1; i <= m; ++i) {
int opt, x, y;
scanf("%d %d %d", &opt, &x, &y);
if(opt == 1) Modify(x, y);
if(opt == 2) puts(Query(x, y) ? "Yes" : "No");
}
return 0;
}
```
期望得分：$100$ 分。
哦，这是没强制在线的代码，随便改改吧（