SDOI2019快速查询

链接

vijos

思路

虽然询问1e7，但他询问很有意思，所以最多修改1e5个。
先把他们修改的点缩小到1e5之内并没有什么影响。
然后维护mul和add。不修改很好弄，修改的点可以弄点式子加加减减弄出来，逆元线性推也是可以的。
总的复杂度\(O(qlogq+tq+mod)\)

总结

我考场上连\(O(n^3)\)都写不对，回来不到一个小时就A了？浮躁！
其实已经写了三遍了、、码力急需加强

代码

#include <bits/stdc++.h>
#define debug(x) cerr << x << " "
using namespace std;
const int N = 1e5 + 7, mod = 1e7 + 19;
int read() {
    int x = 0, f = 1; char s = getchar();
    for (; s > '9' || s < '0'; s = getchar()) if(s == '-') f = -1;
    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
    return x * f;
}
int n, q, t, a[107], b[107];
struct QUERY {
    int opt, id, val;
} Q[N];
map<int, int> Hash;
int lsh_cnt, inv[N*100], stak[N], top;
struct node {
    int val, add, mul;
    node() {val = -1, add = 0,mul = 1;}
    void clear() {val = -1, add = 0, mul = 1;}
} las[N];
int main() {
    // freopen("data.in", "r", stdin);
    n = read(), q = read();
    for (int i = 1; i <= q; ++i) {
        Q[i].opt = read();
        if (Q[i].opt == 1) Q[i].id = read(), Q[i].val = read();
        if (Q[i].opt == 2 || Q[i].opt == 3 || Q[i].opt == 4) Q[i].val = read();
        if (Q[i].opt == 5) Q[i].id = read();
        if (Q[i].id && !Hash.count(Q[i].id)) Hash[Q[i].id] = ++lsh_cnt;
        while (Q[i].val < 0) Q[i].val += mod;
        Q[i].val %= mod;
    }
    for (int i = 1; i <= q; ++i)
        if (Q[i].opt == 1 || Q[i].opt == 5)
            Q[i].id = Hash[Q[i].id];
    inv[1] = 1;
    for (int i = 2; i < mod; ++i)
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    t = read();
    for (int i = 1; i <= t; ++i) a[i] = read(), b[i] = read();
    // cerr << "read is ok\n";
    int ans = 0, tot = 0, add = 0, mul = 1, init = 0;
    for (int i = 1; i <= t; ++i) {
        for (int j = 1; j <= q; ++j) {
            int x = (a[i] + 1LL * j * b[i]) % q + 1;
            // cout<<x<<"\n";
            // debug(Q[x].opt),debug(Q[x].id),debug(Q[x].val);cerr<<"\n";
            if (Q[x].opt == 1) {
                if (las[Q[x].id].val == -1) {
                    tot = ((tot - (1LL * init * mul % mod + add) % mod) %mod + mod) % mod;
                    stak[++top] = Q[x].id;
                } else {
                    int now_mul = 1LL * mul * inv[las[Q[x].id].mul] % mod;
                    int now_add = ((add - 1LL * las[Q[x].id].add * now_mul % mod) % mod + mod) % mod;
                    tot = ((tot - (1LL * las[Q[x].id].val * now_mul % mod + now_add) % mod) % mod + mod) % mod;
                }
                tot = (tot + Q[x].val) % mod;
                las[Q[x].id].val = Q[x].val;
                las[Q[x].id].add = add;
                las[Q[x].id].mul = mul;
            }
            if (Q[x].opt == 2) {
                add = (add + Q[x].val) % mod; 
                tot = (tot + 1LL * Q[x].val * n % mod) % mod;
            }
            if (Q[x].opt == 3) {
                add = 1LL * add * Q[x].val % mod;
                mul = 1LL * mul * Q[x].val % mod;
                tot = 1LL * tot * Q[x].val % mod;
            }
            if (Q[x].opt == 4) {
                while (top) las[stak[top--]].clear();
                init = Q[x].val, add = 0, mul = 1;
                tot = 1LL * Q[x].val * n % mod;
            }
            if (Q[x].opt == 5) {
                if (las[Q[x].id].val == -1) {
                    ans = ((ans + (1LL * init * mul % mod + add) % mod) %mod + mod) % mod;
                } else {
                    int now_mul = 1LL * mul * inv[las[Q[x].id].mul] % mod;
                    int now_add = ((add - 1LL * las[Q[x].id].add * now_mul % mod) % mod + mod) % mod;
                    ans = ((ans + (1LL * las[Q[x].id].val * now_mul % mod + now_add) % mod) % mod + mod) % mod;
                }
            }
            if (Q[x].opt == 6) ans = (ans + tot) % mod;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
/*
5 5
6
6
3 4
1 3 8
5 5
1
8062 15996
*/