結果
| 問題 | No.2421 entersys? |
| ユーザー |
 aplysiaSheep
|
| 提出日時 | 2023-08-12 15:16:16 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 739 ms / 3,000 ms |
| コード長 | 26,914 bytes |
| コンパイル時間 | 5,833 ms |
| コンパイル使用メモリ | 282,032 KB |
| 最終ジャッジ日時 | 2025-02-16 06:01:06 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#define int long long
// #define endl "\n"
#pragma GCC optimize("-O3")
void solve();
typedef long long ll;
typedef __int128_t LL;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, pair<int, int>> pip;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<pair<int, int>> vp;
typedef vector<vector<int>> vvi;
typedef vector<vector<double>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<pair<int, int>>> vvp;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<vector<vector<int>>>> vvvvi;
template <typename T>
using vec = vector<T>;
template <typename T>
using vv = vector<vector<T>>;
template <typename T>
using vvv = vector<vector<vector<T>>>;
template <typename T>
using vvvv = vector<vector<vector<vector<T>>>>;
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using mset = multiset<T>;
template <typename T>
using uset = unordered_set<T>;
template <typename T, typename U>
using umap = unordered_map<T, U>;
#define _PI 3.14159265358979323846
#define _E 2.7182818284590452354
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define td typedef
#define elif else if
#define ifnot(x) if(!(x))
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define sumv(a) accumulate(all(a), 0LL)
#define lb(v, a) (lower_bound(begin(v), end(v), a) - begin(v))
#define ub(v, a) (upper_bound(begin(v), end(v), a) - begin(v))
#define inr(l, x, r) (l <= x && x < r)
#define cbit(x) __builtin_popcountll(x)
#define topbit(t) (t == 0 ? -1 : 63 - __builtin_clzll(t))
#define botbit(t) (t == 0 ? 64 : __builtin_ctzll(t))
#define gbit(msk, i) ((msk) >> (i)&1)
#define mask(x) ((1LL << (x)) - 1)
#define setbits(i, n) \
for(int j = (n), i = botbit(j); j; j ^= 1LL << i, i = botbit(j))
#define rep1(a) for(int i = 0; i < (int)a; i++)
#define rep2(i, a) for(int i = 0; i < (int)a; i++)
#define rep3(i, a, b) for(int i = a; i < (int)b; i++)
#define rep4(i, a, b, c) for(int i = a; i < (int)b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = n; i--;)
#define rrep2(i, n) for(ll i = n; i--;)
#define rrep3(i, a, b) for(ll i = b; i-- > (a);)
#define rrep4(i, a, b, c) \
for(ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c)
#define rrep(...) \
overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define fore1(i, a) for(auto &&i : a)
#define fore2(x, y, a) for(auto &&[x, y] : a)
#define fore3(x, y, z, a) for(auto &&[x, y, z] : a)
#define fore(...) overload4(__VA_ARGS__, fore3, fore2, fore1)(__VA_ARGS__)
#define ryes return yes();
#define rno return no();
#define rerr return err();
istream &operator>>(istream &is, modint998244353 &a) {
long long v;
is >> v;
a = v;
return is;
}
ostream &operator<<(ostream &os, const modint998244353 &a) {
return os << a.val();
}
istream &operator>>(istream &is, modint1000000007 &a) {
long long v;
is >> v;
a = v;
return is;
}
ostream &operator<<(ostream &os, const modint1000000007 &a) {
return os << a.val();
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << p.first << "," << p.second;
return os;
}
template <class T>
ostream &operator<<(ostream &s, set<T> P) {
fore(it, P) {
s << it << " ";
}
return s;
}
template <class T1, class T2>
ostream &operator<<(ostream &s, map<T1, T2> P) {
fore(x, y, P) {
s << "<" << x << "->" << y << "> ";
}
return s;
}
template <class T>
ostream &operator<<(ostream &s, multiset<T> P) {
fore(it, P) {
s << it << " ";
}
return s;
}
template <class T>
ostream &operator<<(ostream &s, unordered_set<T> P) {
fore(it, P) {
s << it << " ";
}
return s;
}
template <class T1, class T2>
ostream &operator<<(ostream &s, unordered_map<T1, T2> P) {
fore(x, y, P) {
s << "<" << x << "->" << y << "> ";
}
return s;
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
for(auto &e : v) is >> e;
return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for(auto &e : v) os << e << ' ';
return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
for(auto &e : v) {
for(auto &c : e) os << c << ' ';
os << endl;
}
return os;
}
template <class T>
vector<T> &operator++(vector<T> &v) {
for(auto &e : v) e++;
return v;
}
template <class T>
vector<T> operator++(vector<T> &v, signed) {
auto res = v;
for(auto &e : v) e++;
return res;
}
template <class T>
vector<T> &operator--(vector<T> &v) {
for(auto &e : v) e--;
return v;
}
template <class T>
vector<T> operator--(vector<T> &v, signed) {
auto res = v;
for(auto &e : v) e--;
return res;
}
// 十進数からb進数へ
template <class T>
string to_baseB(T x, int b = 10) {
string ans;
do {
int num = x % b;
ans = (char)((num <= 9) ? ('0' + num) : ('A' + num - 10)) + ans;
x /= b;
} while(x != 0);
return ans;
}
// b進数から十進数へ
long long to_base10(const string &x, int b = 10) {
long long ans = 0, base = 1;
for(int i = x.length() - 1; i >= 0; --i) {
int num =
('0' <= x[i] && x[i] <= '9') ? (x[i] - '0') : (x[i] - 'A' + 10);
ans += base * num;
base *= b;
}
return ans;
}
ostream &operator<<(ostream &s, const LL &p) {
s << to_baseB(p);
return s;
}
// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) \
cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) \
cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
<< x3 << endl
#define debug_4(x1, x2, x3, x4) \
cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
<< x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) \
cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
<< x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...) \
CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
(__VA_ARGS__)
#else
#define debug(...)
#endif
void out() {
cout << endl;
}
template <class T>
void out(const T &a) {
cout << a;
cout << endl;
}
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
cout << a;
(cout << ... << (cout << ' ', b));
cout << endl;
}
#define rout_1(x1) return out(x1)
#define rout_2(x1, x2) return out(x1, x2)
#define rout_3(x1, x2, x3) return out(x1, x2, x3)
#define rout_4(x1, x2, x3, x4) return out(x1, x2, x3, x4)
#define rout_5(x1, x2, x3, x4, x5) return out(x1, x2, x3, x4, x5)
#define rout(...) \
CHOOSE((__VA_ARGS__, rout_5, rout_4, rout_3, rout_2, rout_1, ~)) \
(__VA_ARGS__)
struct fast_ios {
fast_ios() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(12);
};
} fast_ios_;
struct Binomial {
int p;
int MAX;
vector<long long> fac, finv, inv;
// テーブルを作る前処理
Binomial(int p_, int n = 1) : p(p_), MAX(1), fac(2), finv(2), inv(2) {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
if(n != 1) build(n);
}
void build(int new_max) {
MAX++;
fac.resize(new_max + 1);
inv.resize(new_max + 1);
finv.resize(new_max + 1);
for(; MAX <= new_max; MAX++) {
fac[MAX] = fac[MAX - 1] * MAX % p;
inv[MAX] = p - inv[p % MAX] * (p / MAX) % p;
finv[MAX] = finv[MAX - 1] * inv[MAX] % p;
}
MAX--;
}
// nCk
long long mod_comb(int n, int k) {
if(n < k) return 0;
if(n < 0 || k < 0) return 0;
if(n > MAX) build(n);
return fac[n] * (finv[k] * finv[n - k] % p) % p;
}
long long operator()(int n, int k) {
return mod_comb(n, k);
}
// nPk
long long mod_perm(int n, int k) {
if(n < k) return 0;
if(n < 0 || k < 0) return 0;
if(n > MAX) build(n);
return fac[n] * finv[n - k] % p;
}
long long operator[](int n) {
return mod_perm(n, n);
}
};
struct modpow {
long long x, m;
int n;
vector<long long> d;
modpow(long long x, long long m = 0) : x(x), m(m), n(1), d(1, 1) {}
long long operator[](int i) {
if(m)
while(n <= i) d.push_back(d.back() * x % m), ++n;
else
while(n <= i) d.push_back(d.back() * x), ++n;
return d[i];
}
} two(2), ten(10);
struct RandomNumberGenerator {
mt19937 mt;
RandomNumberGenerator()
: mt(chrono::steady_clock::now().time_since_epoch().count()) {}
long long operator()(long long a, long long b) { // [a, b)
uniform_int_distribution<long long> dist(a, b - 1);
return dist(mt);
}
long long operator()(long long b) { // [0, b)
return (*this)(0, b);
}
long long operator()() {
return (*this)(0, 1LL << 60);
}
double operator[](double a) {
return (double)(*this)(0, 1LL << 60) / (1LL << 60) * a;
}
} rnd;
clock_t start_time = clock();
double now_time() {
clock_t end_time = clock();
return (double)(end_time - start_time) / CLOCKS_PER_SEC;
}
void input_graph(vector<vector<int>> &g, int m = -1, int bidirected = true) {
if(m == -1) m = g.size() - 1;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
g[u].push_back(v);
if(bidirected) g[v].push_back(u);
}
}
vector<int> iota(int n, int s = 0) {
vi a(n);
iota(a.begin(), a.end(), s);
return a;
}
template <class T>
void sort(vector<T> &v) {
sort(all(v));
}
template <class T>
void rsort(vector<T> &v) {
sort(rall(v));
}
template <class T>
void reverse(T &v) {
reverse(all(v));
}
template <class T>
auto max(const T &a) {
return *max_element(all(a));
}
template <class T>
auto min(const T &a) {
return *min_element(all(a));
}
long long max(signed x, long long y) {
return max((long long)x, y);
}
long long max(long long x, signed y) {
return max(x, (long long)y);
}
long long min(signed x, long long y) {
return min((long long)x, y);
}
long long min(long long x, signed y) {
return min(x, (long long)y);
}
template <class T, class S>
bool chmax(T &a, const S &b) {
if(a < (T)b) {
a = (T)b;
return 1;
}
return 0;
}
template <class T, class S>
bool chmin(T &a, const S &b) {
if((T)b < a) {
a = (T)b;
return 1;
}
return 0;
}
template <class T>
vector<T> uniq(vector<T> v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
return v;
}
template <class T>
vector<T> compress(vector<T> v) {
vector<T> v2(v.size());
v2 = v;
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i = 0; i < (int)v2.size(); i++) {
v2[i] = lower_bound(v.begin(), v.end(), v2[i]) - v.begin();
}
return v2;
}
vector<int> inverse(vector<int> &p) {
int n = p.size();
vector<int> inv(n);
for(int i = 0; i < n; i++) inv[p[i]] = i;
return inv;
}
template <typename T>
vector<T> acc0(vector<T> &v) {
vector<T> res(v.size());
if((int)v.size() == 0) return res;
res[0] = v[0];
for(int i = 1; i < (int)v.size(); i++) {
res[i] = res[i - 1] + v[i];
}
return res;
}
template <typename T>
vector<T> acc1(vector<T> &v) {
vector<T> res(v.size() + 1);
for(int i = 0; i < (int)v.size(); i++) {
res[i + 1] = res[i] + v[i];
}
return res;
}
template <typename T>
vector<vector<T>> acc0(vector<vector<T>> v) {
int h = v.size(), w = v[0].size();
for(int i = 0; i < h; i++) {
for(int j = 1; j < w; j++) {
v[i][j] += v[i][j - 1];
}
}
for(int i = 1; i < h; i++) {
for(int j = 0; j < w; j++) {
v[i][j] += v[i - 1][j];
}
}
return v;
}
template <typename T>
vector<vector<T>> acc1(vector<vector<T>> &v) {
int h = v.size(), w = v[0].size();
vector<vector<T>> res(h + 1, vector<T>(w + 1));
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
res[i + 1][j + 1] = v[i][j] + res[i + 1][j];
}
}
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
res[i + 1][j + 1] += res[i][j + 1];
}
}
return res;
}
long long exp(long long x, int n) {
long long res = 1;
while(n > 0) {
if(n & 1) res = res * x;
x = x * x;
n >>= 1;
}
return res;
}
int countDigits(long long n) {
string tmp = to_string(n);
return (int)tmp.size();
}
long long sq(long long n) {
return n * n;
}
long long ceil(long long x, long long y) {
return (x + y - 1) / y;
}
long long floor(long long x, long long y) {
return (y < 0 ? floor(-x, -y)
: (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
constexpr long long tri(long long n) {
return n * (n + 1) / 2;
}
// l + ... + r
constexpr long long tri(long long l, long long r) {
return (l + r) * (r - l + 1) / 2;
}
int ctoi(const char &c, const char start = '0') {
return c - start;
}
int atoi(const char &c, const char start = 'a') {
return c - start;
}
vector<int> ctoi(string &s, const char start = '0') {
vector<int> res;
for(auto &c : s) {
int x = c - start;
if(x < 0 || x >= 10) x = -1;
res.push_back(x);
}
return res;
}
vector<int> atoi(string &s, const char start = 'a') {
vector<int> res;
for(auto &c : s) {
int x = c - start;
if(x < 0 || x >= 26) x = -1;
res.push_back(x);
}
return res;
}
void yes() {
cout << "Yes" << endl;
}
void no() {
cout << "No" << endl;
}
void yesno(bool x) {
if(x)
yes();
else
no();
}
void err() {
cout << -1 << endl;
}
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
long long inf = 1LL << 61;
double eps = 1e-9;
// long long mod = 67280421310721;
// using mint = static_modint<1000000009>;
// using mint = dynamic_modint<1000000009>;
// long long mod = 1000000007;
// using mint = modint1000000007;
// long long mod = 998244353;
// using mint = modint998244353;
// typedef vector<mint> vm;
// typedef vector<vector<mint>> vvm;
// typedef vector<vector<vector<mint>>> vvvm;
// Binomial C(mod);
// modpow mtwo(2, mod), mten(10, mod);
////////////////////////////////////////////////////////////////////////////////////////////
/** structure: 2-3 tree
* available for both set and multiple set (see constructor)
* every method works in O(logn)
* tests: { https://judge.yosupo.jp/submission/105334,
* https://atcoder.jp/contests/abc241/submissions/35040063
* }
*
* コンストラクタの引数にtrueを入れることでmultisetに
* insert.erase,lower_bound,upper_bound(配列番号),size,count,[]
*/
template <class T>
class twothreetree {
private:
struct node {
node *parent = nullptr;
unsigned char position;
unsigned char n = 0;
unsigned size = 0;
T keys[2];
node *children[3] = {nullptr, nullptr, nullptr};
node() {}
unsigned char LB(T key) {
for(unsigned char i = 0; i < n; i++)
if(key <= keys[i]) return i;
return n;
}
unsigned char UB(T key) {
for(unsigned char i = 0; i < n; i++)
if(key < keys[i]) return i;
return n;
}
void insert(unsigned char i, T key, node *child = nullptr) {
if(n < 2) {
if(i == 0) {
keys[1] = keys[0];
children[2] = children[1];
}
keys[i] = key;
children[i + 1] = child;
n++;
coordinate();
if(parent == nullptr) return;
parent->sizeIncrement();
return;
}
node *newNode = new node();
T newKey;
if(i == 0) {
newNode->keys[0] = keys[1];
newNode->children[0] = children[1];
newNode->children[1] = children[2];
newKey = keys[0];
keys[0] = key;
children[1] = child;
} else if(i == 1) {
newNode->keys[0] = keys[1];
newNode->children[0] = child;
newNode->children[1] = children[2];
newKey = key;
} else {
newNode->keys[0] = key;
newNode->children[0] = children[2];
newNode->children[1] = child;
newKey = keys[1];
}
children[2] = nullptr;
newNode->n = 1;
n = 1;
newNode->coordinate();
coordinate();
if(parent == nullptr) {
node *newRoot = new node();
newRoot->keys[0] = newKey;
newRoot->children[0] = this;
newRoot->children[1] = newNode;
newRoot->n = 1;
newRoot->coordinate();
return;
}
parent->insert(position, newKey, newNode);
}
void erase(unsigned char i) {
delete children[i + 1];
children[i + 1] = nullptr;
if(n == 2) {
if(i == 0) {
keys[0] = keys[1];
children[1] = children[2];
children[2] = nullptr;
}
n--;
this->coordinate();
if(parent == nullptr) return;
parent->sizeDecrement();
return;
}
if(parent == nullptr) {
n--;
size--;
return;
}
if(position > 0) {
node *leftNode = parent->children[position - 1];
if(leftNode->n == 2) {
keys[0] = parent->keys[position - 1];
parent->keys[position - 1] = leftNode->keys[1];
children[1] = children[0];
children[0] = leftNode->children[2];
leftNode->children[2] = nullptr;
leftNode->n = 1;
n = 1;
leftNode->coordinate();
coordinate();
if(parent == nullptr) return;
parent->sizeDecrement();
return;
}
leftNode->keys[1] = parent->keys[position - 1];
leftNode->children[2] = children[0];
leftNode->n = 2;
leftNode->coordinate();
parent->erase(position - 1);
return;
}
node *rightNode = parent->children[1];
if(rightNode->n == 2) {
keys[0] = parent->keys[0];
parent->keys[0] = rightNode->keys[0];
children[1] = rightNode->children[0];
rightNode->keys[0] = rightNode->keys[1];
rightNode->children[0] = rightNode->children[1];
rightNode->children[1] = rightNode->children[2];
rightNode->children[2] = nullptr;
rightNode->n = 1;
n = 1;
rightNode->coordinate();
coordinate();
if(parent == nullptr) return;
parent->sizeDecrement();
return;
}
rightNode->keys[1] = rightNode->keys[0];
rightNode->keys[0] = parent->keys[position];
rightNode->children[2] = rightNode->children[1];
rightNode->children[1] = rightNode->children[0];
rightNode->children[0] = children[0];
rightNode->n = 2;
rightNode->coordinate();
parent->children[0] = rightNode;
parent->children[1] = this;
rightNode->position = 0;
parent->erase(0);
}
void sizeIncrement() {
size++;
if(parent != nullptr) parent->sizeIncrement();
}
void sizeDecrement() {
size--;
if(parent != nullptr) parent->sizeDecrement();
}
void coordinate() {
size = n;
if(children[0] == nullptr) return;
for(unsigned char i = 0; i <= n; i++) {
size += children[i]->size;
children[i]->parent = this;
children[i]->position = i;
}
}
};
node *root;
bool isForMulti;
public:
/** if argument is true, works as multiple set.default is set.*/
twothreetree(bool forMultiSet = false) {
root = new node();
isForMulti = forMultiSet;
}
/** returns index.*/
unsigned lower_bound(T key) {
node *presentNode = root;
unsigned res = 0;
while(presentNode->children[0] != nullptr) {
unsigned char i = presentNode->LB(key);
for(unsigned char j = 0; j < i; j++)
res += presentNode->children[j]->size;
res += i;
presentNode = presentNode->children[i];
}
return res + presentNode->LB(key);
}
/** returns index.*/
unsigned upper_bound(T key) {
node *presentNode = root;
unsigned res = 0;
while(presentNode->children[0] != nullptr) {
unsigned char i = presentNode->UB(key);
for(unsigned char j = 0; j < i; j++)
res += presentNode->children[j]->size;
res += i;
presentNode = presentNode->children[i];
}
return res + presentNode->UB(key);
}
bool insert(T key) {
node *presentNode = root;
unsigned char i;
while(presentNode->children[0] != nullptr) {
i = presentNode->LB(key);
if(!isForMulti && i < presentNode->n && presentNode->keys[i] == key)
return false;
presentNode = presentNode->children[i];
}
i = presentNode->LB(key);
if(!isForMulti && i < presentNode->n && presentNode->keys[i] == key)
return false;
presentNode->insert(i, key);
if(root->parent != nullptr) {
root = root->parent;
}
return true;
}
bool erase(T key) {
node *presentNode = root;
unsigned char i;
while(presentNode->children[0] != nullptr) {
i = presentNode->LB(key);
if(i < presentNode->n && presentNode->keys[i] == key) break;
presentNode = presentNode->children[i];
}
if(presentNode->children[0] == nullptr) {
i = presentNode->LB(key);
if(i < presentNode->n && presentNode->keys[i] == key) {
presentNode->erase(i);
if(root->n == 0 && root->children[0] != nullptr) {
root = root->children[0];
delete root->parent;
root->parent = nullptr;
}
return true;
}
return false;
}
node *eraseNode = presentNode->children[i + 1];
while(eraseNode->children[0] != nullptr)
eraseNode = eraseNode->children[0];
presentNode->keys[i] = eraseNode->keys[0];
eraseNode->erase(0);
if(root->n == 0) {
root = root->children[0];
delete root->parent;
root->parent = nullptr;
}
return true;
}
T get(unsigned i) {
if(i < 0) i += root->size;
node *presentNode = root;
while(presentNode->children[0] != nullptr) {
unsigned char j = 0;
while(i >= presentNode->children[j]->size + 1) {
i -= presentNode->children[j]->size + 1;
j++;
}
if(i == presentNode->children[j]->size) {
return presentNode->keys[j];
}
presentNode = presentNode->children[j];
}
return presentNode->keys[i];
}
unsigned size() {
return root->size;
}
unsigned count(T key) {
return upper_bound(key) - lower_bound(key);
}
T operator[](unsigned i) {
return get(i);
}
};
////////////////////////////////////////////////////////////////////////////////////////////
signed main() {
int testcase = 1;
// cin >> testcase;
for(int i = 0; i < testcase; i++) {
solve();
}
}
void solve() {
int n;
cin >> n;
vs x(n);
vi l(n), r(n);
rep(i, n) cin >> x[i] >> l[i] >> r[i];
twothreetree<double> lst(1);
twothreetree<double> rst(1);
map<string, twothreetree<double>> mem;
rep(i, n) {
lst.insert(l[i] - 0.1);
rst.insert(r[i] + 0.1);
mem[x[i]].insert(l[i] - 0.1);
mem[x[i]].insert(r[i] + 0.1);
}
int q;
cin >> q;
rep(i, q) {
int t;
string x;
int l, r, tt;
cin >> t;
if(t == 1) {
cin >> x >> tt;
if(!mem.count(x)) {
no();
continue;
}
auto &st = mem[x];
int p = st.upper_bound(tt);
yesno(p % 2 == 1);
}
else if(t == 2) {
cin >> tt;
int l_n = lst.upper_bound(tt);
int r_n = rst.upper_bound(tt);
debug(l_n, r_n);
out(l_n - r_n);
} else {
cin >> x >> l >> r;
lst.insert(l - 0.1);
rst.insert(r + 0.1);
mem[x].insert(l - 0.1);
mem[x].insert(r + 0.1);
}
}
}