P5358 [SDOI2019]快速查询

思路：。。。乱搞数据结构？？

提交：1次

题解：

观察到除了单点就是全局操作，所以我们维护一个全局加法标记add和乘法标记mul和答案sum。

单点修改时，比如我们要把 \(pos\) 位置改成 \(y\) ，实际上我们应该储存 \(x\) , 且 \(y=mul*x+add\) ，即我们储存的是逆标记操作后的值。

同时要注意全体赋值后标记和 unordered_map 的清空。

代码：自带大常数

#include<bits/stdc++.h>

#define ll long long

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

  register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

  do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;

} const int N=100010,M=1e7+19;

int A,B,n,q,t,add,mul,sum,Inv[M],cvl,ans;

unordered_map<int,int> d;

struct node {int op,p,vl;}a[N];

inline void calc(int x) {

  if(a[x].op==1) {

    R tmp=a[x].vl,dec; tmp=1ll*((tmp-add)%M+M)%M*Inv[mul]%M;

    if(d.count(a[x].p)) dec=(1ll*d[a[x].p]*mul+add)%M;

    else dec=(1ll*mul*cvl+add)%M;

    d[a[x].p]=tmp; sum=(1ll*sum+a[x].vl-dec+M)%M;

  } if(a[x].op==2) add=(add+a[x].vl)%M,sum=(sum+1ll*n*a[x].vl)%M;

  if(a[x].op==3) add=1ll*add*a[x].vl%M,mul=1ll*mul*a[x].vl%M,sum=1ll*sum*a[x].vl%M;

  if(a[x].op==4) d.clear(),cvl=a[x].vl,add=0,mul=1,sum=1ll*n*a[x].vl%M;

  if(a[x].op==5) {

    if(!d.count(a[x].vl)) ans=(ans+1ll*mul*cvl+add)%M;

    else ans=(ans+1ll*mul*d[a[x].vl]+add)%M;

  } if(a[x].op==6) ans=(ans+sum)%M;

}

inline void main() {

  Inv[1]=1; for(R i=2;i<M;++i) Inv[i]=M-1ll*M/i*Inv[M%i]%M;

  n=g(),q=g(); for(R i=1;i<=q;++i) {

    a[i].op=g(); if(a[i].op==1) a[i].p=g();

    else if(a[i].op==6) continue; a[i].vl=(g()%M+M)%M;

  } t=g(); for(R i=1;i<=t;++i) {

    A=g(),B=g();

    for(R j=1,c;j<=q;++j)

      c=(A+1ll*j*B)%q+1,calc(c);

  } printf("%d\n",(ans%M+M)%M);

}

} signed main() {Luitaryi::main(); return 0;}

2019.09.15

61

巴特西

P5358 [SDOI2019]快速查询

思路：。。。乱搞数据结构？？

提交：1次

题解：

代码：自带大常数

最新文章

热门文章