verify/codeforces/codeforces-869E-quadtree.test.cpp

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

Depends on

Code

#define IGNORE "this will TLE, but it works"
#define PROBLEM "https://codeforces.com/contest/1074/problem/F"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/data-structures/2d-range-queries/quadtree.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>;

QuadTree<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,  1, xl, yl) == bit.query(1, 1, xr, yr)) {
				cout << "Yes" << '\n';
			} else {
				cout << "No" << '\n';
			}
		}
	}
	return 0;
}

#define IGNORE "this will TLE, but it works"
#define PROBLEM "https://codeforces.com/contest/1074/problem/F"


#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, int N, int M> struct QuadTree {
	T sm[16 * N * M];

	QuadTree() { memset(sm, 0, sizeof(sm)); }

	void upd(int x, int y, T inc, int n = 1, int x1 = 0, int y1 = 0, int x2 = N - 1, int y2 = M - 1) {
		if (x1 == x2 && y1 == y2) 
			sm[n] += inc;
		else {
			int xm = (x1 + x2) >> 1;
			int ym = (y1 + y2) >> 1;
			if (x <= xm && y <= ym) 
				upd(x, y, inc, 4 * n, x1, y1, xm, ym);
			else if (x <= xm && y > ym) 
				upd(x, y, inc, 4 * n + 1, x1, ym + 1, xm, y2);
			else if (x > xm && y > ym) 
				upd(x, y, inc, 4 * n + 2, xm + 1, ym + 1, x2, y2);
			else 
				upd(x, y, inc, 4 * n + 3, xm + 1, y1, x2, ym);
			sm[n] = sm[4 * n] + sm[4 * n + 1] + sm[4 * n + 2] + sm[4 * n + 3];
		}
	}

	T query(int qx1, int qy1, int qx2, int qy2, int n = 1, int x1 = 0, int y1 = 0, int x2 = N - 1, int y2 = M - 1) {
		if (qx2 < x1 || qy1 > y2 || qx1 > x2 || qy2 < y1) 
			return 0;
		else if (qx1 <= x1 && x2 <= qx2 && qy1 <= y1 && y2 <= qy2) 
			return sm[n];
		int xm = (x1 + x2) >> 1;
		int ym = (y1 + y2) >> 1;
		return query(qx1, qy1, qx2, qy2, 4 * n, x1, y1, xm, ym) 
				+ query(qx1, qy1, qx2, qy2, 4 * n + 1, x1, ym + 1, xm, y2) 
				+ query(qx1, qy1, qx2, qy2, 4 * n + 2, xm + 1, ym + 1, x2, y2) 
				+ query(qx1, qy1, qx2, qy2, 4 * n + 3, xm + 1, y1, x2, ym);
	}
};

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

QuadTree<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,  1, xl, yl) == bit.query(1, 1, xr, yr)) {
				cout << "Yes" << '\n';
			} else {
				cout << "No" << '\n';
			}
		}
	}
	return 0;
}