ABC F
  • 板块学术版
  • 楼主LolaPeppa
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/9 20:58
  • 上次更新2024/6/9 21:40:32
查看原帖
ABC F
1314900
LolaPeppa楼主2024/6/9 20:58

求调,WA*34,非常感谢!

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 200010;
const ll P = 998244353;

int n, q;
ll a[N], b[N];
struct Node {
	int l, r;
	ll add1, add2, sum1, sum2, sum;
}tr[N << 2];

inline void pushup(int u) {
	tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % P;
}

inline void pushdown(int u) {
	if (tr[u].add1 && tr[u].add2) {
		tr[u << 1].sum = (tr[u << 1].sum + (tr[u].add1 * tr[u].add2 * (tr[u << 1].r - tr[u << 1].l + 1) % P) + (tr[u].add2 * tr[u << 1].sum1 % P) + (tr[u].add1 * tr[u << 1].sum2 % P)) % P;
		tr[u << 1].sum1 = (tr[u << 1].sum1 + tr[u].add1 * (tr[u << 1].r - tr[u << 1].l + 1)) % P;
		tr[u << 1].sum2 = (tr[u << 1].sum2 + tr[u].add2 * (tr[u << 1].r - tr[u << 1].l + 1)) % P;
		tr[u << 1].add1 = (tr[u << 1].add1 + tr[u].add1) % P;
		tr[u << 1].add2 = (tr[u << 1].add2 + tr[u].add2) % P;
		tr[u << 1 | 1].sum = (tr[u << 1 | 1].sum + (tr[u].add1 * tr[u].add2 * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) % P) + (tr[u].add2 * tr[u << 1 | 1].sum1 % P) + (tr[u].add1 * tr[u << 1 | 1].sum2 % P)) % P;
		tr[u << 1 | 1].sum1 = (tr[u << 1 | 1].sum1 + tr[u].add1 * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1)) % P;
		tr[u << 1 | 1].sum2 = (tr[u << 1 | 1].sum2 + tr[u].add2 * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1)) % P;
		tr[u << 1 | 1].add1 = (tr[u << 1 | 1].add1 + tr[u].add1) % P;
		tr[u << 1 | 1].add2 = (tr[u << 1 | 1].add2 + tr[u].add2) % P;
		tr[u].add1 = 0; tr[u].add2 = 0;
	}
	else if (tr[u].add1) {
		tr[u << 1].sum = (tr[u << 1].sum + tr[u].add1 * tr[u << 1].sum2) % P;
		tr[u << 1].sum1 = (tr[u << 1].sum1 + tr[u].add1 * (tr[u << 1].r - tr[u << 1].r + 1)) % P;
		tr[u << 1].add1 = tr[u].add1;
		tr[u << 1 | 1].sum = (tr[u << 1 | 1].sum + tr[u].add1 * tr[u << 1 | 1].sum2) % P;
		tr[u << 1 | 1].sum1 = (tr[u << 1 | 1].sum1 + tr[u].add1 * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1)) % P;
		tr[u << 1 | 1].add1 = tr[u].add1;
		tr[u].add1 = 0;
	}
	else if (tr[u].add2) {
		tr[u << 1].sum = (tr[u << 1].sum + tr[u].add2 * tr[u << 1].sum1) % P;
		tr[u << 1].sum2 = (tr[u << 1].sum2 + tr[u].add2 * (tr[u << 1].r - tr[u << 1].l + 1)) % P;
		tr[u << 1].add2 = (tr[u << 1].add2 + tr[u].add2) % P;
		tr[u << 1 | 1].sum = (tr[u << 1 | 1].sum + tr[u].add2 * tr[u << 1 | 1].sum1) % P;
		tr[u << 1 | 1].sum2 = (tr[u << 1 | 1].sum2 + tr[u].add2 * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1)) % P;
		tr[u << 1 | 1].add2 = (tr[u << 1 | 1].add2 + tr[u].add2) % P;
		tr[u].add2 = 0;
	}
}

inline void build(int u, int l, int r) {
	if (l == r) tr[u] = {l, r, 0, 0, a[r], b[r], a[r] * b[r]};
	else {
		int mid = (l + r) >> 1;
		tr[u].l = l, tr[u].r = r;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}

inline void modify(int u, int l, int r, int adda, int addb) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].sum = (tr[u].sum + (adda * addb * (tr[u].r - tr[u].l + 1) % P) + (addb * tr[u].sum1 % P) + (adda * tr[u].sum2 % P)) % P;
		tr[u].sum1 = (tr[u].sum1 + adda * (tr[u].r - tr[u].l + 1)) % P;
		tr[u].sum2 = (tr[u].sum2 + addb * (tr[u].r - tr[u].l + 1)) % P;
		tr[u].add1 = (tr[u].add1 + adda) % P;
		tr[u].add2 = (tr[u].add2 + addb) % P;
	}
	else {
		int mid = (tr[u].l + tr[u].r) >> 1;
		pushdown(u);
		if (l <= mid) modify(u << 1, l, r, adda, addb);
		if (r > mid) modify(u << 1 | 1, l, r, adda, addb);
		pushup(u);
	}
}

inline ll query(int u, int l, int r) {
	if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum % P;
	int mid = (tr[u].l + tr[u].r) >> 1; ll res = 0;
	pushdown(u);
	if (l <= mid) res = query(u << 1, l, r);
	if (r > mid) res = (res + query(u << 1 | 1, l, r)) % P;
	return res;
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
	for (int i = 1; i <= n; i ++ ) scanf("%lld", &b[i]);
	build(1, 1, n);
	while (q -- ) {
		int op, l, r;
		scanf("%d%d%d", &op, &l, &r);
		if (op == 1) {
			ll x; scanf("%lld", &x);
			modify(1, l, r, x, 0);
		} else if (op == 2) {
			ll x; scanf("%lld", &x);
			modify(1, l, r, 0, x);
		} else printf("%lld\n", query(1, l, r) % P);
	}
	return 0;
}
2024/6/9 20:58
加载中...