C++(clang++11) 解法, 执行用时: 304ms, 内存消耗: 10616K, 提交时间: 2021-01-24 22:05:33

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 998244353, a = 438914993, b = 736044383, c = 262199973;
int sum[N];
int n, m, x[N];
inline void mul(int &a, int b) { a = 1ll*a*b%mod; }
inline int Mul(int a, int b) { return 1ll*a*b%mod; }
inline void add(int &a, int b) { a+=b; if(a>=mod) a-=mod; }
inline int Add(int a, int b) { a+=b; if(a>=mod) return a-mod; return a; }
inline void sub(int &a, int b) { a-=b; if(a<0) a+=mod; }
inline int Sub(int a, int b) { a-=b; if(a<0) return a+mod; return a; }
int powmod(int a, int b)
{
	int ans = 1;
	while(b)
	{
		if(b&1) ans = Mul(ans, a);
		a = Mul(a, a);
		b >>= 1;
	}
	return ans;
}
struct SegTree
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	int inv, pw[N]; 
	struct seg
	{
		int l, r, sum, tag;
	}t[N<<2];
	void init(int q)
	{
		pw[0] = 1;
		for(int i=1; i<=n; i++) pw[i] = Mul(pw[i-1], q)%mod;
		inv = powmod(q-1, mod-2);
	}
	void setval(int p, int v)
	{
		add(t[p].sum, Mul(Mul(v, Sub(pw[t[p].r-t[p].l+1], 1)), inv));
		add(t[p].tag, v);
	}
	void pushup(int p)
	{
		t[p].sum = Add(t[ls].sum, t[rs].sum);
	}
	void pushdown(int p)
	{
		setval(ls, t[p].tag); setval(rs, Mul(t[p].tag, pw[t[rs].l-t[ls].l]));
		t[p].tag = 0;
	}
	void build(int p, int l, int r)
	{
		t[p].l = l, t[p].r = r;
		if(l==r) return;
		int mid = (l+r)>>1;
		build(ls, l, mid); build(rs, mid+1, r);
		pushup(p);
	}
	void upd(int p, int x, int y)
	{
		int l = t[p].l, r = t[p].r;
		if(l>=x && r<=y) 
		{
			setval(p, pw[l-x+1]);
			return;
		}
		if(t[p].tag) pushdown(p);
		int mid = (l+r)>>1;
		if(x<=mid) upd(ls, x, y);
		if(y>mid) upd(rs, x, y);
		pushup(p);
	}
	int ask(int p, int x, int y)
	{
		int l = t[p].l, r = t[p].r;
		if(l>=x && r<=y) return t[p].sum;
		if(t[p].tag) pushdown(p);
		int mid = (l+r)>>1, ans = 0;
		if(x<=mid) add(ans, ask(ls, x, y));
		if(y>mid) add(ans, ask(rs, x, y));
		return ans;
	}
	#undef ls
	#undef rs
}T1, T2;
int main()
{
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d", x+i);
	for(int i=1; i<=n; i++) sum[i] = Add(sum[i-1], x[i]);
	T1.init(b); T2.init(c);
	T1.build(1, 1, n); T2.build(1, 1, n);
	while(m--)
	{
		int op, l, r;
		scanf("%d%d%d", &op, &l, &r);
		if(op==1)
		{
			T1.upd(1, l, r);
			T2.upd(1, l, r);
		}
		else
		{
			int ans = Mul(Sub(T1.ask(1, l, r), T2.ask(1, l, r)), a);
			add(ans, Sub(sum[r], sum[l-1]));
			printf("%d\n", ans);
		}
	}
	return 0;
}