Luogu5358 [SDOI2019]快速查询

不敢压行了，调不动\(QAQ\)。

注意查询散列表时，如果已经找到了数，但是是在覆盖以前的，直接返回找不到即可，因为散列表的特点是后插入的数先访问到。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100005
#define M 105
#define ll long long
#define il inline
#define rint register int
using namespace std;
const int p=10000019;
int n,q,t,nt=0,tot=0,allnum=0,s=0,add=0,mul=1,fr[p+25],nxt[p+25],d1[p+25],d2[p+25],inv[p+5],a[M],b[M];
int cnt=0;
ll ans=0;
struct node
{
    int opt;
    int x,val;
}ask[N];
il void Add(int x,int y)
{
    int key=x%p;
    ++tot,d1[tot]=x,d2[tot]=y,nxt[tot]=fr[key],fr[key]=tot;
}
il int getpos(int x)
{
    int key=x%p;
    for (rint i=fr[key];i;i=nxt[i])
    {
        ++cnt;
        if (d1[i]==x)
            return (i>nt)?i:-1;
    }
    return -1;
}
il int rval(int x)
{
    return ((ll)mul*x+add)%p;
}
il int tval(int x)
{
    mul=(mul+p)%p;
    return (ll)(x-add)*inv[mul]%p;
}
int main()
{
    inv[1]=1;
    for (rint i=2;i<p;++i)
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    scanf("%d",&n),scanf("%d",&q);
    for (rint i=1;i<=q;++i)
    {
        scanf("%d",&ask[i].opt);
        if (ask[i].opt==1)
            scanf("%d%d",&ask[i].x,&ask[i].val); else
        if (ask[i].opt==5)
            scanf("%d",&ask[i].x); else
        if (ask[i].opt!=6)
            scanf("%d",&ask[i].val);
    }
    scanf("%d",&t);
    for (rint i=1;i<=t;++i)
        scanf("%d%d",&a[i],&b[i]);
    for (rint i=1;i<=t*q;++i)
    {
        int ct=(i-1)%q+1,par=(i-ct)/q+1,t,k=((ll)a[par]+(ll)ct*b[par])%q+1;
        if (ask[k].opt==1)
            t=getpos(ask[k].x),(t==-1)?(((s-=rval(allnum))+=ask[k].val)%=p,Add(ask[k].x,tval(ask[k].val))):(((s-=rval(d2[t]))+=ask[k].val)%=p,(void)(d2[t]=tval(ask[k].val))); else
        if (ask[k].opt==2)
            (add+=ask[k].val)%=p,s=((ll)s+(ll)n*ask[k].val)%p; else
        if (ask[k].opt==3)
            add=(ll)add*ask[k].val%p,mul=(ll)mul*ask[k].val%p,s=(ll)s*ask[k].val%p; else
        if (ask[k].opt==4)
            add=0,mul=1,nt=tot,allnum=ask[k].val,s=(ll)n*ask[k].val%p; else
        if (ask[k].opt==5)
            t=getpos(ask[k].x),ans+=((t==-1)?rval(allnum):rval(d2[t])); else
            ans+=s;
    }
    ans=(ans%p+p)%p;
    printf("%lld\n",ans);
    return 0;
}