12tqian's Competitive Programming Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub 12tqian/cp-library

:heavy_check_mark: verify/codeforces/codeforces-981G.test.cpp

Depends on

Code

#define PROBLEM "https://codeforces.com/contest/981/problem/G"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/data-structures/1d-range-queries/affine-segment-tree.hpp"
#include "../../library/modular-arithmetic/mod-int2.hpp"
#include "../../library/data-structures/1d-range-queries/interval-union.hpp"

using mi = Mint<998244353, 5>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); 
	int n, q;
	cin >> n >> q;
	vector<IntervalUnion<int>> iu(n);
	AffineSegmentTree<mi> seg;
	seg.init(n);
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int l, r, x;
			cin >> l >> r >> x;
			--l, --r, --x;
			vector<pair<int, int>> use = iu[x].insert({l, r});
			for (auto &y : use) {
				seg.upd(1, max(l, y.first), min(r, y.second), 2);
			}
			if (!use.empty()) {
				for (int i = 0; i < use.size() + 1; ++i) {
					if (i == 0) {
						seg.upd(0, l, use[i].first - 1, 1);
					} else if (i != use.size()) {
						seg.upd(0, use[i - 1].second + 1, use[i].first - 1, 1);
					} else {
						seg.upd(0, use[i - 1].second + 1, r, 1);
					}
				}
			} else {
				seg.upd(0, l, r, 1);
			}
		} else {
			int l, r;
			cin >> l >> r;
			--l, --r;
			cout << seg.qsum(l, r) << '\n';
		}
	}
	return 0;
}
#define PROBLEM "https://codeforces.com/contest/981/problem/G"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <class T> struct AffineSegmentTree {
	int sz;
	std::vector<T> sum, mult, add;

	void push(int ind, int L, int R) { // modify values for current node

		sum[ind] *= mult[ind]; sum[ind] += (R - L + 1) * add[ind];
		if (L != R) {
			mult[2 * ind] *= mult[ind]; mult[2 * ind + 1] *= mult[ind];
			add[2 * ind] *= mult[ind]; add[2 * ind] += add[ind];
			add[2 * ind + 1] *= mult[ind]; add[2 * ind + 1] += add[ind];
		}
		add[ind] = 0; mult[ind] = 1;
	}

	void init(int n) {
		sz = 1;
		while (sz < n) sz *= 2;
		mult.assign(2 * sz, 1);
		sum.assign(2 * sz, 0);
		add.assign(2 * sz, 0);
	}

	void pull(int ind) {
		sum[ind] = sum[2 * ind] + sum[2 * ind + 1];
	}

	// t == 0 is add, t == 1 is for multiplying

	void upd(int t, int lo, int hi, T inc, int ind = 1, int L = 0, int R = -1) {
		if (R == -1) R += sz;
		push(ind, L, R);
		if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) {
			if(t == 0) add[ind] = inc;  
			else mult[ind] = inc;
			push(ind, L, R); return;
		}
		int M = (L + R) / 2;
		upd(t, lo, hi, inc, 2 * ind, L, M); upd(t, lo, hi, inc, 2 * ind + 1, M + 1, R);
		pull(ind);
	}
	
	T qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
		if (R == -1) R += sz;
		push(ind, L, R);
		if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return sum[ind];
		int M = (L + R) / 2;
		return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
	}
};

// 5 is a root of both mods

template <int MOD, int RT> struct Mint {
	static const int mod = MOD;
	static constexpr Mint rt() { return RT; } // primitive root for FFT

	static constexpr int md() { return MOD; } // primitive root for FFT

	int v; 
	explicit operator int() const { return v; } // explicit -> don't silently convert to int

	explicit operator bool() const { return v != 0; }
	Mint() { v = 0; }
	Mint(long long _v) { v = int((-MOD <= _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.v == b.v; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
	friend bool operator>(const Mint& a, const Mint& b) { return a.v > b.v; }
	friend bool operator<=(const Mint& a, const Mint& b) { return a.v <= b.v; }
	friend bool operator>=(const Mint& a, const Mint& b) { return a.v >= b.v; }
	friend std::istream& operator >> (std::istream& in, Mint& a) { 
		long long x; std::cin >> x; a = Mint(x); return in; }
	friend std::ostream& operator << (std::ostream& os, const Mint& a) { return os << a.v; }
	Mint& operator+=(const Mint& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	Mint& operator-=(const Mint& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	Mint& operator*=(const Mint& m) { 
		v = (long long)v * m.v % MOD; return *this; }
	Mint& operator/=(const Mint& m) { return (*this) *= inv(m); }
	friend Mint pow(Mint a, long long p) {
		Mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans; 
	}
	friend Mint inv(const Mint& a) { assert(a.v != 0); return pow(a, MOD - 2); }
	Mint operator-() const { return Mint(-v); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
};

template <class T> struct IntervalUnion {
	const T INF = std::numeric_limits<T>::max();
	std::set<std::pair<T, T>> le, ri;

	void reset() {
		le.clear();
		ri.clear();
	}

	// inserts an interval while returning the intervals it intersected with

	std::vector<std::pair<T, T>> insert(std::pair<T, T> x) {
		std::set<std::pair<T, T>> bad;
		std::vector<std::pair<T, T>> ret;
		std::pair<T, T> use1 = {x.first, -INF}, use2 = {x.second, INF};
		auto it1 = le.lower_bound(use1);
		auto it2 = ri.lower_bound(use2);
		if (it2 != ri.end()) {
			T lo = it2->second, hi = it2->first;
			if (lo <= x.first && x.second <= hi) {
				ret.emplace_back(lo, hi);
				T mn = x.first, mx = x.second;
				for (auto& b : ret) {
					le.erase(b); ri.erase({b.second, b.first});
					mn = std::min(mn, b.first); mx = std::max(mx, b.second);
				}
				le.emplace(mn, mx); ri.emplace(mx, mn);
				return ret;
			}
		}
		if (it1 != le.end()) {
			while (it1 != le.end()) {
				auto val = (*it1);
				if (val.first <= x.second) bad.insert(val);
				else break;
				it1 = next(it1);
			}
		}
		if (it2 != ri.begin()) {
			it2 = prev(it2);
			while (true) {
				auto val = *it2;
				if (val.first >= x.first) bad.emplace(val.second, val.first);
				else break;
				if (it2 == ri.begin()) break;
				it2 = prev(it2);
			}
		}
		for (auto& b : bad) ret.emplace_back(b);
		T mn = x.first, mx = x.second;
		for (auto& b : ret) {
			le.erase(b); ri.erase({b.second, b.first});
			mn = std::min(mn, b.first); mx = std::max(mx, b.second);
		}
		le.emplace(mn, mx); ri.emplace(mx, mn);
		return ret;
	}
};

using mi = Mint<998244353, 5>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); 
	int n, q;
	cin >> n >> q;
	vector<IntervalUnion<int>> iu(n);
	AffineSegmentTree<mi> seg;
	seg.init(n);
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int l, r, x;
			cin >> l >> r >> x;
			--l, --r, --x;
			vector<pair<int, int>> use = iu[x].insert({l, r});
			for (auto &y : use) {
				seg.upd(1, max(l, y.first), min(r, y.second), 2);
			}
			if (!use.empty()) {
				for (int i = 0; i < use.size() + 1; ++i) {
					if (i == 0) {
						seg.upd(0, l, use[i].first - 1, 1);
					} else if (i != use.size()) {
						seg.upd(0, use[i - 1].second + 1, use[i].first - 1, 1);
					} else {
						seg.upd(0, use[i - 1].second + 1, r, 1);
					}
				}
			} else {
				seg.upd(0, l, r, 1);
			}
		} else {
			int l, r;
			cin >> l >> r;
			--l, --r;
			cout << seg.qsum(l, r) << '\n';
		}
	}
	return 0;
}
Back to top page