luogu P5358 [SDOI2019]快速查询【模拟（？）】

佚名 6年前 (2019-05-09) 随笔 555人围观抢沙发百度已收录

把有单点修改和查询的点离散进一个数组，然后单点修改直接改，记录一个修改时间t，维护一个sm表示这些离散的点的和，val表示出了离散点其他点的值，因为都是一样的所以只记录这一个值即可，记录ljlc为加法乘法的lazytag，整体加整体乘的时候像线段树一样改smljlc，还有修改val，整体赋值的时候把valsmljlc都初始化，记录一个赋值时间ti
单点查询的时候如果这个点的修改时间比当前赋值时间早就直接val，否则是数组值和lazytag操作一下，整体查询直接sm+val*has即可
那个求逆元本来应该线性预处理的，但是我看快速幂跑过了就没管（……

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int N=200005,mod=1e7+19;
int n,m,q,o[N],p[N],a[N],b[N],g[N],tot,has,ti,t[N];
long long v[N],d[N],sm,ans,lj,lc=1,val;//,r[N];
map<int,int>mp;
int read()
{
    int r=0,f=1;
    char p=getchar();
    while(p>'9'||p<'0')
    {
        if(p=='-')
            f=-1;
        p=getchar();
    }
    while(p>='0'&&p<='9')
    {
        r=r*10+p-48;
        p=getchar();
    }
    return r*f;
}
long long ksm(long long a,long long b)
{
    long long r=1;
    while(b)
    {
        if(b&1)
            r=r*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return r;
}
int main()
{
    n=read(),q=read();
    for(int i=1;i<=q;i++)
    {
        o[i]=read();
        if(o[i]==1)
            p[i]=read(),v[i]=read(),g[++tot]=p[i];
        else if(o[i]==5)
            p[i]=read(),g[++tot]=p[i];
        else if(o[i]!=6)
            v[i]=read();
    }
    m=read();
    for(int i=1;i<=m;i++)
        a[i]=read(),b[i]=read();
    sort(g+1,g+1+tot);
    for(int i=1;i<=tot;i++)
        if(i==1||g[i]!=g[i-1])
            mp[g[i]]=++has;
    for(int i=1;i<=q;i++)
        p[i]=mp[p[i]];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=q;j++)
        {
            int w=(a[i]+1ll*j*b[i]%q)%q+1;
            if(o[w]==1)
            {
                sm=(sm-((t[p[w]]<ti)?val:(d[p[w]]*lc+lj))+v[w])%mod;
                d[p[w]]=(v[w]-lj)*ksm(lc,mod-2)%mod;
                t[p[w]]=(i-1)*q+j;
            }
            else if(o[w]==2)
            {
                val=(val+v[w])%mod;
                sm=(sm+v[w]*has)%mod;
                lj=(lj+v[w])%mod;
            }
            else if(o[w]==3)
            {
                val=val*v[w]%mod;
                sm=sm*v[w]%mod;
                lc=lc*v[w]%mod;
                lj=lj*v[w]%mod;
            }
            else if(o[w]==4)
            {
                val=v[w],lj==0,lc=1;
                ti=(i-1)*q+j;
                sm=v[w]*has%mod;
            }
            else if(o[w]==5)
                ans=(ans+((t[p[w]]<ti)?val:(d[p[w]]*lc+lj)%mod))%mod;
            else
                ans=(ans+sm+val*(n-has))%mod;
        }
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}