P5358[SDOI2019]快速查询

和当初对一轮D2T2有着同样的感觉吧,省选上最应该做出来的一道题(菜永远是原罪)
首先对于\(50\%\)的数据,我们可以直接线段树过去
但是,我们发现除了单点赋值和查询以外,其他的操作都是对全局进行的操作
虽然元素有\(10^9\)个,但是,操作也最多只有\(10^5\)个,也就是说，修改或查询的位置,也最多是\(10^5\)个,只需要讲这\(10^5\)个位置,单独拿出来维护。
而区间加法乘法和区间赋值我们都可以通过维护一个类似\(kx+b\)的形式
其中\(x\)表示赋值,\(k\)表示乘,\(b\)表示加法
优先级自然是\(x > k > b\),也就是说\(k\)会影响\(b\),\(x\)会影响\(k\)和\(b\)
之后在维护一个全局和就好了
但是,还有一个问题
就是单点修改后,\(k,b\)的值是不适用与我们新修改的值的.
现在全局的\(k,b\),将某一个点修改为\(v\)
只需要将这个点变成\((v - b) /k\)就可以了
至于除法,由于答案是在模质数的意义下,直接逆元就好了
线性求逆元或者费马小定理都是可以的
博主是用类似\(hash\)表的方法维护修改的位置

#include<cstdio>
#include<iostream>
#include<cctype>
#include<cstring>
#define LL long long
using namespace std;
const int N = 1e5 + 3;
const LL mod = 1e7 + 19;
struct Query{
    int type;   
    LL val;
    int p;
}q[N];
LL ni[mod];
inline LL read(){
    LL v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar(); 
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
struct edge{
    int pos;
    int nxt;    
    int idx;
    LL val;
}e[N << 1];
int head[mod + 2];
int n,m,t,tot;
inline void add(int x){
    int st = q[x].p % mod;
     e[++tot].pos = q[x].p;
     e[tot].val = 0;
     e[tot].nxt = head[st];
     head[st] = tot;  
}
inline int getpos(int x){
    int s = x % mod;
    for(int i = head[s];i;i = e[i].nxt){
        if(e[i].pos == x) return i;
    }
    return 0;
}
int main(){
    ni[1] = 1;
    for(int i = 2;i < mod;++i) ni[i] = mod - (mod / i) * ni[mod % i] % mod;
    n = read(),m = read();
    for(int i = 1;i <= m;++i){
        q[i].type = read();
        if(q[i].type == 1) q[i].p = read();
        if(q[i].type != 6) q[i].val = 1ll * (read() % mod + mod) % mod;
        if(q[i].type == 1) add(i);
    }
    LL mul = 1,add = 0,x = 0;
    LL sum = 0,ans = 0;
    LL last = 0;
    int T = read();
    for(int j = 1;j <= T;++j){
        LL xx = read(),yy = read();
    //  cout << x << " " << y << endl;
        for(int i = 1;i <= m;++i){
            
            int w = (xx + 1ll * i * yy) % m + 1;
        //  if(q[w].type >= 5)
        //  printf("%d %d %d %lld\n",w,q[w].type,q[w].p,q[w].val);
            if(q[w].type == 1){
                int s = getpos(q[w].p);
                if(last && e[s].idx < last)
                    sum = ((sum - x * mul - add) % mod + mod) % mod;    
                else sum = ((sum - e[s].val * mul - add) % mod + mod) % mod;
                e[s].idx = j * m + i;
                e[s].val = ((q[w].val - add) * ni[mul]) % mod + mod;
                e[s].val %= mod;
                sum = (sum + q[w].val) % mod; 
            }   
            if(q[w].type == 2){
                sum = (sum + 1ll * n * q[w].val) % mod;
                add = (add + q[w].val) % mod;   
            }
            if(q[w].type == 3 && q[w].val == 0) q[w].type = 4;
            if(q[w].type == 3){
                sum = (sum * q[w].val) % mod;
                mul = mul * q[w].val % mod; 
                add = (add * q[w].val) % mod;
            }
            if(q[w].type == 4){
                mul = 1,add = 0;
                sum = 1ll * n * q[w].val % mod;
                last = j * m + i;
                x = q[w].val;
            }
            if(q[w].type == 5){
                int s = getpos(q[w].val);
                if(s == 0) ans = (ans + x * mul + add) % mod;
                else if(last && e[s].idx < last) ans = (ans + x * mul + add) % mod;
                else ans = (ans + e[s].val * mul + add) % mod;      
            }
            if(q[w].type == 6) ans = (ans + sum) % mod;
        //  cout << ans << endl;
        }
    }
    printf("%lld\n",ans);
    return 0;   
}