题解 P5358 【[SDOI2019]快速查询】
龙之吻—水货
2019-05-08 08:39:31
# [SDOI2019]快速查询
## 题目大意
在 $O(n)$ 的时间复杂度内，完成题目所给的 $6$ 种操作。
## 解题报告
场外同步赛选手，感觉此题并不难？ QwQ
### 对于子任务一的做法
发现允许 $O(nlogn)$ 的时间复杂度，离散化之后就变成了了[【模板】线段树 2](https://www.luogu.org/problemnew/show/P3373)，似乎比那个还简单不少，因为操作都是全局的。
### 对于 $100%$ 的做法
发现操作数一共有 $10^5 \times 100 = 10^7$ 不做到每次 $O(1)$ 的时间复杂度肯定是不行了。
自习思考发现这道题唯一的难点就是操作 $5$，如果可以在 $O(1)$ 的时间复杂度内完成这个操作的话，在在 $O(1)$ 的时间复杂度内完成其他的操作似乎并不难。
所以我们现在只需要考虑操作 $5$ 即可。
如果想到了 $50%$ 的做法，那么不难发现有一个东西可以用到，就是线段树的懒标记，这个懒标记记录了两个值 $mul$ 和 $add$ 表示如果原来的数为 $x$ 那么它应该变为 $x \times mul + add$。
发现我们可以很轻松地维护出来这个标记在全局的前缀和，那么，这个东西是否可满足可减性呢？换句话说，我们是否能够通过 $sum_r - sum_{l-1}$ 来得到 $x$ 从 $l$ 开始，到 $r$ 这一段操作之后变成了什么呢？
思考一下这个问题，假设我们知道 $mul_r, add_r, mul_{l-1}, add_{l-1}$ 是否能求出 $sum_r - sum_{l-1}$ 呢？
我们发现，乘一个数会对 $mul$ 和 $add$ 产生影响，而加一个数只会对 $add$ 产生影响，所以 $\frac{mul_r}{mul_{l-1}}$ 就是这段操作所乘的值，求出这个值后，这段操作所加的值也可以很轻易地求出来，也就是 $add_r - add_{l-1} \times \frac{mul_r}{mul_{l-1}}$。
这样，我们只需要存储一个前缀和，之后用一个 hash 表或者离散化一下记录每个数最后在哪个操作里面被改变就可以了，由于是在取模的意义下，所以需要一个线性求逆元。然后我们就可以完成操作 $5$ 了，之后，其他的操作就十分简单，也就不细说了。
时间复杂度 $O(n)$， Accepted！
附上考场(同步赛) Code :
```cpp
#include<cstdio>
#include<algorithm>
#include<tr1/unordered_map>
class Solution{
private :
static const int maxn = 1e5 + 7;
static const int maxm = 1e2 + 7;
static const int mod = 1e7 + 19;
struct Oper{
int op, pos, val;
};
struct Val{
int mul, add;
};
int n, q, t, a[maxm], b[maxm], inv[mod], id[maxn * maxm], sum, nowVal, start;
int tp, res, ans, vl[maxn];
Oper p[maxn];
Val v[maxn * maxm];
std::tr1::unordered_map<int, int> last;
inline void make(int &x) {
if (x >= mod) {
x -= mod;
}
}
inline int query(int pos) {
if (!last.count(pos)) {
return nowVal;
}
//bool flag = pos == 5;
pos = last[pos];
if (pos < start) {
return nowVal;
}
int mul = 1ll * v[tp].mul * inv[v[pos].mul] % mod;
/*
if (flag) {
//fprintf(stderr, "%d %d\n", v[tp].mul, v[pos].mul);
}
*/
int add = v[tp].add + mod - 1ll * v[pos].add * mul % mod;
make(add);
return (1ll * p[id[pos]].val * mul + add) % mod;
}
public :
Solution() {
get();
solve();
}
void get() {
scanf("%d", &n);
scanf("%d", &q);
for (register int i = 1; i <= q; i++) {
scanf("%d", &p[i].op);
if (p[i].op == 1) {
scanf("%d %d", &p[i].pos, &p[i].val);
} else if (p[i].op == 5) {
scanf("%d", &p[i].pos);
} else if (p[i].op == 6) {
continue;
} else {
scanf("%d", &p[i].val);
}
p[i].val = (p[i].val % mod + mod) % mod;
}
scanf("%d", &t);
for (register int i = 1; i <= t; i++) {
scanf("%d %d", a + i, b + i);
}
}
void solve() {
inv[1] = 1;
for (register int i = 2; i < mod; i++) {
inv[i] = 1ll * (mod - (mod / i)) * inv[mod % i] % mod;
}
v[0].mul = 1;
for (register int i = tp = 1, ed = q * t; i <= ed; i++, tp++) {
int A = i / q + 1, B = i % q;
if (B == 0) {
A--, B = q;
}
id[i] = (a[A] + 1ll * B * b[A]) % q + 1;
int op = p[id[i]].op, pos = p[id[i]].pos, val = p[id[i]].val;
//fprintf(stderr, "%d %d %d\n", op, pos, val);
if (op == 1) {
v[i] = v[i - 1];
int lastVal = query(pos);
make(sum += mod - lastVal);
make(sum += val);
last[pos] = i;
} else if (op == 2) {
v[i] = v[i - 1];
make(v[i].add += val);
make(nowVal += val);
make(sum += 1ll * n * val % mod);
} else if (op == 3) {
v[i].mul = 1ll * v[i - 1].mul * val % mod;
v[i].add = 1ll * v[i - 1].add * val % mod;
nowVal = 1ll * nowVal * val % mod;
sum = 1ll * sum * val % mod;
} else if (op == 4) {
v[i].mul = 1;
nowVal = val, sum = 1ll * nowVal * n % mod;
start = i;
} else if (op == 5) {
v[i] = v[i - 1];
res = query(pos);
//fprintf(stderr, "%d\n", res);
make(ans += res);
} else {
v[i] = v[i - 1];
res = sum;
//fprintf(stderr, "%d\n", res);
make(ans += res);
}
}
printf("%d\n", ans);
}
};
Solution sol;
int main() {}
```