ABC357F求调
查看原帖
ABC357F求调
1028042
Jason_Harry_Song楼主2024/6/9 15:05

这个代码似乎没问题,但是错了30个点。

#include <bits/stdc++.h>
#define int long long
#define N 220000
using namespace std;
const int p = 998244353;
int n, q, a[N], b[N], opt, l, r, x;
struct Flag {
	int a, b;
	void operator += (Flag ot) {
		a = (a + ot.a) % p;
		b = (b + ot.b) % p;
		return;
	}
};
struct Node {
	int len, a, b, s;
	Node operator + (Node ot) {
		int rl, ra, rb, rs;
		rl = (len + ot.len) % p;
		ra = (a + ot.a) % p;
		rb = (b + ot.b) % p;
		rs = (s + ot.s) % p;
		return {rl, ra, rb, rs};
	}
	void operator += (Flag ot) {
		a = (a + (ot.a * len) % p) % p;
		b = (b + (ot.b * len) % p) % p;
		s = (s + (ot.a * b) % p + (ot.b * a) % p + (((ot.a * ot.b) % p) * len) % p) % p;
		return;
	}
};
struct SegmentTree {
	Node nd[N * 4];
	Flag fg[N * 4];
	void build(int id, int l, int r) {
		if (l == r) {
			nd[id] = {1, a[l], b[l], (a[l] * b[l]) % p};
			fg[id] = {0, 0};
			return;
		}
		int mid = (l + r) / 2;
		build(id * 2, l, mid);
		build(id * 2 + 1, mid + 1, r);
		nd[id] = nd[id * 2] + nd[id * 2 + 1];
		fg[id] = {0, 0};
		return;
	}
	void update(int id, int l, int r, int fl, int fr, Flag ch) {
		if (l == fl && r == fr) {
			nd[id] += ch;
			fg[id] += ch;
			return;
		}
		int mid = (l + r) / 2;
		nd[id * 2] += fg[id];
		fg[id * 2] += fg[id];
		nd[id * 2 + 1] += fg[id];
		fg[id * 2 + 1] += fg[id];
		fg[id] = {0, 0};
		if (fr <= mid) {
			update(id * 2, l, mid, fl, fr, ch);
		} else if (mid + 1 <= fl) {
			update(id * 2 + 1, mid + 1, r, fl, fr, ch);
		} else {
			update(id * 2, l, mid, fl, mid, ch);
			update(id * 2 + 1, mid + 1, r, mid + 1, fr, ch);
		}
		nd[id] = nd[id * 2] + nd[id * 2 + 1];
		return;
	}
	Node get_ans(int id, int l, int r, int fl, int fr) {
		if (l == fl && r == fr) {
			return nd[id];
		}
		int mid = (l + r) / 2;
		nd[id * 2] += fg[id];
		fg[id * 2] += fg[id];
		nd[id * 2 + 1] += fg[id];
		fg[id * 2 + 1] += fg[id];
		fg[id] = {0, 0};
		Node ret;
		if (fr <= mid) {
			ret = get_ans(id * 2, l, mid, fl, fr);
		} else if (mid + 1 <= fl) {
			ret = get_ans(id * 2 + 1, mid + 1, r, fl, fr);
		} else {
			ret = get_ans(id * 2 + 1, mid + 1, r, mid + 1, fr);
			ret = ret + get_ans(id * 2, l, mid, fl, mid);
		}
		nd[id] = nd[id * 2] + nd[id * 2 + 1];
		return ret;
	}
} st;
signed main() {
	scanf("%lld%lld", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		a[i] %= p;
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &b[i]);
		b[i] %= p;
	}
	st.build(1, 1, n);
	for (int i = 1; i <= q; i++) {
		scanf("%lld%lld%lld", &opt, &l, &r);
		if (opt == 1) {
			scanf("%lld", &x);
			x %= p;
			st.update(1, 1, n, l, r, {x, 0});
		} else if (opt == 2) {
			scanf("%lld", &x);
			x %= p;
			st.update(1, 1, n, l, r, {0, x});
		} else {
			printf("%lld\n", st.get_ans(1, 1, n, l, r).s % p);
		}
	}
	return 0;
}
2024/6/9 15:05
加载中...