即将 AFO 的老年选手

题解 P5358 【[SDOI2019]快速查询】

2021-01-18 20:25:50


广告


记两个标记 $addv$ 和 $mulv$,表示全局乘和全局加,并维护 $sumv$ 表示所有元素的和。

全局加和全局乘很好处理;全局赋值也很好处理,只需要令 $mulv\gets 1$、$addv\gets w$ 即可。

考虑单点赋值。我们直接开一个 unordered_map 存下所有被单点赋值过的点,每次只需要将 $\frac{w-addv}{mulv}$ 插入其中即可。我们只要在全局赋值时清空这个 unordered_map 即可。

单点查询时,只需要查询 unordered_map 中有无 $p$ 来得到对应值,再乘上 $mulv$ 并加上 $addv$ 即可得到真实值。

同时不难在修改操作中维护 $sumv$(对于单点赋值可以把原来的减掉再加上新的值),这样子也支持了全局求和。

线性预处理逆元,即可做到 $\mathcal{O}(qt)$。

这个做法大概是用哈希表清空代替了别的题解中的记时间戳,少了一些细节但是跑得会慢一些。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=1e7+19;

int n,Q,T,a[N],b[N],inv[mod],ans=0;
struct query { int op,p,w; } q[N];

int addv=0,mulv=1,sumv=0;
unordered_map<int,int> M;
int F(int x) { return (1ll*(M.count(x)?M[x]:0)*mulv+addv)%mod; }
void work(query q) {
    if (q.op==1) sumv=(sumv-F(q.p)+mod)%mod,M[q.p]=1ll*(q.w-addv+mod)*inv[mulv]%mod,sumv=(sumv+q.w)%mod;
    if (q.op==2) addv=(addv+q.w)%mod,sumv=(sumv+1ll*n*q.w)%mod;
    if (q.op==3) mulv=1ll*mulv*q.w%mod,addv=1ll*addv*q.w%mod,sumv=1ll*sumv*q.w%mod;
    if (q.op==4) mulv=1,addv=q.w,sumv=1ll*n*q.w%mod,M.clear();
    if (q.op==5) ans=(ans+F(q.p))%mod;
    if (q.op==6) ans=(ans+sumv)%mod;
}

int main() {
    inv[1]=1;
    for (int i=2;i<mod;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    n=read(),Q=read();
    for (int i=1;i<=Q;++i) {
        q[i].op=read();
        if (q[i].op==1||q[i].op==5) q[i].p=read();
        if (q[i].op<=4) q[i].w=(read()%mod+mod)%mod;
        if (q[i].op==3&&!q[i].w) q[i].op=4; // 乘 0 相当于整体赋值为 0
    }
    T=read();
    for (int i=1;i<=T;++i) a[i]=read(),b[i]=read();
    for (int i=1;i<=T;++i)
        for (int j=1;j<=Q;++j) work(q[(a[i]+1ll*j*b[i])%Q+1]);
    printf("%d\n",ans);
    return 0;
}