A. Parkour Design
Category: Mathematics
Logic
By plotting the points on scratch paper, we can observe a very clear pattern: all reachable points lie on specific line segments with a slope of $$$-1$$$ . These line segments belong to lines that can be expressed as:
To restrict the lines to segments, we also need to apply constraints on $$$x$$$ :
We can directly check these conditions.
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
void solve() {
int x, y;cin >> x >> y;
if ((x + y) % 3 != 0)cout << "NO\n";
else {
int k = (x + y) / 3;
if (x >= 2 * k && x <= 4 * k)cout << "YES\n";
else cout << "NO\n";
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
B. ABAB Construction
Category: Strings, DP, Greedy
Logic
This problem might seem intimidating at first, but it can be solved using either a clever greedy approach or a DP approach.
Approach 1: Greedy
- When $$$n$$$ is even, $$$T = abab \dots ab$$$ . Regardless of whether we pick from the left or the right, the character sequence extracted must be $$$a, b, a, b, \dots$$$ . Therefore, if there exists any adjacent pair $$$X_{i} = X_{i+1}$$$ in $$$X$$$ ( where neither is '?' ), we can directly output
NO. - When $$$n$$$ is odd, $$$T = abab \dots a$$$ . Both the first and last characters are 'a' .
- Therefore, $$$S_{0}$$$ must be 'a' . If $$$S_{0} = \text{'b'}$$$ , output
NO. - After processing $$$S_{0}$$$ , the remaining $$$T$$$ has an even length, which reduces to the even case mentioned above.
- Therefore, $$$S_{0}$$$ must be 'a' . If $$$S_{0} = \text{'b'}$$$ , output
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
void solve() {
int n;cin >> n;
string s;cin >> s;
if ((n & 1) && s[0] == 'b')cout << "NO\n";
else {
for (int i = (n & 1);i < n - 1;i += 2) {
if (s[i] == s[i + 1] && s[i] != '?') {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
Approach 2: State Compression DP
We treat 'a' as $$$0$$$ and 'b' as $$$1$$$ . The original string $$$T$$$ looks like $$$0101 \dots 01$$$ or $$$0101 \dots 010$$$ . Observe that after each operation, the remaining part of $$$T$$$ will always be in one of four states based on its head and tail characters: $$$0 \dots 0, 0 \dots 1, 1 \dots 0, 1 \dots 1$$$ . We use binary values $$$00, 01, 10, 11$$$ to represent these states, corresponding to $$$0, 1, 2, 3$$$ .
We can draw a state transition graph where:
represents removing an element $$$c$$$ from either the head or the tail of a string in state $$$s$$$ to transition to state $$$s^{*}$$$ .
State Design: $$$dp_{i, mask}$$$ : Whether it is possible to generate the prefix of length $$$i$$$ of the target string such that the remaining part of $$$T$$$ is in state $$$mask$$$ .
Initial State: - If $$$n$$$ is odd, the initial state is $$$0 \dots 0$$$ , so $$$dp_{0, 00} = 1$$$ . - If $$$n$$$ is even, the initial state is $$$0 \dots 1$$$ , so $$$dp_{0, 01} = 1$$$ .
We build the edges between states. Then, as we iterate through the target string, the current character can be treated as $$$c$$$ . We only traverse paths where the edge weight matches $$$c$$$ to perform the DP transitions.
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
bool e[4][2][4];
void solve() {
int n;cin >> n;
string s;cin >> s;
rep(i, 0, 3) {
rep(j, 0, 1) {
rep(k, 0, 3)e[i][j][k] = 0;
}
}
e[0][0][1] = e[0][0][2] = 1;
e[1][0][3] = 1;e[1][1][0] = 1;
e[2][0][3] = 1;e[2][1][0] = 1;
e[3][1][1] = e[3][1][2] = 1;
vector<bool>dp(4);
if (n & 1)dp[0] = 1;
else dp[1] = 1;
rep(pos, 0, n - 1) {
vector<bool>ndp(4);
rep(i, 0, 3) {
if (!dp[i])continue;
if (s[pos] == 'a') {
rep(nxt, 0, 3) {
if (e[i][0][nxt])ndp[nxt] = 1;
}
} else if (s[pos] == 'b') {
rep(nxt, 0, 3) {
if (e[i][1][nxt])ndp[nxt] = 1;
}
} else {
rep(nxt, 0, 3) {
if (e[i][0][nxt])ndp[nxt] = 1;
if (e[i][1][nxt])ndp[nxt] = 1;
}
}
}
dp = ndp;
}
rep(i, 0, 3) {
if (dp[i]) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
C1. Lost Civilization (Easy Version)
Category: Two Pointers
Logic
By observation, every element has a minimum element to its left that can generate it. We call this the key element. Taking the example:
We can split the sequence into segments where each segment's key element is its left endpoint. The left endpoint itself doesn't have a key element in its segment.
We traverse the sequence from left to right, maintaining the current key element as $$$last$$$ . If we find that $$$a_{i} \gt a_{i-1} + 1$$$ or $$$a_{i} \le last$$$ , then the current element cannot be generated by $$$last$$$ , and we must start a new segment. At this point, we increment the count $$$ans$$$ and update $$$last = a_{i}$$$ .
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
void solve() {
int n;cin >> n;
vector<int>a(n + 1);
a[0] = -5;
int last = -5, ans = 0;
rep(i, 1, n) {
cin >> a[i];
if (a[i] > a[i - 1] + 1 || a[i] <= last) {
ans++;
last = a[i];
continue;
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
C2. Lost Civilization (Hard Version)
Category: Mathematics
Logic
Similar to the previous problem, we consider the nearest element that can generate a given element, which we call the nearest key element. Let $$$L_{i}$$$ denote the index of the nearest key element for $$$a_{i}$$$ .
To precalculate $$$L_{i}$$$ , we can use a set<pair<int, int>> to store $$${ \text{value}, \text{index} }$$$ to maintain information about elements in the current segment. If a new element belongs to the current set, we can use lower_bound to find the nearest generating element satisfying $$$a_{pos} \lt a_{i}$$$ and $$$pos \lt i$$$ . If the new element does not belong to the current set, we clear the set and start a new segment.
To calculate the sum for all valid subsegments, we fix the right endpoint $$$r$$$ and iterate backwards. By tabulating the answers, we observe that as $$$r$$$ transitions, the answers for the range $$$[ L_{r} + 1, r ]$$$ all decrease by $$$1$$$ . Therefore, we can treat each element's contribution as an interval. Over $$$n$$$ time steps as $$$r$$$ goes from $$$n$$$ to $$$1$$$ , the interval $$$[ L_{i} + 1, i ]$$$ contributes to the answer when $$$1 \le r \le i$$$ and stops contributing when $$$i \lt r \le n$$$ . This is analogous to a lightbulb that stays on for a duration equal to its index $$$i$$$ . The total contribution is the sum of (unit contribution $$$\times$$$ duration):
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
void solve() {
int n;cin >> n;
vector<int>a(n + 1);
vector<int>l(n + 1);
a[0] = -5;
int last = -5, ans = 0;
set<pair<int, int>>s;//val,id
rep(i, 1, n) {
cin >> a[i];
if (a[i] > a[i - 1] + 1 || a[i] <= last) {
last = a[i];
s.clear();
l[i] = 0;
} else {
auto it = s.lower_bound({ a[i],0 });
it--;
l[i] = it->second;
}
s.insert({ a[i],i });
}
rep(i, 1, n) {
ans += (n - i + 1) * (i - l[i]);
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
D. Memorizing Numbers
Category: Mathematics, Constructive
Logic
Consider the minimum and maximum possible number of rounds. If we arrange the cards as $$$1, 1, 2, 2, 3, 3, \dots, n, n$$$ , the number of rounds is minimized at $$$n$$$ . If we arrange them as $$$2, 1, 3, 2, 4, 3, \dots, n, n-1, n, 1$$$ , the number of rounds is maximized at $$$2n - 1$$$ . Why is this the maximum? For each number, picking its identical pair takes $$$n$$$ rounds. Any other operations are "extra". To maximize the rounds, we must maximize these extra operations. In the second arrangement, you must always flip two new cards to find a pair ( $$$1$$$ extra operation ), and the flipping of new cards does not interfere with picking pairs, leading to $$$n-1$$$ extra operations.
Thus, we first check if $$$n \le k \le 2n - 1$$$ . Then we need to control the number of extra operations. Observe that if $$$f(n)$$$ is the sequence maximizing operations for $$$n$$$ cards, then $$$f(n), f(n-1), \dots$$$ have common prefixes. For instance:
To get exactly $$$3$$$ extra operations when $$$n = 6$$$ , we can use the prefix of $$$f(4)$$$ and fill the rest with immediate pairs:
We use the prefix to control the extra count and place identical elements together in the suffix.
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
void solve() {
int n, k;cin >> n >> k;
if (k < n || k>2 * n - 1) {
cout << "NO\n";return;
}
cout << "YES\n";
int cnt = k - n;
vector<int>ans(2*n + 1);
rep(i, 1, cnt) {
ans[2 * i] = i;
ans[2 * i - 1] = i + 1;
}
ans[2 * (cnt + 1)] = 1;
ans[2 * (cnt + 1) - 1] = cnt + 1;
rep(i, cnt + 2, n) {
ans[2 * i] = ans[2 * i - 1] = i;
}
rep(i, 1, 2 * n)cout << ans[i] << " ";cout << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
E. Manipulated Bracket Sequence
Category: Strings, DP, Counting DP
Logic
A bracket sequence is valid if, when treating '(' as $$$+1$$$ and ')' as $$$-1$$$ , all prefix sums are $$$\ge 0$$$ . Let $$$pre_{i}$$$ be the prefix sum of $$$1 \dots i$$$ . Suppose we choose $$$s_{k_{1}}, s_{k_{2}}, \dots, s_{k_{t}}$$$ as a subsequence and right-shift it. - For $$$1 \le i \lt k_{1}$$$ , $$$pre_{i}$$$ does not change. - For $$$k_{t} \lt i \le n$$$ , $$$pre_{i}$$$ does not change. For $$$i = k_{j}$$$ , after the shift, $$$pre_{k_{j}}$$$ becomes $$$pre_{k_{j}} - s_{k_{j}} + s_{k_{t}}$$$ . - If $$$s_{k_{t}} = +1$$$ , the change is $$$1 - s_{k_{j}} \ge 0$$$ , so it remains valid. - If $$$s_{k_{t}} = -1$$$ , the change is $$$-1 - s_{k_{j}} \le 0$$$ . — If $$$s_{k_{j}} = -1$$$ , change is $$$0$$$ . — If $$$s_{k_{j}} = 1$$$ , change is $$$-2$$$ . This requires the original $$$pre_{k_{j}} \ge 2$$$ .
Therefore, if $$$s_{k_{t}} = +1$$$ , any previous prefix of the subsequence works, giving $$$2^{i-1}$$$ ways for each such $$$i$$$ . If $$$s_{k_{t}} = -1$$$ , we need to carefully count valid subsequences.
State Design: $$$dp_{i}$$$ : The number of valid subsequences $$$1 \dots i$$$ ending with $$$s_{k_{t}} = -1$$$ .
Transition: Let $$$S_{i}$$$ be indices $$$j \lt i$$$ such that $$$s_{j} = +1$$$ and $$$pre_{j} \ge 2$$$ .
- The $$$+1$$$ represents the subsequence of length $$$1$$$ .
- For $$$s_{j} = -1$$$ , we need $$$pre_{j} \ge 2$$$ in the original sequence for the $$$-1$$$ at $$$k_{t}$$$ to not break validity.
To optimize, let $$$L_{i}$$$ be the nearest position to the left of $$$i$$$ where $$$pre_{pos} \lt 2$$$ . Then $$$\sum_{j \in S_{i}} dp_{j}$$$ becomes $$$\sum_{L_{i-1} \lt j \lt i, s_{j} = +1} dp_{j}$$$ . We maintain prefix sums of $$$dp$$$ values for $$$s_{j} = +1$$$ and $$$s_{j} = -1$$$ to transition in $$$O(1)$$$ .
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
const int mod = 998244353;
int n;
constexpr int qpow(int a, int b) {
int ans = 1;a %= mod;
while (b) {
if (b & 1) { ans *= a; ans %= mod; }
a *= a;a %= mod;b >>= 1;
}
return ans % mod;
}
void solve() {
cin >> n;
string s;cin >> s;
vector<int>prel(n + 1);
vector<int>prer(n + 1);
vector<int>dp(n + 1);
vector<int>pre(n + 1);
vector<int>L(n + 1);
rep(i, 1, n) {
int add = 0;
if (s[i - 1] == '(')add = 1;
else add = -1;
pre[i] = add;
if (i - 1 >= 1) {
pre[i] += pre[i - 1];
L[i] = L[i - 1];
}
if (pre[i] < 2)L[i] = i;
}
int ans = 0;
rep(i, 1, n) {
dp[i] = 1 + prel[i - 1] - prel[L[i - 1]] + prer[i - 1] + mod;
dp[i] %= mod;
if (s[i - 1] == '(')prel[i] = dp[i];
else prer[i] = dp[i];
if (i - 1 >= 1) {
prel[i] += prel[i - 1];
prer[i] += prer[i - 1];
prel[i] %= mod;
prer[i] %= mod;
}
if (s[i - 1] == '(') {
ans += qpow(2, i - 1);
ans %= mod;
} else {
ans += dp[i];
ans %= mod;
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
F. Non-Binary Search and Queries
Category: STL, Mathematics
Logic
The key observation is: $$$k_{max}$$$ must be the maximum difference between indices of identical elements. Consider a segment $$$x_{p}, a, b, \dots, z, x_{q}$$$ . We can choose the intervals $$$[ p, q-1 ]$$$ and $$$[ p+1, q ]$$$ . The occurrences of each element in these two intervals will be identical. Thus, finding the maximum distance between identical elements gives $$$k_{max}$$$ .
Once $$$k_{max}$$$ is fixed, how to find $$$f(a)$$$ ? For an element $$$x$$$ with $$$len_{x} = k_{max}$$$ where $$$len_{x}$$$ is the distance between its first and last occurrence, let its first occurrence be $$$first_{x}$$$ . Any interval starting in $$$[ first_{x}, first_{x} + 1 ]$$$ would be valid. If multiple elements have the same $$$k_{max}$$$ , we can merge their starting intervals. For instance, if $$$a_{i}, a_{i+1}, \dots, a_{i+t}$$$ all satisfy $$$len = k_{max}$$$ , the merged interval for the starting point is $$$[ p, p+t+1 ]$$$ , contributing $$$\binom{t+1}{2}$$$ to the answer.
We need to maintain these continuous segments of starting points dynamically. We use set<pair<int, int>> lr[N] to store segments for each $$$len$$$ . When modifying an element, we update the segments and the contribution $$$ans_{k}$$$ . We also use a multiset<int> len to track the current $$$k_{max}$$$ .
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
const int N = 2e5 + 5, Q = 1e5 + 5;
int a[N], n, q, ans[N];
set<pair<int, int>>lr[N];
constexpr int C(int x) {
return x * (x - 1) / 2;
}
void add(int k, int x) {
if (k <= 0)return;
int L = x, R = x;
auto& s = lr[k];
auto it = s.lower_bound({ x,0 });
if (it != s.end() && it->first == x + 1) {
auto [l, r] = *it;
R = r;
ans[k] -= C(r - l + 2);
s.erase(it);
}
it = s.lower_bound({ x,0 });
if (it != s.begin() && (--it)->second == x - 1) {
auto [l, r] = *it;
L = l;
ans[k] -= C(r - l + 2);
s.erase(it);
}
s.insert({ L,R });
ans[k] += C(R - L + 2);
}
void del(int k, int x) {
if (k <= 0)return;
auto& s = lr[k];
auto it = s.lower_bound({ x + 1,0 });
if (it != s.begin()) {
it--;
auto [L, R] = *it;
if (L > x || R < x)return;
s.erase(it);
ans[k] -= C(R - L + 2);
if (x - 1 >= L) {
s.insert({ L,x - 1 });
ans[k] += C(x - 1 - L + 2);
}
if (x + 1 <= R) {
s.insert({ x + 1,R });
ans[k] += C(R - (x + 1) + 2);
}
}
}
void solve() {
cin >> n >> q;
vector<set<int>>pos(n + 1);
rep(i, 1, n) {
cin >> a[i];
pos[a[i]].insert(i);
lr[i].clear();
ans[i] = 0;
}
lr[0].clear();ans[0] = 0;
multiset<int>len;
rep(i, 1, n) {
if (pos[i].size()) {
int k = *pos[i].rbegin() - *pos[i].begin();
len.insert(k);
add(k, *pos[i].begin());
}
}
rep(i, 1, q) {
int x, val;cin >> x >> val;
if (!len.size()) {
cout << "0 0\n";continue;
}
int orilen = *pos[a[x]].rbegin() - *pos[a[x]].begin();
len.erase(len.find(orilen));
del(orilen, *pos[a[x]].begin());
pos[a[x]].erase(x);
if (pos[a[x]].size()) {
int nowlen = *pos[a[x]].rbegin() - *pos[a[x]].begin();
len.insert(nowlen);
add(nowlen, *pos[a[x]].begin());
}
a[x] = val;
if (pos[a[x]].size()) {
orilen = *pos[a[x]].rbegin() - *pos[a[x]].begin();
len.erase(len.find(orilen));
del(orilen, *pos[a[x]].begin());
}
pos[a[x]].insert(x);
int nowlen = *pos[a[x]].rbegin() - *pos[a[x]].begin();
len.insert(nowlen);
add(nowlen, *pos[a[x]].begin());
int ma = *len.rbegin();
if (!ma)cout << "0 0\n";
else cout << ma << " " << ans[ma] << '\n';
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
G1. Monotonic Matrix (Easy Version)
Category: Bitset, Mathematics, STL
Logic
Treating white as $$$0$$$ and black as $$$1$$$ , each row is a binary number. Conclusion: A matrix is monotonic if and only if for any two rows $$$a, b$$$ , one contains the other ($$$a \subseteq b$$$ or $$$b \subseteq a$$$). In bitwise terms: $$$(a \ & \ \sim b) = 0$$$ or $$$(\sim a \ & \ b) = 0$$$ .
If we sort the rows by the number of black cells cnt, they must form a chain: $$$S_{p_{1}} \subseteq S_{p_{2}} \subseteq \dots \subseteq S_{p_{n}}$$$ . We use a set to maintain this sorted order. When a cell is modified, we check if the local containment relationship is preserved between the modified row and its neighbors in the set. We use bitset to speed up the containment check.
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
const int N = 25005;
int n, q;
bitset<N>bs[N];
int cnt[N];
bool pd(int a, int b) {
if (!a || !b)return 0;
return (bs[a] & ~bs[b]).any();
}
void solve() {
cin >> n >> q;
set<pair<int, int>>s;//cnt,id
rep(i, 1, n)s.insert({ 0,i }), bs[i] = 0, cnt[i] = 0;
int tot = 0;
rep(i, 1, q) {
int r, c;cin >> r >> c;
auto it = s.lower_bound({ cnt[r],r });
int pre = 0, nxt = 0;
if (it != s.begin())pre = prev(it)->second;
if (next(it) != s.end())nxt = next(it)->second;
if (pre && pd(pre, r))tot--;
if (nxt && pd(r, nxt))tot--;
if (pre && nxt && pd(pre, nxt))tot++;
s.erase(it);
bs[r][c] = 1;
cnt[r]++;
s.insert({ cnt[r],r });
it = s.lower_bound({ cnt[r],r });
pre = 0, nxt = 0;
if (it != s.begin())pre = prev(it)->second;
if (next(it) != s.end())nxt = next(it)->second;
if (pre && pd(pre, r))tot++;
if (nxt && pd(r, nxt))tot++;
if (pre && nxt && pd(pre, nxt))tot--;
if (!tot)cout << "YES\n";
else cout << "NO\n";
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
G2. Monotonic Matrix (Hard Version)
Category: Mathematics
Logic
In the Hard version, $$$N, Q \le 2 \times 10^{6}$$$ , so the bitset approach is too slow. We need an $$$O(N + Q)$$$ approach using invariants.
This problem relates to the Gale-Ryser Theorem. 1. Let $$$R$$$ be the row sum sequence. Define a theoretical column distribution $$$R^{*}$$$ where $$$R^{*}_{k}$$$ is the number of rows with black cells $$$\ge k$$$ . 2. A matrix is monotonic if and only if the actual column sums $$$C$$$ are a permutation of $$$R^{*}$$$ . 3. A property of majorization is that the sum of squares $$$\sum C_{i}^{2}$$$ reaches its theoretical maximum if and only if $$$C$$$ is a permutation of $$$R^{*}$$$ .
We maintain two "fingerprints": - sumC : $$$\sum (cntC_{j})^{2}$$$ - sumR : $$$\sum (R^{*}_{k})^{2}$$$
Using the identity $$$(x+1)^{2} - x^{2} = 2x+1$$$ , we can update these in $$$O(1)$$$ . If sumC == sumR , the answer is YES .
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
const int N = 2e6 + 5;
int n, q, cntC[N], cntR[N], sufR[N];
int sumC, sumR;
void solve() {
cin >> n >> q;
rep(i, 1, n)cntC[i] = cntR[i] = sufR[i] = 0;
sumC = sumR = 0;
rep(i, 1, q) {
int r, c;cin >> r >> c;
sumC += 2 * cntC[c] + 1;
cntC[c]++;
sumR += 2 * sufR[cntR[r] + 1] + 1;
sufR[cntR[r] + 1]++;
cntR[r]++;
if (sumC == sumR)cout << "YES\n";
else cout << "NO\n";
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)solve();
}
