Submission #37712082

---

Source Code Expand

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

pair<long long, long long> inv_gcd(long long a, long long b) {
	a %= b;
	if(a < 0) {
		a += b;
	}
	
	if(a == 0) return {b, 0};

	long long s = b, t = a;
	long long m0 = 0, m1 = 1;

	while(t) {
		long long u = s / t;
		s -= t * u;
		m0 -= m1 * u;
		swap(s, t);
		swap(m0, m1);
	}
	if(m0 < 0) m0 += b / s;
	return {s, m0};
}

template<int m>
class static_modint {
public:
	static constexpr int mod() {
		return m;
	}
 
	static_modint() : value(0) {}
 
	static_modint(long long v) {
		v %= mod();
		if(v < 0) {
			v += mod();
		}
		value = v;
	}
 
	const int& operator()() const {
		return value;
	}
 
	template<class T>
	explicit operator T() const {
		return static_cast<T>(value);
	}
 
	static_modint& operator+=(const static_modint& rhs) {
		value += rhs.value;
		if(value >= mod()) {
			value -= mod();
		}
		return *this;
	}
 
	static_modint& operator-=(const static_modint& rhs) {
		value -= rhs.value;
		if(value < 0) {
			value += mod();
		}
		return *this;
	}
 
	static_modint& operator*=(const static_modint& rhs) {
		value = (long long) value * rhs.value % mod();
		return *this;
	}
 
	static_modint& operator/=(const static_modint& rhs) {
		auto eg = inv_gcd(rhs.value, mod());
		assert(eg.first == 1);
		return *this *= eg.second;
	}
 
	template<class T>
	static_modint& operator+=(const T& rhs) {
		return *this += static_modint(rhs);
	}
 
	template<class T>
	static_modint& operator-=(const T& rhs) {
		return *this -= static_modint(rhs);
	}
 
	template<class T>
	static_modint& operator*=(const T& rhs) {
		return *this *= static_modint(rhs);
	}
 
	template<class T>
	static_modint& operator/=(const T& rhs) {
		return *this /= static_modint(rhs);
	}
 
	static_modint operator+() const {
		return *this;
	}
 
	static_modint operator-() const {
		return static_modint() - *this;
	}
 
	static_modint& operator++() {
		return *this += 1;
	}
 
	static_modint& operator--() {
		return *this -= 1;
	}
 
	static_modint operator++(int) {
		static_modint res(*this);
		*this += 1;
		return res;
	}
 
	static_modint operator--(int) {
		static_modint res(*this);
		*this -= 1;
		return res;
	}
 
	static_modint operator+(const static_modint& rhs) {
		return static_modint(*this) += rhs;
	}
 
	static_modint operator-(const static_modint& rhs) {
		return static_modint(*this) -= rhs;
	}
 
	static_modint operator*(const static_modint& rhs) {
		return static_modint(*this) *= rhs;
	}
 
	static_modint operator/(const static_modint& rhs) {
		return static_modint(*this) /= rhs;
	}
 
	inline bool operator==(const static_modint& rhs) const {
		return value == rhs();
	}
 
	inline bool operator!=(const static_modint& rhs) const {
		return !(*this == rhs);
	}

	static_modint pow(unsigned long long p) const {
		assert(p >= 0);
		static_modint res = 1;
		static_modint a(*this);
		while(p) {
			if(p & 1) {
				res *= a;
			}
			a *= a;
			p >>= 1;
		}
		return res;
	}

	static_modint inv() const {
		return 1 / static_modint(*this);
	}
 
private:
	int value;
};
 
template<int m, class T> static_modint<m> operator+(const T& lhs, const static_modint<m>& rhs) {
	return static_modint<m>(lhs) += rhs;
}
 
template<int m, class T> static_modint<m> operator-(const T& lhs, const static_modint<m>& rhs) {
	return static_modint<m>(lhs) -= rhs;
}
 
template<int m, class T> static_modint<m> operator*(const T& lhs, const static_modint<m>& rhs) {
	return static_modint<m>(lhs) *= rhs;
}
 
template<int m, class T> static_modint<m> operator/(const T& lhs, const static_modint<m>& rhs) {
	return static_modint<m>(lhs) /= rhs;
}
 
template<int m>
istream& operator>>(istream& in, static_modint<m>& num) {
	long long x;
	in >> x;
	num = static_modint<m>(x);
	return in;
}
 
template<int m>
ostream& operator<<(ostream& out, const static_modint<m>& num) {
	return out << num();
}

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;

template<class S,
         S (*e)(),
         S (*op)(S, S),
         class F,
         F (*id)(),
         S (*mapping)(F, S),
         F (*composition)(F, F)>
class lazy_segtree {
public:
	lazy_segtree() : lazy_segtree(0) {}

	explicit lazy_segtree(int _n) : lazy_segtree(vector<S>(_n, e())) {}

	explicit lazy_segtree(const vector<S>& v) : n((int) v.size()) {
		log = 31 - __builtin_clz(2 * n - 1);
		size = 1 << log;
		d = vector<S>(size << 1, e());
		lz = vector<F>(size, id());
		for(int i = 0; i < n; i++) {
			d[size + i] = v[i];
		}
		for(int i = size - 1; i; --i) {
			update(i);
		}
	}

	void set(int p, S x) {
		assert(0 <= p && p < n);
		p += size;
		for(int i = log; i; --i) {
			push(p >> i);
		}
		d[p] = x;
		for(int i = 1; i <= log; ++i) {
			update(p >> i);
		}
	}

	S get(int p) {
		assert(0 <= p && p < n);
		p += size;
		for(int i = log; i; i--) {
			push(p >> i);
		}
		return d[p];
	}

	S operator[](int p) {
		return get(p);
	}

	S prod(int l, int r) {
		assert(0 <= l && l <= r && r <= n);
		if(l == r) {
			return e();
		}
		l += size;
		r += size;
		for(int i = log; i; i--) {
			if(((l >> i) << i) != l) {
				push(l >> i);
			}
			if(((r >> i) << i) != r) {
				push(r >> i);
			}
		}
		S sml = e(), smr = e();
		while(l < r) {
			if(l & 1) {
				sml = op(sml, d[l++]);
			}
			if(r & 1) {
				smr = op(d[--r], smr);
			}
			l >>= 1;
			r >>= 1;
		}
		return op(sml, smr);
	}

	S all_prod() const { return d[1]; }

	void apply(int p, F f) {
		assert(0 <= p && p < n);
		p += size;
		for(int i = log; i; i--) {
			push(p >> i);
		}
		d[p] = mapping(f, d[p]);
		for(int i = 1; i <= log; i++) {
			update(p >> i);
		}
	}
	void apply(int l, int r, F f) {
		assert(0 <= l && l <= r && r <= n);
		if(l == r) {
			return;
		}
		l += size;
		r += size;
		for(int i = log; i; i--) {
			if(((l >> i) << i) != l) {
				push(l >> i);
			}
			if(((r >> i) << i) != r) {
				push((r - 1) >> i);
			}
		}
		{
			int l2 = l, r2 = r;
			while(l < r) {
				if(l & 1) {
					all_apply(l++, f);
				}
				if(r & 1) {
					all_apply(--r, f);
				}
				l >>= 1;
				r >>= 1;
			}
			l = l2;
			r = r2;
		}
		for(int i = 1; i <= log; i++) {
			if(((l >> i) << i) != l) {
				update(l >> i);
			}
			if(((r >> i) << i) != r) {
				update((r - 1) >> i);
			}
		}
	}

	template<bool (*g)(S)> int max_right(int l) {
		return max_right(l, [](S x) { return g(x); });
	}

	template<class G> int max_right(int l, G g) {
		assert(0 <= l && l <= n);
		assert(g(e()));
		if(l == n) {
			return n;
		}
		l += size;
		for(int i = log; i; i--) {
			push(l >> i);
		}
		S sm = e();
		do {
			while(!(l & 1)) {
				l >>= 1;
			}
			if(!g(op(sm, d[l]))) {
				while(l < size) {
					push(l);
					l <<= 1;
					if(g(op(sm, d[l]))) {
						sm = op(sm, d[l]);
						l++;
					}
				}
				return l - size;
			}
			sm = op(sm, d[l]);
			l++;
		} while((l & -l) != l);
		return n;
	}

	template<bool (*g)(S)> int min_left(int r) {
		return min_left(r, [](S x) { return g(x); });
	}

	template<class G> int min_left(int r, G g) {
		assert(0 <= r && r <= n);
		assert(g(e()));
		if(r == 0) {
			return 0;
		}
		r += size;
		for(int i = log; i >= 1; i--) {
			push((r - 1) >> i);
		}
		S sm = e();
		do {
			r--;
			while(r > 1 && (r & 1)) {
				r >>= 1;
			}
			if(!g(op(d[r], sm))) {
				while(r < size) {
					push(r);
					r = r << 1 | 1;
					if(g(op(d[r], sm))) {
						sm = op(d[r], sm);
						r--;
					}
				}
				return r + 1 - size;
			}
			sm = op(d[r], sm);
		} while((r & -r) != r);
		return 0;
	}

private:
	int n, size, log;
	vector<S> d;
	vector<F> lz;

	inline void update(int k) { d[k] = op(d[k << 1], d[k << 1 | 1]); }

	void all_apply(int k, F f) {
		d[k] = mapping(f, d[k]);
		if(k < size) {
			lz[k] = composition(f, lz[k]);
		}
	}

	void push(int k) {
		all_apply(k << 1, lz[k]);
		all_apply(k << 1 | 1, lz[k]);
		lz[k] = id();
	}
};

using mint = modint998244353;

const mint inv2 = mint(1) / 2;

struct S {
	mint val = 0;
	int l = INT_MAX;
	int r = INT_MIN;

	S() {}
	S(mint a, int b, int c) : val(a), l(b), r(c) {}
};

S e() {
	return S();
}

S op(S a, S b) {
	return S(a.val + b.val, min(a.l, b.l), max(a.r, b.r));
}

struct F {
	int pos = -1;
	mint a0 = 0;
	mint d = 0;

	F() {}
	F(int a, mint b, mint c) : pos(a), a0(b), d(c) {}
};

F id() {
	return F();
}

S mapping(F f, S s) {
	mint head = f.a0 + (s.l - f.pos) * f.d;
	mint tail = f.a0 + (s.r - f.pos) * f.d;
	int sz = s.r - s.l + 1;
	s.val += (head + tail) * sz * inv2;
	return s;
}

F composition(F a, F b) {
	if(a.pos == -1 || b.pos == -1) {
		return a.pos == -1 ? b : a;
	}
	b.a0 += a.a0 + (b.pos - a.pos) * a.d;
	b.d += a.d;
	return b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	lazy_segtree<S, e, op, F, id, mapping, composition> seg(n);
	for(int i = 0; i < n; ++i) {
		seg.set(i, S(0, i, i));
	}
	vector<long long> a(n);
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		seg.apply(i, n, F(i, mint(a[i]), mint(a[i])));
	}
	while(q--) {
		int t, p;
		cin >> t >> p;
		--p;
		if(t == 1) {
			long long val;
			cin >> val;
			long long dif = val - a[p];
			seg.apply(p, n, F(p, mint(dif), mint(dif)));
			a[p] += dif;
		} else {
			cout << seg.prod(0, p + 1).val << "\n";
		}
	}
	return 0;
}

Submission Info

Judge Result