[SDOI2019]快速查询
[题目链接]
[思路要点]
据说是 ( ext{SDOI2019}) 最水的题
操作次数为 (1e7) 范围，显然要求每次操作 (mathcal{O}(1)) 完成
并不需要任何数据结构维护
由于不同的操作数量为 (1e5) 级别，可以将所有涉及到的变量离散化出来，并且使用数组直接存储，其它的一些变量全程中值都相同，只需要一个变量记录
如果没有全体赋值的操作，只需要记录一个 (A) 和 (B) 以及每个数的初值，表示当前某个数的值是其初值乘上 (A) 再加 (B)，对于单点修改操作，假设修改后的数是 (x)，完全可以将这个位置的初值改成 (y) 满足 (Ay+B=x)。由于 (A) 一定非零且模数为质数，所以这样的 (y) 一定存在，对于全体加和全体乘操作可以直接修改 (A) 和 (B) 的值
对于全体赋值，需要更改一下初值，同样很好实现
注意对于乘上 (0) 的操作，实质上是全体赋值，需要特殊处理
[代码]
// Copyright: lzt
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
typedef pair<int, pair<int, long long> > lzt;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int mod = 10000019;
const int maxn = 10001000;
int n, q, t, ans;
int fac[maxn], ifac[maxn], inv[maxn];
vector<int> vec;
inline void dd(int &x) {
x %= mod;
if (x < 0) x += mod;
}
struct Ope {
int tp;
int x, y;
inline void re() {
tp = read();
if (tp == 1) x = read(), y = read();
else if (tp != 6) x = read();
if (tp == 1) dd(y);
else if (tp != 6) dd(x);
if (tp == 3 && x == 0) tp = 4;
}
inline void pr() {
if (tp == 1) printf("%d %d %d
", tp, x, y);
else if (tp == 6) printf("%d
", tp);
else printf("%d %d
", tp, x);
}
} op[100100];
inline int ksm(int x, int p) {
int ret = 1;
while (p) {
if (p & 1) ret = ret * 1ll * x % mod;
p >>= 1; x = x * 1ll * x % mod;
}
return ret;
}
inline int getid(int x) {
return (int)(lower_bound(vec.begin(), vec.end(), x) - vec.begin()) + 1;
}
int sum, num, vv;
int A, B, tot = 1;
int val[1000100], nw[1000100];
inline void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
inline void sub(int &x, int y) {
x -= y;
if (x < 0) x += mod;
}
inline int fnd(int ind) {
if (nw[ind] == tot) return val[ind];
return vv;
}
inline int calc(int v) {
sub(v, B);
// cout<<"fuc"<<v<<' '<<A<<' '<<inv[A]<<endl;
return v * 1ll * inv[A] % mod;
}
inline void fuck(int x) {
// Debug("ans %d
", x);
add(ans, x);
}
inline void doit(int ind) {
Ope o = op[ind];// o.pr();
if (o.tp == 6) fuck((sum * 1ll * A + B * 1ll * n) % mod);
else if (o.tp == 1) {
sub(sum, fnd(o.x)), val[o.x] = calc(o.y), nw[o.x] = tot, add(sum, fnd(o.x));
// Debug("shit %d
", val[o.x]);
}
else if (o.tp == 2) B = (B + o.x) % mod;
else if (o.tp == 3) {
A = A * 1ll * o.x % mod;
B = B * 1ll * o.x % mod;
} else if (o.tp == 4) {
tot++;
sum = o.x * 1ll * n % mod;
A = 1; B = 0; vv = o.x;
} else fuck((fnd(o.x) * 1ll * A + B) % mod);
}
void work() {
fac[0] = 1; rep(i, 1, mod - 1) fac[i] = fac[i - 1] * 1ll * i % mod;
ifac[mod - 1] = ksm(fac[mod - 1], mod - 2); rrep(i, mod - 2, 0) ifac[i] = ifac[i + 1] * 1ll * (i + 1) % mod;
rep(i, 1, mod - 1) inv[i] = fac[i - 1] * 1ll * ifac[i] % mod;
n = read(); q = read();
rep(i, 1, q) {
op[i].re();
if (op[i].tp == 1 || op[i].tp == 5) vec.pb(op[i].x);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
// cout<<vec.size()<<endl;
rep(i, 1, q) if (op[i].tp == 1 || op[i].tp == 5) {
op[i].x = getid(op[i].x);
}
t = read(); A = 1; B = 0;
rep(i, 1, t) {
int a = read(), b = read();
rep(j, 1, q) {
int nw = (a + j * 1ll * b) % q + 1;
doit(nw);
}
}
printf("%d
", ans);
}
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
work();
#ifdef LZT
Debug("My Time: %.3lfms
", (double)clock() / CLOCKS_PER_SEC);
#endif
}