LuoguP5358「SDOI2019」题解

我是鸽子/cy

Description

维护一个长度为 $n$ 的序列$a_n$，$q$次操作.

要求支持单点赋值、整体赋值、整体加、整体乘、单点查询和整体求和。

$n \leq 10^9, q \leq 10^5, 0 \leq a_i \leq 10^9$.

Samples

Input #1

7
28
6
4 -192321079
3 418379342
1 3 189801569
3 -840249197
4 -751917965
3 649799919
1 5 -92666141
6
4 451258008
5 1
4 696880327
3 772574465
6
4 301010289
3 480168068
5 3
5 2
4 840536237
5 5
5 4
1 7 -792284106
2 604521872
3 966540578
2 -381646699
3 -939378260
2 -20129935
6
2
0 1
197 199

Output #1

2816930

Solution

$\rm Subtask 1$直接随便拿一个平衡树就好了。

全部数据的话，序列长度极大，有$10^9$, 显然要求执行操作复杂度$\mathcal O(1)$.

注意到本质不同的操作只有$10^5$个，那么可以把涉及的编号拿出来离散化一下即可。

因为所有的区间操作全部是针对整个数列的，考虑类似于分块打标记的方式，我们维护四个标记：

• $\rm add$ 全局加标记，$\rm mul$ 全局乘标记， $\rm sum$ 全局和标记， $\rm inv$ 逆元标记。

针对操作二，那么就有add += val, sum += n * val.

针对操作三，那么就有add *= val, mul *= val, sum *= val.

针对操作四，之前的修改全都白费了，就有add = 0, mul = 1, sum = n * val.

针对操作五，那么就有ans += mul * a[x] + add.

操作六就直接在答案上累加sum标记即可。

考虑操作一， 由于我们要考虑标记，所以不能把$\rm a_x$直接赋值为$\rm val$, 假设我们这么干了，那么我们统计的答案就是mul * val + add.

但是实际上查询这个点，我们直到结果应该是val, 那么可以得到val_real = (val - add) * inv.

注意进行这个操作的同时，全局和标记也需要修改，即sum += val_real - val.

其他的就是注意随地取模，注意下细节就好了，时间复杂度$\mathcal O(q \log q + tq)$

Code

/* Headers */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define RevEdge(x) x^1
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE], *is = ibuf, *its = ibuf;
    char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE;
    inline char getch() {
        if(is == its)
            its = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
        return (is == its) ? EOF : *is++;
    }
    inline int getint() {
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-') {neg = 1;ch = getch();}
        while(isdigit(ch)) {
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg ? -res : res;
    }
    inline void flush(){
        fwrite(obuf, 1, os - obuf, stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot) flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--) putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x, bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
template<typename T>
inline T max(T a, T b) {return (a > b) ? a : b;}
template<typename T>
inline T min(T a, T b) {return (a > b) ? b : a;}
/* definitions */
#define ll long long
const int MAXN = 1e5 + 10, mod = 1e7 + 19;
int n, m, T, A[MAXN], B[MAXN], d[MAXN], ser[MAXN], rser[MAXN], cnt, tot;
ll a[MAXN], add, mul, sum, inv, ans;
struct Query {int opt, x, y;} q[MAXN];
/* functions */
inline ll quick_power(ll a, ll b, ll p = mod) {
    ll res = 1ll, base = a;
    while(b) {
        if(b & 1) res = res * base % p;
        b >>= 1; base = base * base % p;
    } return res;
}
inline void solve(int opt, int x, int y) {
    ll last, now;
    if(opt == 1) {
        last = (a[ser[x]] * mul + add) % mod; sum = (sum - last + y) % mod;
        now = (y - add) * inv % mod; (!ser[x]) ? rser[ser[x] = ++cnt] = x : 0;
        a[ser[x]] = now;
    } else if(opt == 2) {
        add = (add + x) % mod; sum = (sum + 1ll * n * x) % mod;
    } else if(opt == 3) {
        add = add * x % mod; mul = mul * x % mod; sum = sum * x % mod; inv = inv * y % mod;
    } else if(opt == 4) {
        mul = inv = 1; add = 0; sum = 1ll * n * x % mod;
        FOR(i, 1, cnt, 1) ser[rser[i]] = 0, a[i] = rser[i] = 0;
        a[0] = x; cnt = 0;
    } else if(opt == 5) {
        if(!x || !ser[x]) ans = (ans + (a[0] * mul + add) % mod) % mod;
        else ans = (ans + (a[ser[x]] * mul + add) % mod) % mod;
    } else if(opt == 6) ans = (ans + sum) % mod;
}
int main(int argc, char *argv[]) {
    FILE_IN("data.in"); read(n); read(m);
    FOR(i, 1, m, 1) {
        read(q[i].opt);
        if(q[i].opt < 6) read(q[i].x);
        if(q[i].opt == 1) read(q[i].y), q[i].y %= mod, d[++tot] = q[i].x;
        if(q[i].opt >= 2 && q[i].opt <= 4) q[i].x %= mod;
    } read(T);
    FOR(i, 1, T, 1) read(A[i]), read(B[i]);
    int now; std::sort(d + 1, d + tot + 1);
    tot = std::unique(d + 1, d + tot + 1) - d - 1;
    FOR(i, 1, m, 1) {
        if(q[i].opt == 1) q[i].x = std::lower_bound(d + 1, d + tot + 1, q[i].x) - d;
        if(q[i].opt == 3) q[i].y = quick_power(q[i].x, mod - 2);
        if(q[i].opt == 5) now = std::lower_bound(d + 1, d + tot + 1, q[i].x) - d,
                          q[i].x = (d[now] == q[i].x) ? now : 0;
    } mul = inv = 1; add = sum = 0;
    FOR(i, 1, T, 1) {
        FOR(j, 1, m, 1) {
            now = (A[i] + 1ll * j * B[i] % m) % m + 1;
            solve(q[now].opt, q[now].x, q[now].y);
        }
    }
    ans = (ans % mod + mod) % mod; printf("%lld\n", ans);
    return 0;
}

THE END