verify/codeforces/codeforces-869E-general-fwt.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://codeforces.com/contest/869/problem/E

Depends on

Code

#define PROBLEM "https://codeforces.com/contest/869/problem/E"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/data-structures/2d-range-queries/general-fenwick-tree.hpp"
#include "../../library/modular-arithmetic/mod-int2.hpp"

const int N = 2505;

const int P = 998244353;
const int B = 2;

using mi = Mint<998244353, 5>;

BIT<mi, N, N> bit;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, q;
	cin >> m >> m >> q;
	map<array<int, 4>, mi> rects;
	mi run = 1;
	while (q--) {
		int t, xl, xr, yl, yr;
		cin >> t >> xl >> yl >> xr >> yr;
		auto rect = [&]() {
			mi v;
			if (t == 1) {
				rects[{xl, xr, yl, yr}] = run;
				v = run;
				run *= 2;
			} else {
				v = rects[{xl, xr, yl, yr}];
				v *= -1;
			}
			bit.upd(xl, yl, v);
			bit.upd(xl, yr + 1, -v);
			bit.upd(xr + 1, yl, -v);
			bit.upd(xr + 1, yr + 1, v);
		};
		if (t <= 2) {
			rect();
		} else {	
			if (bit.query(1, xl, 1, yl) == bit.query(1, xr, 1, yr)) {
				cout << "Yes" << '\n';
			} else {
				cout << "No" << '\n';
			}
		}
	}
	return 0;
}

#define PROBLEM "https://codeforces.com/contest/869/problem/E"


#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;

constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); } 

template <class T, int ...Ns> struct BIT {
	T val = 0; void upd(T v) { val += v; }
	T query() { return val; }
};

template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
	BIT<T, Ns...> bit[N + 1];

	template <typename... Args> void upd(int pos, Args... args) { 
		assert(pos > 0);
		for (; pos <= N; pos += pos & -pos) 
			bit[pos].upd(args...); 
	}

	template <typename... Args> T sum(int r, Args... args) {
		T res = 0; 
		for (; r; r -= r & -r) 
			res += bit[r].query(args...); 
		return res; 
	}

	template <typename... Args> T query(int l, int r, Args... args) { 
		return sum(r, args...) - sum(l - 1, args...); 
	}

	int get_kth(T des) { 
		assert(des > 0);
		int ind = 0;
		for (int i = 1 << bits(N); i; i /= 2)
			if (ind + i <= N && bit[ind + i].val < des)
				des -= bit[ind += i].val;
		assert(ind < N); return ind + 1;
	}
}; 


// 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; }
};

const int N = 2505;

const int P = 998244353;
const int B = 2;

using mi = Mint<998244353, 5>;

BIT<mi, N, N> bit;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, q;
	cin >> m >> m >> q;
	map<array<int, 4>, mi> rects;
	mi run = 1;
	while (q--) {
		int t, xl, xr, yl, yr;
		cin >> t >> xl >> yl >> xr >> yr;
		auto rect = [&]() {
			mi v;
			if (t == 1) {
				rects[{xl, xr, yl, yr}] = run;
				v = run;
				run *= 2;
			} else {
				v = rects[{xl, xr, yl, yr}];
				v *= -1;
			}
			bit.upd(xl, yl, v);
			bit.upd(xl, yr + 1, -v);
			bit.upd(xr + 1, yl, -v);
			bit.upd(xr + 1, yr + 1, v);
		};
		if (t <= 2) {
			rect();
		} else {	
			if (bit.query(1, xl, 1, yl) == bit.query(1, xr, 1, yr)) {
				cout << "Yes" << '\n';
			} else {
				cout << "No" << '\n';
			}
		}
	}
	return 0;
}