题目链接：

[SDOI2019]快速查询

对于整个序列维护一个标记$(k,b)$表示序列的每个数的真实值为$k*a_{i}+b$(注意要实时维护$k$的逆元)，并记录序列的和。

对于单点修改，将$a_{i}$修改为$val$，因为有序列标记，所以实际修改成$\frac{val-b}{k}$并开一个栈将这个位置压入栈中。

对于序列加和序列乘操作，直接修改标记与序列和即可，注意修改$k$时也要修改$b$。

对于序列赋值操作，将$k$赋成$0$，将$b$赋成$val$(即将操作看成先序列赋成$0$再序列加)并将之前压入栈中的数都弹出并清零(因为只有栈中的数和其他的不一样)。

查询时返回之前记录的值即可。因为每次单点修改只会进栈和出栈一次，所以可以保证序列赋值的时间复杂度。

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<cstdio>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int mod=10000019;

int n,m,t;

int s[10000010];

int v[100010];

int sum;

int cnt;

int ans;

int pls;

int mul=1;

int inv=1;

int ai,bi;

struct lty

{

    int inv,val,opt,num;

}a[100010];

int quick(int x,int y)

{

    int res=1;

    while(y)

    {

        if(y&1)

        {

            res=1ll*res*x%mod;

        }

        y>>=1;

        x=1ll*x*x%mod;

    }

    return res;

}

void change(int x,int y)

{

    sum=(sum+1ll*(mod-v[x])*mul+mod-pls)%mod;

    v[x]=1ll*(y-pls+mod)*inv%mod,s[++cnt]=x;

    sum=(sum+y)%mod;

}

void add(int x)

{

    sum=(sum+1ll*n*x%mod)%mod;

    pls=(pls+x)%mod;

}

void cover(int x)

{

    while(cnt)v[s[cnt--]]=0;

    mul=inv=1,pls=x;

    sum=1ll*n*x%mod;

}

void multi(int x,int y)

{

    if(x)

    {

        sum=1ll*sum*x%mod,mul=1ll*mul*x%mod;

        pls=1ll*pls*x%mod,inv=1ll*inv*y%mod;

    }

    else

    {

        cover(0);

    }

}

int query(int x)

{

    if(x==0)return sum;

    else return (1ll*v[x]*mul+pls)%mod;

}

int main()

{

    scanf("%d%d",&n,&m);

    n%=mod;

    for(int i=1;i<=m;i++)

    {

        scanf("%d",&a[i].opt);

        if(a[i].opt==1||a[i].opt==5)scanf("%d",&a[i].num),s[++cnt]=a[i].num;

        if(a[i].opt<=4)scanf("%d",&a[i].val),a[i].val=(a[i].val%mod+mod)%mod,a[i].inv=quick(a[i].val,mod-2);

    }

    sort(s+1,s+1+cnt);

    cnt=unique(s+1,s+1+cnt)-s-1;

    for(int i=1;i<=m;i++)

    {

        if(a[i].opt==1||a[i].opt==5)

        {

            a[i].num=lower_bound(s+1,s+1+cnt,a[i].num)-s;

        }

    }

    scanf("%d",&t);

    cnt=0;

    for(int i=1;i<=t;i++)

    {

        scanf("%d%d",&ai,&bi);

        ai%=m,bi%=m;

        for(int j=1;j<=m;j++)

        {

            int now=(ai+1ll*j*bi)%m+1;

            if(a[now].opt==1)change(a[now].num,a[now].val);

            if(a[now].opt==2)add(a[now].val);

            if(a[now].opt==3)multi(a[now].val,a[now].inv);

            if(a[now].opt==4)cover(a[now].val);

            if(a[now].opt==5)ans=(ans+query(a[now].num))%mod;

            if(a[now].opt==6)ans=(ans+query(0))%mod;

        }

    }

    printf("%d",ans);

}

巴特西

[SDOI2019]快速查询——模拟

题目链接：

最新文章

热门文章