P5358 [SDOI2019]快速查询
SDOI2019D1T1
我自闭了,所以感想很简单:SDOI二轮果然还是没了好
-
1 i val :将 赋值为给定整数 ;
-
2 val :将所有元素同时加上 ;
-
3 val :将所有元素同时乘上 ;
-
4 val :将所有元素同时赋值为 ;
-
5 i :询问第 个元素 现在的值是多少;
-
6 :询问现在所有元素的和。
n<=1e9,p<=1e7
暴力就不用说了吧?动态开点线段树,挂个log,神威太湖之光跑起来轻轻松松
说正解:这个题就是打标记
首先你会发现我们有1e9个数但是只有1e7个询问或者修改,也就是说本质不同的数数量小于1e7,而且我们最多也就支持个单点查询,所以只需要维护每个数就好了
他们的编号是1e9级别?手写一个哈希表存一下就行了...什么?你哈希表模数被卡了?那我只能/kk
然后这样单点查询和单点赋值就支持了,再考虑全局加乘,不难发现我们只需要打个标记就能解决他和单点操作的兼容??
并不是这样,我们还是要推式子,设hash表里存,乘法标记为,加法标记为
然后某数真实值是
现在要改成tmp,但我们hash表内要存x,
并不过瘾,但是这就够了,另外如果您是带师那么考虑在每个hash值上再多存一点东西替代推这个式子也是可以的,因为这个东西要算逆元,逆元是有坑的
然后再考虑全局赋值和单点兼容性问题.....
首先乘法标记和加法标记要清空,然后打上一个赋值标记,而且好像还要考虑在这之后的单点赋值标记又能够覆盖了他...?
这里其实只需要在每个hash值处记录一下"时间"信息,然后我们发现有现成的数组,就是hash表中那个记当前有多少条边的那个,那正好也代表了边出现的顺序,所以只需要用那玩意记录一下时间信息就好了
然后你会发现我们都兼容了,所以这个题就做完了.只需要100行左右哦,快去写吧
好吧我最后再多调了1个多h才做完/kk
code:
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
#define ULL unsigned long long
#define ll long long
const int MOD = 1e7 + 19;
const int MAXN = 2e5 + 7;
const int P = 1e7 + 19;
struct rec {
ll a, b, c;
} q[MAXN];
ll fac[P + 10], ifac[P + 10], inv[P + 10];
ll sum, ans, nt, nfzv, mul, add, n, Q;
int a[MAXN], b[MAXN];
struct H_SH {
struct edge {
ll x;
ULL rx;
ll nxt;
} e[21000000];
int home[MOD + 1], cnt_e;
void add(ULL x, ll d) {
int u = (x % MOD) + 1;
// for(int i = home[u]; i; i = e[i].nxt) {
// if(e[i].x == x) { //
// e[i].cnt += d;
// return ;
// }
// }
e[++cnt_e] = (edge) {
d, x, home[u]
};
home[u] = cnt_e;
//老八蜜汁哈希表
}
ll query(ULL x, int &o) {
int u = (x % MOD) + 1;
for(int i = home[u]; i; i = e[i].nxt) {
if(e[i].rx == x) {
o = i;
return e[i].x;
}
}
o = 0;
return 1e18;
}
} _;
inline void ddfz(int pos, int val) {
int lst;
ll V = _.query(pos, lst);
// printf("%lld %lld %lld %lld#\n", pos, val, V, lst);
if(nt >= lst) {
sum = (sum - nfzv * mul % P - add + P) % P;
} else {
sum = (sum - V * mul % P - add + P ) % P;
}
//和要减去之前的
ll opr = (((val - add) % P + P) % P * inv[(mul + P) % P]) % P;
// printf("%lld &\n", opr);
//反演
_.add(pos, opr);
sum = (sum + val) % P;
}
inline void Aadd(ll x) {
add = (add + x) % P;
sum = (sum + n * x % P) % P;
}
inline void Amul(ll x) {
add = (add * x) % P;
mul = (mul * x) % P;
sum = (sum * x) % P;
}
inline void Afz(ll x) {
nt = _.cnt_e;
nfzv = x;
add = 0;
mul = 1;
sum = (nfzv * n) % P;
}
inline void query(int x) {
int lst;
ll V = _.query(x, lst);
// printf("%lld %lld?\n", V, lst);
if(nt >= lst) {
ans = (ans + nfzv * mul % P + add) % P;
} else {
ans = (ans + V * mul % P + add) % P;
}
}
inline void solve(int x) {
// printf("%d?\n", x);
if(q[x].a == 1)
ddfz(q[x].c, q[x].b);
else if(q[x].a == 2)
Aadd(q[x].b);
else if(q[x].a == 3)
Amul(q[x].b);
else if(q[x].a == 4)
Afz(q[x].b);
else if(q[x].a == 5)
query(q[x].b);
else ans = (ans + sum) % P;
// printf("%lld %lld %lld\n", sum, mul, add);
}
inline ll ksm(ll x, ll y) {
ll ans = 1;
while(y) {
if(y & 1)ans = ans * x % P;
x = x * x % P;
y >>= 1;
}
return ans;
}
inline void init() {
// fac[0] = fac[1] = 1;
// ifac[0] = ifac[1] = 1;
// for(register int i = 2; i < P; ++i) {
// fac[i] = fac[i - 1] * i % P;
// }
// fac[P - 1] = ksm(fac[P - 1], P - 2);
// for(register int i = P - 2; i >= 2; --i) {
// ifac[i] = ifac[i + 1] * (i + 1) % P;
// inv[i + 1] = fac[i + 1] * ifac[i] % P;
// }
// inv[2] = fac[2] * ifac[1] % P;
// printf("%lld?\n", inv[2]);
inv[0] = inv[1] = 1;
for (ll i = 2; i <= P - 1; i++) {
inv[i] = (((P - P / i) % P) * inv[P % i]) % P;
}
return ;
}
signed main() {
//freopen("test.in", "r", stdin);
mul = 1;
init();
scanf("%lld%lld", &n, &Q);
for(register int i = 1; i <= Q; ++i) {
scanf("%lld", &q[i].a);
if(q[i].a == 1)scanf("%lld%lld", &q[i].c, &q[i].b);
else if(q[i].a != 6) {
scanf("%lld", &q[i].b);
}
if(q[i].a != 5)q[i].b %= P;
} int t;
scanf("%lld", &t);
for(register int i = 1; i <= t; ++i)scanf("%lld%lld", &a[i], &b[i]);
//puts("qwq");
for(register int i = 1; i <= t; ++i) {
for(register int j = 1; j <= Q; ++j) {
solve((a[i] + j * b[i] % Q) % Q + 1);
}
// printf("???\n");
}
printf("%lld\n", (ans % P + P) % P);
return 0;
}
尼康不见我,我恨凯信