C++ 解法, 执行用时: 678ms, 内存消耗: 22164K, 提交时间: 2021-12-18 21:28:23

#include <bits/stdc++.h>
using namespace std;

typedef long long s64;
const int N = 2e5 + 5, B = 300, D = 998244353;
int a[N];
s64 s0[N], ss0[N], s1[N];
int q1[N], rk1[N];

namespace Block {
	const int L = N / B + 5;
	int s0[N], a0[N];
	s64 s1[N], a1[N];
	void clear() {
		for (int i = 0; i < N; ++i) s0[i] = a0[i] = s1[i] = a1[i] = 0;
	}
	void add(int i, int w) { //add suf
		int j = (i / B + 1) * B - 1;
		while (i <= j) {
			a0[i]++;
			(a1[i] += w) %= D;
			++i;
		}
		i = j / B + 1;
		while (i < L) {
			s0[i]++;
			(s1[i] += w) %= D;
			++i;
		}
	}
	int query(int i, int w) {
		int j = i / B;
		//	if (i == 1) cout << "Q " << i << " " << a0[i] << " " << w << endl;
		return (w * s64(a0[i] + s0[j]) - a1[i] - s1[j]) % D;
	}
};

struct Query {
	int l, r, i;
} query[N];
s64 ans[N], del[N], p0[N], p1[N];
vector<tuple<int, int, int>> lk_r[N]; //(l,r,i*(-1)^w)

int n, m;
void work() {
	Block::clear();
	for (int i = 0; i <= n; ++i) {
		if (i) {
			p1[i] = (p1[i - 1] + Block::query(rk1[i], s1[i])) % D;
			p0[i] = (p0[i - 1] + s0[i] * i - ss0[i - 1]) % D;
			//cout << p0[i] << " " << p1[i] << " " << s1[i] << " " << rk1[i] << endl;
		}
		for (auto [l, r, j]: lk_r[i]) {
			s64 sum = 0;
			if (i) sum = ((ss0[r] - ss0[l - 1]) * i - ss0[i - 1] * (r - l + 1)) % D;
			//cout << i << " " << l << " " << r << sum << endl;
			for (int k = l; k <= r; ++k) sum += Block::query(rk1[k], s1[k]);
			(del[abs(j)] += j > 0 ? sum : -sum) %= D;
		}
		Block::add(rk1[i], s1[i]);
	}
	for (int i = 0; i <= n; ++i)
		for (auto [l, r, j]: lk_r[i]) {
			s64 sum = p1[r] - p1[l - 1] + p0[r] - p0[l - 1];
			(del[abs(j)] += j > 0 ? -sum : sum) %= D;
		}
	for (int i = 1; i <= m; ++i) {
		(del[i] += del[i - 1]) %= D;
		(ans[query[i].i] += del[i]) %= D;
	}
}
void work_r(bool d) {
	for (int i = 1; i <= n; ++i) {
		int j = i;
		if (d) j = n - j + 1;
		s0[i] = (s0[i - 1] + j % 2 * a[i]) % D;
		ss0[i] = (ss0[i - 1] + s0[i]) % D;
		s1[i] = (s1[i - 1] + (j % 2 ? -a[i] : a[i]));
		q1[i] = i;
	}
	q1[0] = 0;
	sort(q1 + 0, q1 + n + 1, [&](int x, int y) {
		return s1[x] < s1[y];
	});
	for (int i = 0; i <= n; ++i) {
		rk1[q1[i]] = i;
		s1[i] %= D;
	}
	for (int i = 0; i <= n; ++i) lk_r[i].clear();
	int nl = 1, nr = 0;
	if (d) swap(nl = n - nl + 1, nr = n - nr + 1);
	for (int i = 1; i <= m; ++i) {
		del[i] = 0;
		int l = query[i].l, r = query[i].r;
		if (!d) {
			if (nr < r) {
				lk_r[nl - 1].push_back({ nr + 1, r, -i });
				nr = r;
			}
			if (nl > l) {
				nl = l;
			}
			if (nr > r) {
				lk_r[nl - 1].push_back({ r + 1, nr, i });
				nr = r;
			}
			if (nl < l) {
				nl = l;
			}
		} else {
			if (nl > l) {
				nl = l;
			}
			if (nr < r) {
				lk_r[nl - 1].push_back({ nr + 1, r, -i });
				nr = r;
			}
			if (nl < l) {
				nl = l;
			}
			if (nr > r) {
				lk_r[nl - 1].push_back({ r + 1, nr, i });
				nr = r;
			}
		}
	}
	work();
}

int main() {
#ifdef kcz
	freopen("1.in", "r", stdin); //freopen("1.out","w",stdout);
#endif
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		scanf("%d", a + i);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &query[i].l, &query[i].r);
		query[i].i = i;
	}
	sort(query + 1, query + m + 1, [&](Query a, Query b) {
		int i = a.l / B;
		if (i != b.l / B) return i < b.l / B;
		if (i % 2) return a.r > b.r;
		return a.r < b.r;
	});
	work_r(0);
	reverse(a + 1, a + n + 1);
	for (int i = 1; i <= m; ++i) {
		swap(query[i].l = n - query[i].l + 1, query[i].r = n - query[i].r + 1);
	}
	work_r(1);
	for (int i = 1; i <= m; ++i) printf("%d\n", int((ans[i] % D + D) % D));
}