P5358 [SDOI2019]快速查询

SDOI2019D1T1

P站真好

我自闭了,所以感想很简单:SDOI二轮果然还是没了好

  • 1 i val :将 aia_i​ 赋值为给定整数 valval

  • 2 val :将所有元素同时加上 valval

  • 3 val :将所有元素同时乘上 valval

  • 4 val :将所有元素同时赋值为 valval

  • 5 i :询问第 ii 个元素 aiai​ 现在的值是多少;

  • 6 :询问现在所有元素的和。

n<=1e9,p<=1e7

暴力就不用说了吧?动态开点线段树,挂个log,神威太湖之光跑起来轻轻松松

说正解:这个题就是打标记

首先你会发现我们有1e9个数但是只有1e7个询问或者修改,也就是说本质不同的数数量小于1e7,而且我们最多也就支持个单点查询,所以只需要维护每个数就好了

他们的编号是1e9级别?手写一个哈希表存一下就行了...什么?你哈希表模数被卡了?那我只能/kk

然后这样单点查询和单点赋值就支持了,再考虑全局加乘,不难发现我们只需要打个标记就能解决他和单点操作的兼容??

并不是这样,我们还是要推式子,设hash表里存valval,乘法标记为mulmul,加法标记为addadd

然后某数真实值是valmul+addval*mul+add

现在要改成tmp,但我们hash表内要存x,tmp=valx+addtmp=val*x+add

x=tmpaddvalx=\frac{tmp-add}{val}

并不过瘾,但是这就够了,另外如果您是带师那么考虑在每个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;
}

尼康不见我,我恨凯信