Thanks for participating. We apologize for problem F that has appeared before. Still, we hope you all enjoy our round!↵
↵
[problem:1705A]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
<spoiler summary="Hint 1">↵
First, sort $h_1 \leq h_2 \leq \dots \leq h_{2n}$. There is a very explicit description to which $h_i$'s work.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
What is the optimal arrangement that maximizes the minimum difference across all pairs?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
We have a very explicit description of whether the arrangement is possible. Sort the heights so that $h_1 \leq h_2 \leq \dots \leq h_{2n}$. Then, there exists such arrangement if and only if all the following conditions hold.↵
$$\begin{align*}↵
h_{n+1}-h_1 &\geq x \\↵
h_{n+2}-h_2 &\geq x \\↵
&\vdots \\↵
h_{2n}-h_n &\geq x↵
\end{align*}$$↵
We present two proofs.↵
↵
-----↵
↵
*Proof 1 (Direct Proof).* Suppose that the arrangement is possible. We will show that for each $i$, we have $h_{n+i}-h_i\geq x$.↵
↵
To do so, note that $n+1$ people who have height in $[h_i, h_{n+i}]$. It's impossible that these $n+1$ people got assigned to different columns (because there are $n$ columns), so there exist two people that got assigned to the same column. ↵
↵
However, because these two people have height in $[h_i, h_{n+i}]$, the difference in heights between these two people is at most $h_{n+i}-h_i$. As the difference is at least $x$ by the arrangement, we must have that $h_{n+i}-h_i\geq x$. $\blacksquare$↵
↵
-----↵
↵
*Proof 2 (Exchange Argument).* First, we look at two pairs. Suppose that the $i$-th person in the first and second row have heights $a < b$, while the $j$-th person in the first and second row have heights $c < d$. ↵
$$\begin{array}{ccccc}↵
\dots & a & \dots & c & \dots \\↵
\dots & b & \dots & d & \dots↵
\end{array}$$↵
↵
* Assume that $b\geq c$, then we switch $b,c$. The arrangement still works since $a-c \geq a-b \geq x$ and $b-d \geq c-d \geq x$.↵
* Similarly, $a\geq d$ yields a switch.↵
↵
Thus, we can keep exchanging until anyone in the first row is at least as tall as anyone in the second row. Thus, the first row must be $h_{n+1}, h_{n+2}, \dots, h_{2n}$, while the second row must be $h_1, h_2, \dots, h_n$ in some order.↵
↵
Now, we look at the same picture again. Assume that $a\geq c$ but $b\leq d$. then, we can switch $b,d$, and it still works because $a-d \geq c-d \geq x$ and $c-b \geq c-d \geq x$. Thus, we can switch the second row until it matches the order of the first row.↵
↵
Therefore, we force the first row to be $h_{n+1}, h_{n+2}, \dots, h_{2n}$, while the second row must be $h_1, h_2, \dots, h_n$ in that order. This implies the conclusion. $\blacksquare$↵
↵
-----↵
↵
Time Complexity: $O(n\log n)$ for sorting.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve() {↵
int n, x;↵
cin >> n >> x;↵
vector<int> a(2 * n);↵
for (int i = 0; i < 2 * n; ++i)↵
cin >> a[i];↵
sort(a.begin(), a.end());↵
bool ok = true;↵
for (int i = 0; i < n; ++i)↵
if (a[n + i] - a[i] < x) ok = false;↵
cout << (ok ? "YES" : "NO") << "\n";↵
}↵
↵
int main() {↵
int tt; cin >> tt;↵
while (tt--) solve();↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705B]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
<spoiler summary="Hint">↵
The optimal way is to fill all the zero entries first.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
Delete the leading zeroes in the array $a$ (i.e., the first $t$ numbers of $a$ that are zero) so that now $a_1\ne 0$. Let $k$ be the number of $0$'s in $a_1,a_2,\dots,a_{n-1}$. The answer is↵
$$(a_1+a_2+\dots + a_{n-1}) + k.$$↵
To see why, let Mark keep filling the *holes* (rooms with dust level $0$) first by subtracting the first nonzero index and changing the first zero index to $1$. This takes $k$ moves to fill all zeroes in $a_1,a_2,\dots,a_{n-1}$. Then, we can start moving, from left to right, all dust to the $n$-th room, taking $a_1+a_2+\dots+a_{n-1}$ moves.↵
↵
Finally, we argue that this is the minimum number of moves. To that end, we prove that each move decreases the answer by at most $1$. We consider two cases.↵
↵
* If a move has $j=n$, then it decreases $a_1+a_2+\dots+a_{n-1}$ by $1$ but does not decrease $k$.↵
* If $j\ne n$, then the move doesn't decrease $a_1+a_2+\dots+a_{n-1}$ and decreases $k$ by at most $1$.↵
↵
Thus, we are done. The time complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#define ll long long↵
↵
using namespace std;↵
↵
↵
void solve(){↵
int n; cin >> n;↵
vector<int> a(n);↵
for(int i = 0; i < n; ++i)↵
cin >> a[i];↵
ll ans = 0;↵
int ptr = 0;↵
while(ptr < n && a[ptr] == 0)↵
ptr++;↵
for(int i = ptr; i < n-1; ++i){↵
ans += a[i];↵
if(a[i] == 0) ans++;↵
}↵
cout << ans << "\n";↵
}↵
int main(){↵
int tt; cin >> tt;↵
while(tt--) solve();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705C]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
<spoiler summary="Hint 1">↵
What's in common between all letters that were copied at the same time?</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
The answer is the difference between the current position and the position where it came from. That's what you need to store.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
By tracking the difference, you can recurse to the previously-copied substring.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
This is an implementation problem. What you need to do is after the $i$-th copying operation, we need to keep track of the beginning point $a_i$ and the ending point $b_i$ of the appended string. Moreover, we also keep track the *subtraction distance* $t_i = a_i-l_i$ so that for $k\in [a_i, b_i]$, the $k$-th letter is the same as the $(k-t_i)$-th letter. Thus, we have recursed the position to the smaller position $k-t_i$, so we keep doing that until we reach the initial string.↵
↵
Therefore, to solve this problem, we iterate from $i=c,c-1,\dots,1$. If $k$ is in $[a_i,b_i]$, subtract $k$ by $t_i$. After all operations, $k$ should be at the inital string, and we output the $k$-th letter.↵
↵
The time complexity of this solution is $O(cq)$. However, less efficient solutions of $O((c\log c) q)$ (using binary search each time) or $O(c^2q)$ (by going through all intervals in each iteration) pass as well.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define ll long long↵
↵
using namespace std;↵
↵
void solve(){↵
int n, c, q; cin >> n >> c >> q;↵
string s; cin >> s;↵
↵
vector<ll> left(c+1), right(c+1), diff(c+1);↵
left[0] = 0;↵
right[0] = n;↵
↵
for(int i=1; i<=c; ++i){↵
ll l, r; cin >> l >> r;↵
l--; r--;↵
left[i] = right[i-1];↵
right[i] = left[i] + (r-l+1);↵
diff[i] = left[i] - l;↵
}↵
↵
while(q--){↵
ll k; cin >> k;↵
k--;↵
for(int i=c; i>=1; --i){↵
if(k < left[i]) continue;↵
else k -= diff[i];↵
}↵
cout << s[k] << "\n";↵
}↵
↵
}↵
↵
int main(){↵
int tt; cin >> tt;↵
while(tt--) solve();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705D]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
<spoiler summary="Hint 1">↵
Look at all the $01$'s and $10$'s carefully.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
The sum of the number of $01$'s and $10$'s is constant.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Consider all positions of $01$'s and $10$'s. How does it change in each operation?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
As explained in the sample explanations, the operation cannot change the first or the last bit. Thus, if either $s_1\ne t_1$ or $s_n\ne t_n$, simply return $\texttt{-1}$.↵
↵
Now, the key idea is to consider a binary $\overline{s} = (s_1\oplus s_2)(s_2\oplus s_3) \dots (s_{n-1}\oplus s_n)$ of length $n-1$, where $a\oplus b$ denotes the XOR operation of bits $a$ and $b$. Then, it's easy to verify that the operation acts on $\overline{s}$ by just swapping two different bits. An example is shown below↵
$$↵
\begin{array}{cc}↵
s & \overline s \\↵
\texttt{000101} & \texttt{00111} \\↵
\downarrow & \downarrow \\↵
\texttt{001101} & \texttt{01011}\\↵
\downarrow & \downarrow \\↵
\texttt{011101} & \texttt{10011} \\↵
\downarrow & \downarrow \\↵
\texttt{011001} & \texttt{10101} \\↵
\downarrow & \downarrow \\↵
\texttt{011011} & \texttt{10110} \\↵
\downarrow & \downarrow \\↵
\texttt{010011} & \texttt{11010}↵
\end{array}$$↵
Thus, the operation is possible if and only if $\overline s$ and $\overline t$ has the same number of $1$'s. Moreover, if $a_1,a_2,\dots,a_k$ are the positions of $1$'s in $\overline s$ and $b_1,b_2,\dots,b_k$ are the positions of $1$'s in $\overline t$. Then, the minimum number of moves is given by↵
$$|a_1-b_1| + |a_2-b_2| + \dots + |a_k-b_k|,$$↵
which can be evaluated in $O(n)$.↵
↵
This is a well-known fact, but for completeness, here is the proof. Note that the operation is moving $1$ to left or right by one position. Thus, to achieve that number of moves, simply move the first $1$ from $a_1$ to $b_1$, move the second $1$ from $a_2$ to $b_2$, $\ldots$, and move the $k$-th $1$ from $a_k$ to $b_k$. For the lower bound, notice that the $i$-th $1$ cannot move past the $(i-1)$-th or $(i+1)$-th $1$. Thus, it takes at least $|a_i-b_i|$ moves to move the $i$-th $1$ from $a_i$ to $b_i$. Summing gives the conclusion.↵
↵
Note that another way to think about this problem is to look at the block of $1$'s and $0$'s and notice that the number of blocks remains constant. This is more or less the same as the above solution.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
↵
using namespace std;↵
↵
void solve(){↵
int n; cin >> n;↵
string s,t; cin >> s >> t;↵
vector<ll> pos_s, pos_t;↵
↵
if(s[0] != t[0] || s[n-1] != t[n-1]){↵
cout << -1 << "\n";↵
return;↵
}↵
for(int i=0; i<n-1; i++){↵
if(s[i] != s[i+1]) pos_s.push_back(i);↵
if(t[i] != t[i+1]) pos_t.push_back(i);↵
}↵
if(pos_s.size() != pos_t.size()){↵
cout << -1 << "\n";↵
}↵
else{↵
int k = pos_s.size();↵
ll ans = 0;↵
for(int i=0; i<k; ++i){↵
ans += abs(pos_s[i] - pos_t[i]);↵
}↵
cout << ans << "\n";↵
}↵
}↵
↵
int main(){↵
int tt; cin >> tt;↵
while(tt--) solve();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705E]↵
----------------↵
↵
Author: [user:abc241,2022-07-15]↵
↵
<spoiler summary="Hint 1">↵
Find a concise description of the answer first.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Think about power of two.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
The sum $2^{a_1}+2^{a_2}+\dots+2^{a_n}$ is constant. Show that the answer must be the most significant bit of that.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Use either bitset or lazy segment tree to simulate the addition/subtraction.↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
The key observation is the following.↵
↵
**Claim:** The answer is $\lfloor\log_2(2^{a_1}+2^{a_2}+\dots+2^{a_n})\rfloor.$↵
↵
*Proof:* The upper bound is pretty clear, as thefirst operation doesn't change the $\sum 2^{a_i}$, while the second operation decreases that sum. Thus, $\sum 2^{a_i}$ is always decreasing, and it. Moreover, the sum must be at least $2^{\text{ans}}$, giving the result.↵
↵
For the construction, let Mark keep performing thefirst operation until he cannot. At this point, all numbers must be distinct, and the $\sum 2^{a_i}$ is unchanged. Let the current numbers on the board be $b_1<b_2<\dots < b_k$. Then,↵
$$\sum_{i=1}^n 2^{a_i} = 2^{b_1}+2^{b_2}+\dots + 2^{b_k} \leq 2^1+2^2+\dots+2^{b_k} < 2^{b_k+1}.$$↵
Thus, Mark can make the final number be $b_k = \lfloor\log_2(2^{a_1}+2^{a_2}+\dots+2^{a_n})\rfloor$ as desired. $\blacksquare$↵
↵
------↵
↵
Finally, we need a data structure to maintain the $\sum 2^{a_i}$ and simulate base 2 addition. There are many ways to proceed, including the following:↵
↵
* Using bitsets, partition the bits into many chunks of $w$ bits ($w$ between $50$ and $64$ is fine). This gives $O(n^2/w)$ complexity, but its low constant factor makes it enough to pass comfortably.↵
↵
* Use lazy segment augmented with $O(\log n)$ binary search. For each bit added, find where the longest streak of $1$'s to the left of that bit ends, and update accordingly. Similarly, for each bit subtracted, find where the longest streak of $0$'s to the left of that bit ends, and update accordingly. The total complexity is $O(n\log n)$.↵
</spoiler>↵
↵
<spoiler summary="Code (Bitsets, by errorgorn)">↵
↵
~~~~~↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")↵
↵
// Super Idol的笑容↵
// 都没你的甜↵
// 八月正午的阳光↵
// 都没你耀眼↵
// 热爱105°C的你↵
// 滴滴清纯的蒸馏水↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define ii pair<ll,ll>↵
#define iii pair<ii,ll>↵
#define fi first↵
#define se second↵
#define endl '\n'↵
#define debug(x) cout << #x << ": " << x << endl↵
↵
#define pub push_back↵
#define pob pop_back↵
#define puf push_front↵
#define pof pop_front↵
#define lb lower_bound↵
#define ub upper_bound↵
↵
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))↵
#define all(x) (x).begin(),(x).end()↵
#define sz(x) (int)(x).size()↵
↵
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());↵
↵
struct bitset{↵
unsigned long long arr[3130]={};↵
unsigned long long AF=-1ull;↵
↵
void flip(int l,int r){↵
arr[l/64]^=(1ull<<(l%64))-1;↵
if (r%64==63) arr[r/64]^=AF;↵
else arr[r/64]^=(1ull<<(r%64+1))-1;↵
l/=64,r/=64;↵
if (l==r) return;↵
arr[l]^=AF;↵
↵
for (int x=l+1;x<r;x++) arr[x]^=AF;↵
}↵
↵
int get(int i){↵
if (arr[i/64]&(1ull<<(i%64))) return 1;↵
else return 0;↵
}↵
↵
int get1(int i){↵
//search [i%64,64) on i/64 first↵
unsigned long long mask=AF^((1ull<<(i%64))-1);↵
↵
i=i/64;↵
unsigned long long temp=arr[i]&mask;↵
if (temp) return i*64+__builtin_ctzll(temp);↵
i++;↵
while (true){↵
if (arr[i]==0) i++;↵
else return i*64+__builtin_ctzll(arr[i]);↵
}↵
}↵
↵
int get0(int i){↵
//search [i%64,64) on i/64 first↵
unsigned long long mask=AF^((1ull<<(i%64))-1);↵
↵
i=i/64;↵
unsigned long long temp=(arr[i]^AF)&mask;↵
if (temp) return i*64+__builtin_ctzll(temp);↵
i++;↵
while (true){↵
if (arr[i]==AF) i++;↵
else return i*64+__builtin_ctzll(arr[i]^AF);↵
}↵
}↵
↵
int gethigh(){↵
int i=3129;↵
while (true){↵
if (arr[i]==0) i--;↵
else return i*64+63-__builtin_clzll(arr[i]);↵
}↵
}↵
} BS;↵
↵
int n,q;↵
int arr[200005];↵
↵
void add(int i){↵
BS.flip(i,BS.get0(i));↵
}↵
↵
void del(int i){↵
BS.flip(i,BS.get1(i));↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
cin.exceptions(ios::badbit | ios::failbit);↵
↵
cin>>n>>q;↵
rep(x,1,n+1) cin>>arr[x];↵
rep(x,1,n+1) add(arr[x]);↵
↵
int a,b;↵
while (q--){↵
cin>>a>>b;↵
del(arr[a]);↵
arr[a]=b;↵
add(arr[a]);↵
↵
cout<<BS.gethigh()<<endl;↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Code (Lazy Segment)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
struct LazySeg {↵
int l, r;↵
int val = 0, tag = 0;↵
bool is_lazy = false;↵
LazySeg * l_child = NULL, * r_child = NULL;↵
↵
LazySeg(int _l, int _r) {↵
l = _l;↵
r = _r;↵
if (r - l > 1) {↵
int m = (l + r) / 2;↵
l_child = new LazySeg(l, m);↵
r_child = new LazySeg(m, r);↵
}↵
}~LazySeg() {↵
delete l_child;↵
delete r_child;↵
}↵
void unlazy() {↵
if (!is_lazy) return;↵
val = (r - l) * tag;↵
if (r - l <= 1) return;↵
l_child -> tag = tag;↵
l_child -> is_lazy = true;↵
r_child -> tag = tag;↵
r_child -> is_lazy = true;↵
tag = 0;↵
is_lazy = false;↵
}↵
void update(int from, int to, int x) {↵
unlazy();↵
if (from >= r || l >= to) return;↵
if (from <= l && to >= r) {↵
tag = x;↵
is_lazy = true;↵
unlazy();↵
} else {↵
l_child -> update(from, to, x);↵
r_child -> update(from, to, x);↵
val = l_child -> val + r_child -> val;↵
}↵
}↵
int query(int from, int to) {↵
if (from >= r || l >= to) return 0;↵
unlazy();↵
if (from <= l && to >= r) return val;↵
else {↵
if (l_child == NULL) return 0;↵
return l_child -> query(from, to) + r_child -> query(from, to);↵
}↵
}↵
//pre = prefix in [l,k)↵
int max_right(int k, int pre, int v) {↵
unlazy();↵
if (r - l == 1) {↵
if (val == v) return l;↵
else return l - 1;↵
}↵
l_child -> unlazy();↵
int mid = (l + r) / 2;↵
if (mid <= k) {↵
return r_child -> max_right(k, pre - l_child -> val, v);↵
} else if (l_child -> val - pre == v * (mid - k)) {↵
//left to mid-1 has all 1's => answer must be >= mid-1↵
return r_child -> max_right(mid, 0, v);↵
} else {↵
return l_child -> max_right(k, pre, v);↵
}↵
}↵
//suff = suffix↵
int get_answer() {↵
unlazy();↵
if (r - l == 1) {↵
if (val == 1) return l;↵
else return l - 1;↵
}↵
r_child -> unlazy();↵
if (r_child -> val == 0) {↵
//[mid to end] are all 0↵
return l_child -> get_answer();↵
} else {↵
return r_child -> get_answer();↵
}↵
}↵
};↵
↵
signed main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
↵
int n, q;↵
cin >> n >> q;↵
LazySeg tr(0, 200100);↵
↵
auto add = [ & ](int x) {↵
int y = tr.max_right(x, tr.query(0, x), 1) + 1;↵
if (y == x) { //no carry; just change 0 to 1↵
tr.update(x, x + 1, 1);↵
} else { //there is a carry; set the whole block of 1's to 0↵
tr.update(x, y, 0);↵
tr.update(y, y + 1, 1);↵
}↵
};↵
↵
auto remove = [ & ](int x) {↵
int y = tr.max_right(x, tr.query(0, x), 0) + 1;↵
if (y == x) {↵
tr.update(x, x + 1, 0);↵
} else {↵
tr.update(x, y, 1);↵
tr.update(y, y + 1, 0);↵
}↵
};↵
vector < int > a(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
add(a[i]);↵
}↵
while (q--) {↵
int k, l; cin >> k >> l;↵
k--; ↵
remove(a[k]); add(l);↵
a[k] = l;↵
cout << tr.get_answer() << "\n";↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705F]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
Unfortunately, a harder version of this problem has appeared in a Chinese contest [here](https://www.luogu.com.cn/problem/P7848) and [here](https://www.luogu.com.cn/problem/T183641). You can look at their solution [here](https://www.luogu.com.cn/blog/1973224568qq/kao-shi-2021-coe-iii-d#). We thank many contestants who pointed it out.↵
↵
<spoiler summary="Hint 0">↵
It's possible to solve this problem without any randomization. See the subsequent hints for how to do so.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
Observe that we can take differences between two very close queries to get the number of $\texttt{T}$'s in a small subsequence.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
You can take the difference against a pre-computed query. Applying this with a group of two questions.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
You have three possibilities: either $\texttt{TT}$, $\texttt{FF}$, and $\{\texttt{TF}, \texttt{FT}\}$. If the third possibility happens, simultaneously figure out whether is $\texttt{TF}$ or $\texttt{FT}$ and answer one question within one query.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
You will need to precompute the query $\texttt{TFTF}\dots\texttt{TF}$.↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
There are many possible approaches, including using randomized algorithms. However, I will present the solution that takes about $\tfrac{2n}{3}$ queries deterministically.↵
↵
We pre-query $\texttt{TTT...T}$ and $\texttt{TFTF...TF}$. Then, for $i=1,2,\dots,\left\lfloor\frac n3\right\rfloor$, we take the difference when both the $(2i-1)$-th and the $2i$-th question in $\texttt{TTT...T}$ is changed to $\texttt{F}$.↵
↵
* If the difference is $+1$, then both answers must be $\texttt F$.↵
* If the difference is $-1$, then both answers must be $\texttt T$.↵
* Else, the answers must be $\texttt{TF}$ or $\texttt{FT}$ in some order.↵
↵
Now, here is the key idea: if the last case happens, then we can figure out if it's $\texttt{TF}$ or $\texttt{FT}$ **as well as** the answer to one more question in one query. To do so, compare the previous $\texttt{TFTF...TF}$ with a new query that has $3$ differences:↵
$$\begin{align*} \\↵
\texttt{TFTF} \dots \texttt{TF} \dots \texttt{T} \dots \texttt{TF} \\↵
\texttt{TFTF} \dots \color{red}{\texttt{FT}} \dots \color{red}{\texttt F} \dots \texttt{TF}↵
\end{align*}$$↵
(Note: we assume that the third question corresponds to $\texttt T$ in the query. If it's $\texttt F$, just change to $\texttt T$ and proceed analogously.)↵
↵
There are four possible scenarios.↵
↵
* If the answers are $\texttt{TF}$ and $\texttt{T}$, then the difference is $-3$.↵
* If the answers are $\texttt{TF}$ and $\texttt{F}$, then the difference is $-1$.↵
* If the answers are $\texttt{FT}$ and $\texttt{T}$, then the difference is $+1$.↵
* If the answers are $\texttt{FT}$ and $\texttt{F}$, then the difference is $+3$.↵
↵
Therefore, we can distinguish these four scenarios in one go.↵
↵
Finally, if the first two cases happen, we can easily figure out the answer to one more question in one query (say, by changing that question to $\texttt F$ and compare with the $\texttt{TT...T}$ query). Either way, we can deduce the answer to $3$ questions in $2$ queries, leading to a solution with $\tfrac{2n}{3}$ queries.↵
↵
Note that this solution can be easily improved to $\frac {3n}{5}$ on average by randomly shuffling the questions.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int query(string s){↵
cout << s << endl;↵
cout.flush();↵
int x; cin >> x;↵
if(x==n) exit(0);↵
return x;↵
}↵
↵
int main(){↵
int n; cin >> n;↵
↵
//query true count↵
string all_T(n, 'T'), ans(n, '?');↵
int cnt_T = query(all_T);↵
↵
//query TF↵
string all_TF(n, 'T');↵
for(int i=1; i<n; i+=2) all_TF[i] = 'F';↵
int cnt_TF = query(all_TF);↵
↵
//begin the loop↵
int l = 0, r = n-1;↵
while(r >= l){↵
if(r==l){ //only l is undetermined↵
string s(all_T);↵
s[l] = 'F';↵
int k = query(s);↵
↵
if(k > cnt_T){↵
ans[l] = 'F';↵
}↵
else{↵
ans[l] = 'T';↵
}↵
l++; r--;↵
}↵
else{↵
string s(all_T);↵
s[l] = 'F'; s[l+1] = 'F';↵
int k = query(s) - cnt_T;↵
↵
if(k == 2){↵
ans[l] = 'F'; ans[l+1] = 'F';↵
l += 2;↵
}↵
else if(k == -2){↵
ans[l] = 'T'; ans[l+1] = 'T';↵
l += 2;↵
}↵
else{↵
if(r == l+1){ //only l and l+1 left; figure out the order↵
string s(all_T);↵
s[l] = 'F';↵
int k = query(s);↵
↵
if(k > cnt_T){↵
ans[l] = 'F'; ans[l+1] = 'T';↵
}↵
else{↵
ans[l] = 'T'; ans[l+1] = 'F';↵
}↵
l += 2;↵
}↵
else{ //determine l, l+1, r↵
string s(all_TF);↵
s[l] = 'F'; s[l+1] = 'T';↵
↵
if(s[r] == 'F') s[r] = 'T';↵
else s[r] = 'F';↵
↵
int k = query(s) - cnt_TF;↵
if(k == 3){↵
ans[l] = 'F'; ans[l+1] = 'T'; ans[r] = s[r];↵
}↵
else if(k == 1){↵
ans[l] = 'F'; ans[l+1] = 'T'; ans[r] = all_TF[r];↵
}↵
else if(k == -1){↵
ans[l] = 'T'; ans[l+1] = 'F'; ans[r] = s[r];↵
}↵
else{↵
ans[l] = 'T'; ans[l+1] = 'F'; ans[r] = all_TF[r];↵
}↵
l += 2; r--;↵
}↵
}↵
}↵
}↵
query(ans);↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1705A]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
<spoiler summary="Hint 1">↵
First, sort $h_1 \leq h_2 \leq \dots \leq h_{2n}$. There is a very explicit description to which $h_i$'s work.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
What is the optimal arrangement that maximizes the minimum difference across all pairs?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
We have a very explicit description of whether the arrangement is possible. Sort the heights so that $h_1 \leq h_2 \leq \dots \leq h_{2n}$. Then, there exists such arrangement if and only if all the following conditions hold.↵
$$\begin{align*}↵
h_{n+1}-h_1 &\geq x \\↵
h_{n+2}-h_2 &\geq x \\↵
&\vdots \\↵
h_{2n}-h_n &\geq x↵
\end{align*}$$↵
We present two proofs.↵
↵
-----↵
↵
*Proof 1 (Direct Proof).* Suppose that the arrangement is possible. We will show that for each $i$, we have $h_{n+i}-h_i\geq x$.↵
↵
To do so, note that $n+1$ people who have height in $[h_i, h_{n+i}]$. It's impossible that these $n+1$ people got assigned to different columns (because there are $n$ columns), so there exist two people that got assigned to the same column. ↵
↵
However, because these two people have height in $[h_i, h_{n+i}]$, the difference in heights between these two people is at most $h_{n+i}-h_i$. As the difference is at least $x$ by the arrangement, we must have that $h_{n+i}-h_i\geq x$. $\blacksquare$↵
↵
-----↵
↵
*Proof 2 (Exchange Argument).* First, we look at two pairs. Suppose that the $i$-th person in the first and second row have heights $a < b$, while the $j$-th person in the first and second row have heights $c < d$. ↵
$$\begin{array}{ccccc}↵
\dots & a & \dots & c & \dots \\↵
\dots & b & \dots & d & \dots↵
\end{array}$$↵
↵
* Assume that $b\geq c$, then we switch $b,c$. The arrangement still works since $a-c \geq a-b \geq x$ and $b-d \geq c-d \geq x$.↵
* Similarly, $a\geq d$ yields a switch.↵
↵
Thus, we can keep exchanging until anyone in the first row is at least as tall as anyone in the second row. Thus, the first row must be $h_{n+1}, h_{n+2}, \dots, h_{2n}$, while the second row must be $h_1, h_2, \dots, h_n$ in some order.↵
↵
Now, we look at the same picture again. Assume that $a\geq c$ but $b\leq d$. then, we can switch $b,d$, and it still works because $a-d \geq c-d \geq x$ and $c-b \geq c-d \geq x$. Thus, we can switch the second row until it matches the order of the first row.↵
↵
Therefore, we force the first row to be $h_{n+1}, h_{n+2}, \dots, h_{2n}$, while the second row must be $h_1, h_2, \dots, h_n$ in that order. This implies the conclusion. $\blacksquare$↵
↵
-----↵
↵
Time Complexity: $O(n\log n)$ for sorting.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve() {↵
int n, x;↵
cin >> n >> x;↵
vector<int> a(2 * n);↵
for (int i = 0; i < 2 * n; ++i)↵
cin >> a[i];↵
sort(a.begin(), a.end());↵
bool ok = true;↵
for (int i = 0; i < n; ++i)↵
if (a[n + i] - a[i] < x) ok = false;↵
cout << (ok ? "YES" : "NO") << "\n";↵
}↵
↵
int main() {↵
int tt; cin >> tt;↵
while (tt--) solve();↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705B]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
<spoiler summary="Hint">↵
The optimal way is to fill all the zero entries first.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
Delete the leading zeroes in the array $a$ (i.e., the first $t$ numbers of $a$ that are zero) so that now $a_1\ne 0$. Let $k$ be the number of $0$'s in $a_1,a_2,\dots,a_{n-1}$. The answer is↵
$$(a_1+a_2+\dots + a_{n-1}) + k.$$↵
To see why, let Mark keep filling the *holes* (rooms with dust level $0$) first by subtracting the first nonzero index and changing the first zero index to $1$. This takes $k$ moves to fill all zeroes in $a_1,a_2,\dots,a_{n-1}$. Then, we can start moving, from left to right, all dust to the $n$-th room, taking $a_1+a_2+\dots+a_{n-1}$ moves.↵
↵
Finally, we argue that this is the minimum number of moves. To that end, we prove that each move decreases the answer by at most $1$. We consider two cases.↵
↵
* If a move has $j=n$, then it decreases $a_1+a_2+\dots+a_{n-1}$ by $1$ but does not decrease $k$.↵
* If $j\ne n$, then the move doesn't decrease $a_1+a_2+\dots+a_{n-1}$ and decreases $k$ by at most $1$.↵
↵
Thus, we are done. The time complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#define ll long long↵
↵
using namespace std;↵
↵
↵
void solve(){↵
int n; cin >> n;↵
vector<int> a(n);↵
for(int i = 0; i < n; ++i)↵
cin >> a[i];↵
ll ans = 0;↵
int ptr = 0;↵
while(ptr < n && a[ptr] == 0)↵
ptr++;↵
for(int i = ptr; i < n-1; ++i){↵
ans += a[i];↵
if(a[i] == 0) ans++;↵
}↵
cout << ans << "\n";↵
}↵
int main(){↵
int tt; cin >> tt;↵
while(tt--) solve();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705C]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
<spoiler summary="Hint 1">↵
What's in common between all letters that were copied at the same time?</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
The answer is the difference between the current position and the position where it came from. That's what you need to store.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
By tracking the difference, you can recurse to the previously-copied substring.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
This is an implementation problem. What you need to do is after the $i$-th copying operation, we need to keep track of the beginning point $a_i$ and the ending point $b_i$ of the appended string. Moreover, we also keep track the *subtraction distance* $t_i = a_i-l_i$ so that for $k\in [a_i, b_i]$, the $k$-th letter is the same as the $(k-t_i)$-th letter. Thus, we have recursed the position to the smaller position $k-t_i$, so we keep doing that until we reach the initial string.↵
↵
Therefore, to solve this problem, we iterate from $i=c,c-1,\dots,1$. If $k$ is in $[a_i,b_i]$, subtract $k$ by $t_i$. After all operations, $k$ should be at the inital string, and we output the $k$-th letter.↵
↵
The time complexity of this solution is $O(cq)$. However, less efficient solutions of $O((c\log c) q)$ (using binary search each time) or $O(c^2q)$ (by going through all intervals in each iteration) pass as well.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define ll long long↵
↵
using namespace std;↵
↵
void solve(){↵
int n, c, q; cin >> n >> c >> q;↵
string s; cin >> s;↵
↵
vector<ll> left(c+1), right(c+1), diff(c+1);↵
left[0] = 0;↵
right[0] = n;↵
↵
for(int i=1; i<=c; ++i){↵
ll l, r; cin >> l >> r;↵
l--; r--;↵
left[i] = right[i-1];↵
right[i] = left[i] + (r-l+1);↵
diff[i] = left[i] - l;↵
}↵
↵
while(q--){↵
ll k; cin >> k;↵
k--;↵
for(int i=c; i>=1; --i){↵
if(k < left[i]) continue;↵
else k -= diff[i];↵
}↵
cout << s[k] << "\n";↵
}↵
↵
}↵
↵
int main(){↵
int tt; cin >> tt;↵
while(tt--) solve();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705D]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
<spoiler summary="Hint 1">↵
Look at all the $01$'s and $10$'s carefully.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
The sum of the number of $01$'s and $10$'s is constant.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Consider all positions of $01$'s and $10$'s. How does it change in each operation?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
As explained in the sample explanations, the operation cannot change the first or the last bit. Thus, if either $s_1\ne t_1$ or $s_n\ne t_n$, simply return $\texttt{-1}$.↵
↵
Now, the key idea is to consider a binary $\overline{s} = (s_1\oplus s_2)(s_2\oplus s_3) \dots (s_{n-1}\oplus s_n)$ of length $n-1$, where $a\oplus b$ denotes the XOR operation of bits $a$ and $b$. Then, it's easy to verify that the operation acts on $\overline{s}$ by just swapping two different bits. An example is shown below↵
$$↵
\begin{array}{cc}↵
s & \overline s \\↵
\texttt{000101} & \texttt{00111} \\↵
\downarrow & \downarrow \\↵
\texttt{001101} & \texttt{01011}\\↵
\downarrow & \downarrow \\↵
\texttt{011101} & \texttt{10011} \\↵
\downarrow & \downarrow \\↵
\texttt{011001} & \texttt{10101} \\↵
\downarrow & \downarrow \\↵
\texttt{011011} & \texttt{10110} \\↵
\downarrow & \downarrow \\↵
\texttt{010011} & \texttt{11010}↵
\end{array}$$↵
Thus, the operation is possible if and only if $\overline s$ and $\overline t$ has the same number of $1$'s. Moreover, if $a_1,a_2,\dots,a_k$ are the positions of $1$'s in $\overline s$ and $b_1,b_2,\dots,b_k$ are the positions of $1$'s in $\overline t$. Then, the minimum number of moves is given by↵
$$|a_1-b_1| + |a_2-b_2| + \dots + |a_k-b_k|,$$↵
which can be evaluated in $O(n)$.↵
↵
This is a well-known fact, but for completeness, here is the proof. Note that the operation is moving $1$ to left or right by one position. Thus, to achieve that number of moves, simply move the first $1$ from $a_1$ to $b_1$, move the second $1$ from $a_2$ to $b_2$, $\ldots$, and move the $k$-th $1$ from $a_k$ to $b_k$. For the lower bound, notice that the $i$-th $1$ cannot move past the $(i-1)$-th or $(i+1)$-th $1$. Thus, it takes at least $|a_i-b_i|$ moves to move the $i$-th $1$ from $a_i$ to $b_i$. Summing gives the conclusion.↵
↵
Note that another way to think about this problem is to look at the block of $1$'s and $0$'s and notice that the number of blocks remains constant. This is more or less the same as the above solution.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
↵
using namespace std;↵
↵
void solve(){↵
int n; cin >> n;↵
string s,t; cin >> s >> t;↵
vector<ll> pos_s, pos_t;↵
↵
if(s[0] != t[0] || s[n-1] != t[n-1]){↵
cout << -1 << "\n";↵
return;↵
}↵
for(int i=0; i<n-1; i++){↵
if(s[i] != s[i+1]) pos_s.push_back(i);↵
if(t[i] != t[i+1]) pos_t.push_back(i);↵
}↵
if(pos_s.size() != pos_t.size()){↵
cout << -1 << "\n";↵
}↵
else{↵
int k = pos_s.size();↵
ll ans = 0;↵
for(int i=0; i<k; ++i){↵
ans += abs(pos_s[i] - pos_t[i]);↵
}↵
cout << ans << "\n";↵
}↵
}↵
↵
int main(){↵
int tt; cin >> tt;↵
while(tt--) solve();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705E]↵
----------------↵
↵
Author: [user:abc241,2022-07-15]↵
↵
<spoiler summary="Hint 1">↵
Find a concise description of the answer first.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Think about power of two.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
The sum $2^{a_1}+2^{a_2}+\dots+2^{a_n}$ is constant. Show that the answer must be the most significant bit of that.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Use either bitset or lazy segment tree to simulate the addition/subtraction.↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
The key observation is the following.↵
↵
**Claim:** The answer is $\lfloor\log_2(2^{a_1}+2^{a_2}+\dots+2^{a_n})\rfloor.$↵
↵
*Proof:* The upper bound is pretty clear, as the
↵
For the construction, let Mark keep performing the
$$\sum_{i=1}^n 2^{a_i} = 2^{b_1}+2^{b_2}+\dots + 2^{b_k} \leq 2^1+2^2+\dots+2^{b_k} < 2^{b_k+1}.$$↵
Thus, Mark can make the final number be $b_k = \lfloor\log_2(2^{a_1}+2^{a_2}+\dots+2^{a_n})\rfloor$ as desired. $\blacksquare$↵
↵
------↵
↵
Finally, we need a data structure to maintain the $\sum 2^{a_i}$ and simulate base 2 addition. There are many ways to proceed, including the following:↵
↵
* Using bitsets, partition the bits into many chunks of $w$ bits ($w$ between $50$ and $64$ is fine). This gives $O(n^2/w)$ complexity, but its low constant factor makes it enough to pass comfortably.↵
↵
* Use lazy segment augmented with $O(\log n)$ binary search. For each bit added, find where the longest streak of $1$'s to the left of that bit ends, and update accordingly. Similarly, for each bit subtracted, find where the longest streak of $0$'s to the left of that bit ends, and update accordingly. The total complexity is $O(n\log n)$.↵
</spoiler>↵
↵
<spoiler summary="Code (Bitsets, by errorgorn)">↵
↵
~~~~~↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")↵
↵
// Super Idol的笑容↵
// 都没你的甜↵
// 八月正午的阳光↵
// 都没你耀眼↵
// 热爱105°C的你↵
// 滴滴清纯的蒸馏水↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define ii pair<ll,ll>↵
#define iii pair<ii,ll>↵
#define fi first↵
#define se second↵
#define endl '\n'↵
#define debug(x) cout << #x << ": " << x << endl↵
↵
#define pub push_back↵
#define pob pop_back↵
#define puf push_front↵
#define pof pop_front↵
#define lb lower_bound↵
#define ub upper_bound↵
↵
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))↵
#define all(x) (x).begin(),(x).end()↵
#define sz(x) (int)(x).size()↵
↵
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());↵
↵
struct bitset{↵
unsigned long long arr[3130]={};↵
unsigned long long AF=-1ull;↵
↵
void flip(int l,int r){↵
arr[l/64]^=(1ull<<(l%64))-1;↵
if (r%64==63) arr[r/64]^=AF;↵
else arr[r/64]^=(1ull<<(r%64+1))-1;↵
l/=64,r/=64;↵
if (l==r) return;↵
arr[l]^=AF;↵
↵
for (int x=l+1;x<r;x++) arr[x]^=AF;↵
}↵
↵
int get(int i){↵
if (arr[i/64]&(1ull<<(i%64))) return 1;↵
else return 0;↵
}↵
↵
int get1(int i){↵
//search [i%64,64) on i/64 first↵
unsigned long long mask=AF^((1ull<<(i%64))-1);↵
↵
i=i/64;↵
unsigned long long temp=arr[i]&mask;↵
if (temp) return i*64+__builtin_ctzll(temp);↵
i++;↵
while (true){↵
if (arr[i]==0) i++;↵
else return i*64+__builtin_ctzll(arr[i]);↵
}↵
}↵
↵
int get0(int i){↵
//search [i%64,64) on i/64 first↵
unsigned long long mask=AF^((1ull<<(i%64))-1);↵
↵
i=i/64;↵
unsigned long long temp=(arr[i]^AF)&mask;↵
if (temp) return i*64+__builtin_ctzll(temp);↵
i++;↵
while (true){↵
if (arr[i]==AF) i++;↵
else return i*64+__builtin_ctzll(arr[i]^AF);↵
}↵
}↵
↵
int gethigh(){↵
int i=3129;↵
while (true){↵
if (arr[i]==0) i--;↵
else return i*64+63-__builtin_clzll(arr[i]);↵
}↵
}↵
} BS;↵
↵
int n,q;↵
int arr[200005];↵
↵
void add(int i){↵
BS.flip(i,BS.get0(i));↵
}↵
↵
void del(int i){↵
BS.flip(i,BS.get1(i));↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
cin.exceptions(ios::badbit | ios::failbit);↵
↵
cin>>n>>q;↵
rep(x,1,n+1) cin>>arr[x];↵
rep(x,1,n+1) add(arr[x]);↵
↵
int a,b;↵
while (q--){↵
cin>>a>>b;↵
del(arr[a]);↵
arr[a]=b;↵
add(arr[a]);↵
↵
cout<<BS.gethigh()<<endl;↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Code (Lazy Segment)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
struct LazySeg {↵
int l, r;↵
int val = 0, tag = 0;↵
bool is_lazy = false;↵
LazySeg * l_child = NULL, * r_child = NULL;↵
↵
LazySeg(int _l, int _r) {↵
l = _l;↵
r = _r;↵
if (r - l > 1) {↵
int m = (l + r) / 2;↵
l_child = new LazySeg(l, m);↵
r_child = new LazySeg(m, r);↵
}↵
}~LazySeg() {↵
delete l_child;↵
delete r_child;↵
}↵
void unlazy() {↵
if (!is_lazy) return;↵
val = (r - l) * tag;↵
if (r - l <= 1) return;↵
l_child -> tag = tag;↵
l_child -> is_lazy = true;↵
r_child -> tag = tag;↵
r_child -> is_lazy = true;↵
tag = 0;↵
is_lazy = false;↵
}↵
void update(int from, int to, int x) {↵
unlazy();↵
if (from >= r || l >= to) return;↵
if (from <= l && to >= r) {↵
tag = x;↵
is_lazy = true;↵
unlazy();↵
} else {↵
l_child -> update(from, to, x);↵
r_child -> update(from, to, x);↵
val = l_child -> val + r_child -> val;↵
}↵
}↵
int query(int from, int to) {↵
if (from >= r || l >= to) return 0;↵
unlazy();↵
if (from <= l && to >= r) return val;↵
else {↵
if (l_child == NULL) return 0;↵
return l_child -> query(from, to) + r_child -> query(from, to);↵
}↵
}↵
//pre = prefix in [l,k)↵
int max_right(int k, int pre, int v) {↵
unlazy();↵
if (r - l == 1) {↵
if (val == v) return l;↵
else return l - 1;↵
}↵
l_child -> unlazy();↵
int mid = (l + r) / 2;↵
if (mid <= k) {↵
return r_child -> max_right(k, pre - l_child -> val, v);↵
} else if (l_child -> val - pre == v * (mid - k)) {↵
//left to mid-1 has all 1's => answer must be >= mid-1↵
return r_child -> max_right(mid, 0, v);↵
} else {↵
return l_child -> max_right(k, pre, v);↵
}↵
}↵
//suff = suffix↵
int get_answer() {↵
unlazy();↵
if (r - l == 1) {↵
if (val == 1) return l;↵
else return l - 1;↵
}↵
r_child -> unlazy();↵
if (r_child -> val == 0) {↵
//[mid to end] are all 0↵
return l_child -> get_answer();↵
} else {↵
return r_child -> get_answer();↵
}↵
}↵
};↵
↵
signed main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
↵
int n, q;↵
cin >> n >> q;↵
LazySeg tr(0, 200100);↵
↵
auto add = [ & ](int x) {↵
int y = tr.max_right(x, tr.query(0, x), 1) + 1;↵
if (y == x) { //no carry; just change 0 to 1↵
tr.update(x, x + 1, 1);↵
} else { //there is a carry; set the whole block of 1's to 0↵
tr.update(x, y, 0);↵
tr.update(y, y + 1, 1);↵
}↵
};↵
↵
auto remove = [ & ](int x) {↵
int y = tr.max_right(x, tr.query(0, x), 0) + 1;↵
if (y == x) {↵
tr.update(x, x + 1, 0);↵
} else {↵
tr.update(x, y, 1);↵
tr.update(y, y + 1, 0);↵
}↵
};↵
vector < int > a(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
add(a[i]);↵
}↵
while (q--) {↵
int k, l; cin >> k >> l;↵
k--; ↵
remove(a[k]); add(l);↵
a[k] = l;↵
cout << tr.get_answer() << "\n";↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705F]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
Unfortunately, a harder version of this problem has appeared in a Chinese contest [here](https://www.luogu.com.cn/problem/P7848) and [here](https://www.luogu.com.cn/problem/T183641). You can look at their solution [here](https://www.luogu.com.cn/blog/1973224568qq/kao-shi-2021-coe-iii-d#). We thank many contestants who pointed it out.↵
↵
<spoiler summary="Hint 0">↵
It's possible to solve this problem without any randomization. See the subsequent hints for how to do so.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
Observe that we can take differences between two very close queries to get the number of $\texttt{T}$'s in a small subsequence.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
You can take the difference against a pre-computed query. Applying this with a group of two questions.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
You have three possibilities: either $\texttt{TT}$, $\texttt{FF}$, and $\{\texttt{TF}, \texttt{FT}\}$. If the third possibility happens, simultaneously figure out whether is $\texttt{TF}$ or $\texttt{FT}$ and answer one question within one query.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
You will need to precompute the query $\texttt{TFTF}\dots\texttt{TF}$.↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
There are many possible approaches, including using randomized algorithms. However, I will present the solution that takes about $\tfrac{2n}{3}$ queries deterministically.↵
↵
We pre-query $\texttt{TTT...T}$ and $\texttt{TFTF...TF}$. Then, for $i=1,2,\dots,\left\lfloor\frac n3\right\rfloor$, we take the difference when both the $(2i-1)$-th and the $2i$-th question in $\texttt{TTT...T}$ is changed to $\texttt{F}$.↵
↵
* If the difference is $+1$, then both answers must be $\texttt F$.↵
* If the difference is $-1$, then both answers must be $\texttt T$.↵
* Else, the answers must be $\texttt{TF}$ or $\texttt{FT}$ in some order.↵
↵
Now, here is the key idea: if the last case happens, then we can figure out if it's $\texttt{TF}$ or $\texttt{FT}$ **as well as** the answer to one more question in one query. To do so, compare the previous $\texttt{TFTF...TF}$ with a new query that has $3$ differences:↵
$$\begin{align*} \\↵
\texttt{TFTF} \dots \texttt{TF} \dots \texttt{T} \dots \texttt{TF} \\↵
\texttt{TFTF} \dots \color{red}{\texttt{FT}} \dots \color{red}{\texttt F} \dots \texttt{TF}↵
\end{align*}$$↵
(Note: we assume that the third question corresponds to $\texttt T$ in the query. If it's $\texttt F$, just change to $\texttt T$ and proceed analogously.)↵
↵
There are four possible scenarios.↵
↵
* If the answers are $\texttt{TF}$ and $\texttt{T}$, then the difference is $-3$.↵
* If the answers are $\texttt{TF}$ and $\texttt{F}$, then the difference is $-1$.↵
* If the answers are $\texttt{FT}$ and $\texttt{T}$, then the difference is $+1$.↵
* If the answers are $\texttt{FT}$ and $\texttt{F}$, then the difference is $+3$.↵
↵
Therefore, we can distinguish these four scenarios in one go.↵
↵
Finally, if the first two cases happen, we can easily figure out the answer to one more question in one query (say, by changing that question to $\texttt F$ and compare with the $\texttt{TT...T}$ query). Either way, we can deduce the answer to $3$ questions in $2$ queries, leading to a solution with $\tfrac{2n}{3}$ queries.↵
↵
Note that this solution can be easily improved to $\frac {3n}{5}$ on average by randomly shuffling the questions.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int query(string s){↵
cout << s << endl;↵
cout.flush();↵
int x; cin >> x;↵
if(x==n) exit(0);↵
return x;↵
}↵
↵
int main(){↵
int n; cin >> n;↵
↵
//query true count↵
string all_T(n, 'T'), ans(n, '?');↵
int cnt_T = query(all_T);↵
↵
//query TF↵
string all_TF(n, 'T');↵
for(int i=1; i<n; i+=2) all_TF[i] = 'F';↵
int cnt_TF = query(all_TF);↵
↵
//begin the loop↵
int l = 0, r = n-1;↵
while(r >= l){↵
if(r==l){ //only l is undetermined↵
string s(all_T);↵
s[l] = 'F';↵
int k = query(s);↵
↵
if(k > cnt_T){↵
ans[l] = 'F';↵
}↵
else{↵
ans[l] = 'T';↵
}↵
l++; r--;↵
}↵
else{↵
string s(all_T);↵
s[l] = 'F'; s[l+1] = 'F';↵
int k = query(s) - cnt_T;↵
↵
if(k == 2){↵
ans[l] = 'F'; ans[l+1] = 'F';↵
l += 2;↵
}↵
else if(k == -2){↵
ans[l] = 'T'; ans[l+1] = 'T';↵
l += 2;↵
}↵
else{↵
if(r == l+1){ //only l and l+1 left; figure out the order↵
string s(all_T);↵
s[l] = 'F';↵
int k = query(s);↵
↵
if(k > cnt_T){↵
ans[l] = 'F'; ans[l+1] = 'T';↵
}↵
else{↵
ans[l] = 'T'; ans[l+1] = 'F';↵
}↵
l += 2;↵
}↵
else{ //determine l, l+1, r↵
string s(all_TF);↵
s[l] = 'F'; s[l+1] = 'T';↵
↵
if(s[r] == 'F') s[r] = 'T';↵
else s[r] = 'F';↵
↵
int k = query(s) - cnt_TF;↵
if(k == 3){↵
ans[l] = 'F'; ans[l+1] = 'T'; ans[r] = s[r];↵
}↵
else if(k == 1){↵
ans[l] = 'F'; ans[l+1] = 'T'; ans[r] = all_TF[r];↵
}↵
else if(k == -1){↵
ans[l] = 'T'; ans[l+1] = 'F'; ans[r] = s[r];↵
}↵
else{↵
ans[l] = 'T'; ans[l+1] = 'F'; ans[r] = all_TF[r];↵
}↵
l += 2; r--;↵
}↵
}↵
}↵
}↵
query(ans);↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
