codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1810.md (29476B)


      1 Source: https://codeforces.com/blog/entry/114521
      2 
      3 [A. Beautiful Sequence](https://codeforces.com/contest/1810/problem/A)
      4 
      5 **Hint**
      6 
      7 What is the necessary and sufficient condition?
      8 
      9 **Tutorial**
     10 
     11 The necessary and sufficient condition for a beautiful sequence is that there exist one $i$, such that $a_{i} \le i$. Just check the sequence for the condition.
     12 
     13 **Solution**
     14 
     15 ```
     16 #include<bits/stdc++.h>
     17 using namespace std;
     18 int a[100005];
     19 void solve()
     20 {
     21     int n;
     22     scanf("%d",&n);
     23     for(int i  =1;i <= n;i++) scanf("%d",&a[i]);
     24     for(int i = 1;i <= n;i++) {
     25         if(a[i] <= i) {
     26             puts("YES");
     27             return;
     28         }
     29     }
     30     puts("NO");
     31 }
     32 int main()
     33 {
     34     int t;scanf("%d",&t);
     35     while(t--) solve();
     36 }
     37 ```
     38 
     39 [B. Candies](https://codeforces.com/contest/1810/problem/B)
     40 
     41 **Hint**
     42 
     43 How the binary representation changes after an operation?
     44 
     45 **Tutorial**
     46 
     47 First, we notice that after each operation, the number of candies is always a odd number. So even numbers can not be achieved.
     48 
     49 Then consider how the binary representation changes for a odd number $x$, after turn it into $2x+1$ or $2x-1$.
     50 
     51 * For the $2x + 1$ operation: $\overline{\dots 1}$ turns into $\overline{\dots 11}$.
     52 * For the $2x - 1$ operation: $\overline{\dots 1}$ turns into $\overline{\dots 01}$.
     53 
     54 So, the operation is just insert a $0/1$ before the last digit. And the answer for an odd $n$ is just the binary representation of $n$, after removing the last digit.
     55 
     56 **Solution**
     57 
     58 ```
     59 #include<bits/stdc++.h>
     60 using namespace std;
     61 void solve()
     62 {
     63     int n;scanf("%d",&n);
     64     if(n % 2 == 0) {
     65         puts("-1");return;
     66     }
     67     vector<int> v;
     68     int f = 0;
     69     for(int i = 29;i >= 1;i--) {
     70         if((n >> i) & 1) {
     71             f = 1;
     72             v.push_back(2);
     73         }
     74         else if(f) {
     75             v.push_back(1);
     76         }
     77     }
     78     printf("%d\n",v.size());
     79     for(auto x : v) {
     80         printf("%d ",x);
     81     }
     82     printf("\n");
     83 }
     84 int main()
     85 {
     86     int t;scanf("%d",&t);
     87     while(t--) solve();
     88     return 0;
     89 }
     90 ```
     91 
     92 [C.Make It Permutation](https://codeforces.com/contest/1810/problem/C)
     93 
     94 **Hint 1**
     95 
     96 Try the enumerate the length $n$ of permutation.
     97 
     98 **Hint 2**
     99 
    100 There're too many lengths to be checked. How to decrease the amount of $n$?
    101 
    102 **Tutorial**
    103 
    104 Firstly, we need to remove numbers such that each number appears at most once, this part of cost is unavoidable. Then, let's sort the array $a_{1},a_{2} \dots a_{m}$ ($1\le a_{i} \lt a_{2} \lt \dots \lt a_{m}$).
    105 
    106 Secondly, assume we enumerate the length of the permutation $n$. We need to remove all the $a_{i}$ greater than $n$, and insert some numbers $x$ ($x \le n$) but does not appear in the array $a$. We can find some $i$ such that $a_{i} \le n \lt a_{i+1}$, the cost here is simply $(m-i)\cdot a + (n - i)\cdot b$. Here, $m$ is the length of array $a$, after removing the repeated numbers.
    107 
    108 However, $n$ can up to $10^9$ and can not be enumerated. But for all the $n \in [a_{i} , a_{i+1})$, the smaller $n$ has a smaller cost. (see that $(m-i)\cdot a$ do not change, and $(n-i)\cdot b$ decreases). Thus, the possible $n$ can only be some $a_{i}$, and we can caculate the cost in $O(n)$ in total.
    109 
    110 Don't forget the special case: remove all the numbers and add a $1$.
    111 
    112 **Solution**
    113 
    114 ```
    115 #include<bits/stdc++.h>
    116 using namespace std;
    117 int p[100005];
    118 typedef long long ll;
    119 void solve()
    120 {
    121     int n,a,b;scanf("%d%d%d",&n,&a,&b);
    122     set<int> st;
    123     ll sol = 0 , ans = 2e18;
    124     for(int i = 1;i <= n;i++) {
    125         int x;scanf("%d",&x);
    126         if(st.find(x) == st.end()) st.insert(x);
    127         else sol += a;
    128     }
    129     int c = 0;
    130     for(auto x : st) p[++c] = x;
    131     for(int i = 1;i <= c;i++) {
    132         ans = min(ans , 1LL*(p[i] - i)*b + 1LL*(c-i)*a);
    133     }
    134     ans = min(ans , 1LL*c*a + b) ;
    135     printf("%lld\n",ans+sol);
    136 }
    137 int main()
    138 {
    139     int t;scanf("%d",&t);
    140     while(t--) solve();
    141 }
    142 ```
    143 
    144 [D.Climbing the Tree](https://codeforces.com/contest/1810/problem/D)
    145 
    146 **Hint**
    147 
    148 The possible $L$ is always an interval. How to maintain it?
    149 
    150 **Tutorial**
    151 
    152 The main idea is to that for each $a,b,n$, the possible $L$ is a interval $[l,r]$. We will show how to calculate that.
    153 
    154 In the first $n-1$ days, the snail will climb $(n-1)\cdot (a-b)$ meters. And in the daytime of the $n$-th day, the snail will climb $a$ meters. So after $n$ days, the snail climbs at most $(n-1)\cdot (a-b) + a$ meters, which means $L \le (n-1)\cdot (a-b) + a$. Also, the snail can not reach $L$ before $n$ days, which means $L \gt (n-2)\cdot (a-b) + a$. So $L \in [(n-2)\cdot (a-b) + a + 1 , (n-1)\cdot (a-b) + a]$. $n=1$ is a special case, where $L \in [1,a]$ .
    155 
    156 Now after each operation $1$, we can maintain a possible interval $[L_{min} , L_{max}]$. When a snail comes, we let the new $[L_{min}',L_{max}']$ be $[L_{min},L_{max}] \cap [l,r]$, where $[l,r]$ is the possible interval for the new snail. If the new interval is empty, we ignore this information, otherwise adopt it.
    157 
    158 Now let's focus on another problem: for a fixed $L,a,b$, how to calculate the number of days the snail needs to climb? We can solve the equation $(n-2)(a-b) + a \lt L \le (n-1)(a-b) + a$, and get $n - 2 \lt \frac{L - a}{a - b} \le n - 1$, which means $n$ equals to $\lceil \frac{L-a}{a-b} \rceil + 1$. Still, special judge for $L \le a$, where $n=1$ in this case.
    159 
    160 Then, for each query of type $2$, we just calculate the number of days we need for $L_{min}$ and $L_{max}$. If they are the same, output that number. Otherwise output $-1$.
    161 
    162 **Solution**
    163 
    164 ```
    165 #include<bits/stdc++.h>
    166 using namespace std;
    167 typedef long long ll;
    168 void solve()
    169 {
    170     int q;scanf("%d",&q);
    171     ll L = 1 , R = 1e18;
    172     while(q--) {
    173         int op;scanf("%d",&op) ;
    174         if(op == 1) {
    175             int a,b,n;scanf("%d%d%d",&a,&b,&n);
    176             ll ql = 1LL*(n - 2)*(a - b) + a + 1, qr = 1LL*(n - 1)*(a - b) + a;
    177             if(n == 1) ql = 1 , qr = a;
    178             if(ql > R || qr < L) {
    179                 puts("0");
    180             }
    181             else L = max(L , ql) , R = min(R , qr) , puts("1");
    182         }
    183         else {
    184             int a,b;scanf("%d%d",&a,&b);
    185             ll ans1 = max(1LL,(L - b - 1) / (a - b) + 1) , ans2 = max(1LL,(R - b - 1) / (a - b) + 1);
    186             if(ans1 == ans2) printf("%lld\n",ans1);
    187             else puts("-1");
    188         }
    189     }
    190     return;
    191 }
    192 int main()
    193 {
    194     int t;scanf("%d",&t);
    195     while(t--) solve();
    196 }
    197 ```
    198 
    199 [E.Monsters](https://codeforces.com/contest/1810/problem/E)
    200 
    201 **Hint 1**
    202 
    203 How to check whether it is possible to defeat all the monsters, starting from a fixed vertex $u$?
    204 
    205 **Hint 2**
    206 
    207 Let $S(u)$ be the vertices set that can be reached, starting from vertex $u$. What's the relationship between $S(u)$ and $S(v)$, where $v\in S(u)$?
    208 
    209 **Tutorial**
    210 
    211 For some vertex set $T$, let's define $E(T)$ as the ''neighbours'' of vertex set $T$. Formally, $v \in E(T)$ if and only if $v \notin T$, but there exist some vertex $u$, such that there's an edge $(u,v)$ in the graph, and $u \in T$.
    212 
    213 Now let's consider how to solve the problem for some fixed starting vertex $u$? Let's maintain the set $S(u)$ and $E(S(u))$. Initially, $S(u) = {u }$. We keep doing the procedure: choose a vertex $v \in E(S(u))$ with minimal value $a_{v}$. If $a_{v} \le |S(u)|$, we add $v$ into set $S(u)$, and update set $E(S(u))$ simultaneously. Since $S(u)$ is always connected during the procedure, we are actually doing such a thing: find a vertex $v$ that is ''reachable'' now with minimal value $a_{v}$, and try to defeat the monster on it. Our goal is to find some $u$ such that $|S(u)| = n$.
    214 
    215 Then let's move to a lemma: if $v \in S(u)$, then $S(v) \subseteq S(u)$.
    216 
    217 **Proof**
    218 
    219 If it is not, consider the procedure above and the first time we add some vertex $x$ such that $x \notin S(u)$ into $S(v)$. At this moment, $|S(v)| \le |S(u)|$ must hold(since it's the first time we add some vertex not in $S(u)$). On the other side, $x \in E(S(u))$ must hold, and hence $a_{x} \gt |S(u)| \ge |S(v)|$. Thus, we can not add $x$ into $S(v)$.
    220 
    221 Then we can tell, if $|S(u)| \lt n$, then for $v \in S(u)$, $|S(v)| \lt n$. So it's unnecessary to search starting from $v$. And we can construct such an algorithm: Search from $1,2,3,\dots n$ in order, if some $i$ has been included in some $S(j)$ before, do not search from it.
    222 
    223 Surprisingly, this algorithm is correct. We can prove it's time complexity. For each vertex $v$, if $v \in S(u)$ now, and when searching from vertex $u'$, $v$ is add into $S(u')$ again, then $|S(u')| \gt 2|S(u)|$. Thus, one vertex can not be visited more than $log(n)$ times, which means the time complexity is $O(nlog^2(n))$.
    224 
    225 This problem has many other methods to solve. This one I think is the easiest to implement.
    226 
    227 **Solution**
    228 
    229 ```
    230 #include<bits/stdc++.h>
    231 using namespace std;
    232 int vis[200005];
    233 int n , m;
    234 vector<int> E[200005];
    235 int a[200005];
    236 int T = 1;
    237 bool span(int u)
    238 {
    239     set<pair<int,int> > st;
    240     st.insert(pair<int,int>{a[u] , u});
    241     int amt = 0 , df = 0;
    242     while(st.size()) {
    243         auto pa = (*st.begin()) ; vis[pa.second] = u;
    244         if(pa.first > df) {return (amt == n);}
    245         st.erase(st.begin());
    246         amt++ ; df++ ;
    247         for(auto v : E[pa.second]) {
    248             if(vis[v] < u) {
    249                 st.insert(pair<int,int>{a[v] , v});
    250             }
    251         }
    252     }
    253     return (amt == n);
    254 }
    255 void solve()
    256 {
    257     scanf("%d%d",&n,&m);
    258     for(int i= 1;i <= n;i++) scanf("%d",&a[i]) , vis[i] = 0, E[i].clear();
    259     for(int i = 1;i <= m;i++) {
    260         int u,v;scanf("%d%d",&u,&v);E[u].push_back(v) ; E[v].push_back(u);
    261     }
    262     for(int i = 1;i <= n;i++) {
    263         if(a[i] == 0 && !vis[i]) {
    264             if(span(i)){puts("YES");return;}
    265         }
    266     }
    267     puts("NO");
    268 }
    269 int main()
    270 {
    271     int t;scanf("%d",&t);
    272     while(t--) solve();
    273 }
    274 ```
    275 
    276 [F.M-tree](https://codeforces.com/contest/1810/problem/F)
    277 
    278 **Hint 1**
    279 
    280 Can you solve a single query using binary search? How to check the answer?
    281 
    282 **Hint 2**
    283 
    284 Try to find a closed formula for this problem.
    285 
    286 **Tutorial**
    287 
    288 Let $num_{i}$ be the number of occurances of integer $i$ in the array $a$. To check whether the answer can be $\le x$ or not, we can do the following greedy: Starting with a single vertex written $x$, which is the root. For each $i$(from large ones to small ones), if the number of current leaves is smaller than $num_{i}$, then we can not make the answer $\le x$. Otherwise, let $num_{i}$ leaves stop, and other leaves ''grow'' $m$ children each(these vertices are no longer leaves, but their children are). We can discover that each round, the ''stopped'' vertices have $dep = x - i$, which represents their value is $x$.
    289 
    290 We can use the following code to calculate it.
    291 
    292 ```
    293 bool check(int x)
    294 {
    295     int d = 1;
    296     for(int i = x;i >= 1;i--){
    297         if(d < num[i]) return 0;
    298         d = (d - num[i]) * m;
    299     }
    300     return 1;
    301 }
    302 ```
    303 
    304 Since a negtive number multiplies $m$ is still a negtive number, the code can be as following:
    305 
    306 ```
    307 bool check(int x)
    308 {
    309     int d = 1;
    310     for(int i = x;i >= 1;i--){
    311         d = (d - num[i]) * m;
    312     }
    313     return d >= 0;
    314 }
    315 ```
    316 
    317 Find out something? The final $d$ is just $m^x - \sum_{i=1}^{x}{num_{i} \cdot m^i}$, which represents it's equivalent to checking $m^x \ge \sum_{i=1}^{n}{m^{a_{i}}}$! So now the answer is just $\lceil log_{m}{\sum_{i=1}^{n}{m^{a_{i}}}} \rceil$. This is the highest bit plus one of $\sum{m^{a_{i}}}$ in $m$-base representation(except for that it's just some $m^x$. In this case the answer is $x$ but not $x+1$). We can use a segment tree, supporting interval min/max query and interval covering to solve the question.
    318 
    319 **Solution**
    320 
    321 ```
    322 using namespace std;
    323 int n , m , q;
    324 const int N = 2e5 + 40;
    325 int num[N];
    326 int a[N];
    327 int cov[N*4 + 5] , mx[N*4 + 5] , mn[N*4 + 5];
    328 void rec(int u)
    329 {
    330     mx[u] = max(mx[u<<1|1] , mx[u<<1]) ; mn[u] = min(mn[u<<1|1] , mn[u<<1]);
    331 }
    332 void pd(int u)
    333 {
    334     if(cov[u] != -1) {
    335         cov[u<<1] = mn[u<<1] = mx[u<<1] = cov[u];
    336         cov[u<<1|1] = mn[u<<1|1] = mx[u<<1|1] = cov[u];
    337         cov[u] = -1;
    338     }
    339     return;
    340 }
    341 void build(int u,int l,int r)
    342 {
    343     cov[u] = -1;
    344     if(l == r) {mn[u] = mx[u] = num[l] ; return;}
    345     build(u<<1 , l , (l + r >> 1)) ; build(u<<1|1 , (l + r >> 1) + 1 , r);
    346     rec(u) ; return;
    347 }
    348 void modify(int u,int l,int r,int ql,int qr,int v)
    349 {
    350     if(ql <= l && qr >= r) {
    351         cov[u] = mn[u] = mx[u] = v; return;
    352     }
    353     pd(u);
    354     int md = (l + r>> 1);
    355     if(ql <= md) modify(u<<1 , l , md , ql , qr ,v);
    356     if(qr > md) modify(u<<1|1 , md +1 , r , ql , qr , v);
    357     rec(u);
    358     return;
    359 }
    360  
    361 int qumax(int u,int l,int r,int ql)
    362 {
    363     if(mn[u] == m - 1) return -1;
    364     if(l == r) return l;
    365     pd(u);
    366     int md = (l + r>> 1);
    367     if(ql > md) return qumax(u<<1|1 , md + 1 , r , ql);
    368     if(ql == l) {
    369         if(mn[u<<1] < m - 1) return qumax(u<<1 , l , md , ql);
    370         return qumax(u<<1|1 , md + 1 , r , md + 1);
    371     }
    372     int w = qumax(u<<1 , l , md , ql) ;
    373     if(w == -1) return qumax(u<<1|1 , md + 1 , r , md + 1);
    374     return w;
    375 }
    376 int qumin(int u,int l,int r,int ql)
    377 {
    378     if(mx[u] == 0) return -1;
    379     if(l == r) return l;
    380     pd(u);
    381     int md = (l + r>> 1) ;
    382     if(ql > md) return qumin(u<<1|1 , md + 1 , r , ql);
    383     if(ql == l) {
    384         if(mx[u<<1] > 0) return qumin(u<<1 , l , md , ql);
    385         return qumin(u<<1|1 , md + 1 , r , md + 1);
    386     }
    387     int w = qumin(u<<1 , l , md , ql);
    388     if(w == -1) return qumin(u<<1|1 , md + 1 , r , md + 1);
    389     return w;
    390 }
    391  
    392 int qmax(int u,int l,int r,int ql,int qr)
    393 {
    394     if(ql <= l && qr >= r) {
    395         return mx[u];
    396     }
    397     pd(u);
    398     int md = (l + r>> 1) , ans = 0;
    399     if(ql <= md) ans = max(ans , qmax(u<<1 , l , md , ql , qr ));
    400     if(qr > md) ans = max(ans , qmax(u<<1|1 , md +1 , r , ql , qr));
    401     return ans;
    402 }
    403 int qmin(int u,int l,int r,int ql,int qr)
    404 {
    405     if(ql <= l && qr >= r) {
    406         return mn[u];
    407     }
    408     pd(u);
    409     int md = (l + r>> 1) , ans = 1e9;
    410     if(ql <= md) ans = min(ans , qmin(u<<1 , l , md , ql , qr ));
    411     if(qr > md) ans = min(ans , qmin(u<<1|1 , md +1 , r , ql , qr));
    412     return ans;
    413 }
    414 int ask(int u,int l,int r)
    415 {
    416     if(l == r) return l;
    417     int md = (l + r >> 1);
    418     pd(u);
    419     if(mx[u<<1|1] == 0) return ask(u<<1 , l , md);
    420     return ask(u<<1|1 , md + 1 , r) ;
    421 }
    422 int get()
    423 {
    424     int highbit = ask(1 , 1 , n+35);
    425     if(highbit == 1 || qmax(1 , 1 , n+35 , 1 , highbit - 1) == 0) return highbit;
    426     return highbit + 1;
    427 }
    428 void add(int u)
    429 {
    430     int l = qumax(1 , 1 , n + 35 , u);
    431     if(l > u) modify(1 , 1 , n+35 , u , l - 1 , 0) ;
    432     modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) + 1);
    433     return;
    434 }
    435 void sub(int u)
    436 {
    437     int l = qumin(1 , 1 , n + 35 , u);
    438     if(l > u) modify(1 , 1 , n+35 , u , l - 1 , m - 1) ;
    439     modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) - 1);
    440     return;
    441 }
    442 void solve()
    443 {
    444     scanf("%d%d%d",&n,&m,&q);
    445     for(int i = 1;i <= n + 35;i++) num[i] = 0;
    446     for(int i = 1;i <= n;i++) {
    447         scanf("%d",&a[i]);num[a[i]]++;
    448     }
    449     for(int i = 1;i <= n + 35;i++) {
    450         num[i + 1] += num[i] / m;num[i] %= m;
    451     }
    452     build(1 , 1 , n + 35);
    453     while(q--) {
    454         int u , v;scanf("%d%d",&u,&v);
    455         sub(a[u]) ; a[u] = v; add(a[u]) ;
    456         printf("%d%c",get(), " \n"[q == 0]);
    457     }
    458     return;
    459 }
    460 int main()
    461 {
    462     int t;scanf("%d",&t);
    463     while(t--) solve();
    464 }
    465 ```
    466 
    467 [G. The Maximum Prefix](https://codeforces.com/contest/1810/problem/G)
    468 
    469 **Hint**
    470 
    471 How to calculate the maximal prefix sum? One possible way is let $f_{n+1} = 0$ and $f_{i}=max(f_{i+1},0)+a_{i}$.
    472 
    473 **Tutorial**
    474 
    475 Consider this method to find maximal prefix sum: let $f_{n+1} = 0$ and $f_{i}=max(f_{i+1},0)+a_{i}$. We can discover that the only influence $[a_{i+1},a_{i+2} \dots a_{n}]$ has(to the whole array's maximal prefix sum) is its maximal prefix sum. Then we let $dp_{i,j}$ be : the expect score we can get, if we assume that the maximal prefix sum of $[a_{i+1},a_{i+2} \dots a_{n}]$ is $j$ (Read the definition carefully). The answer for each $k$ is $dp_{k,0}$, since if the maximal prefix sum for $[a_{k+1},a_{k+2} \dots a_{n}]$ is $0$, that is equivalent to removing them from the array. And also $dp_{0,j} = h_{j}$.
    476 
    477 And we have $dp_{i,j} = p_{i}\cdot dp_{i-1,j+1} + (1 - p_{i})\cdot dp_{i-1,max(j-1,0)}$. The first section represents chosing $a_{i} = 1$ and the second one represents chosing $a_{i} = -1$.
    478 
    479 We also have other solutions, using inclusion-exclusion or generate function. Actually all the testers' solutions differs from each other.
    480 
    481 **Solution**
    482 
    483 ```
    484 #include<bits/stdc++.h>
    485 using namespace std;
    486 const int mod = 1e9 + 7;
    487 const int N = 5005;
    488 int p[N] , q[N];
    489 int n;
    490 int f[N][N];
    491 int h[N];
    492 int fpow(int a,int b)
    493 {
    494     int ans = 1;
    495     while(b){
    496         if(b & 1) ans = 1LL*ans*a%mod;
    497         a = 1LL*a*a%mod;b >>= 1;
    498     }
    499     return ans;
    500 }
    501 void solve()
    502 {
    503     scanf("%d",&n);
    504     for(int i = 1;i <= n;i++) {
    505         int a,b;scanf("%d%d",&a,&b);
    506         p[i] = 1LL*a*fpow(b , mod - 2) % mod;
    507         q[i] = (1 - p[i] + mod) % mod;
    508     }
    509     for(int i = 0;i <= n;i++) scanf("%d",&h[i]);
    510     for(int i = 0;i <= n;i++) f[0][i] = h[i];
    511     for(int i = 1;i <= n;i++) {
    512         for(int j = 0;j <= n;j++) {
    513             f[i][j] = (1LL*p[i]*f[i - 1][j + 1] + 1LL*q[i]*f[i - 1][max(0 , j - 1)] ) % mod;
    514         }
    515         printf("%d ",f[i][0]);
    516     }
    517     printf("\n");
    518     return;
    519 }
    520 int main()
    521 {
    522     int t;scanf("%d",&t);
    523     while(t--) solve();
    524     return 0;
    525 }
    526 ```
    527 
    528 [H.Last Number](https://codeforces.com/contest/1810/problem/H)
    529 
    530 **Hint**
    531 
    532 Actually I don't know how to hint. Try to find some rules related to $\frac{\sqrt{5}+1}{2}$, fibnacci or similar
    533 
    534 **Tutorial**
    535 
    536 Assume that the moment before the $x$-th operation(but after $x-1$-th), the first time we have $S_{max} \le 2S_{min}$. Let's divide the operation into two part: before $x$ and equal or after $x$.
    537 
    538 Still, at the moment just before the $x$-th operation, let us sort the elements in the multiset in non-decreasing order, $S_{0},S_{1} \dots S_{k}$. We will show that the answer is $S_{0}\cdot (-1)^{k} + \sum_{i=1}^{k}{S_{i}\cdot (-1)^{i+1}}$.
    539 
    540 **Proof**
    541 
    542 This lemma is based on the fact that, after each operation(which is after $x$-th), $S_{1}$ to $S_{k-1}$ will not change, $S_{k}$ is removed, and $S_{0}$ turn to $S_{k}-S_{0}$. Which also means $S_{k} - S_{0} \le S_{1}$ always holds.
    543 
    544 At the very beginning, $S_{k} - S_{0} \le S_{0} \le S_{1}$ obviously holds. And we can observe that either $S_{k} = S_{k-1}$ or $S_{k-1} = S_{k} - 1$. When $S_{k-1} = S_{k}$, the new $S_{0}$ after two operations is equal to the old $S_{0}$. When $S_{k-1} = S_{k} - 1$, the new $S_{0}$ after two operations is equal to the old $S_{0}$ minus one. So if we write the $S_{0}$ as an array $t_{0} , t_{1} \ldots t_{k}$ by time order, $t_{i+2} \le t_{i}$ always holds. Thus, $t_{i} \le S_{1}$ always holds.
    545 
    546 Let $d_{i}$ be the $S_{max}$ value in the $i$-th operation. Let's prove that before the $x$-th operation, $d_{i} = n-\lceil \frac{i}{\phi} \rceil + 1$, where $\phi = \frac{\sqrt{5} + 1}{2}$.
    547 
    548 **Proof**
    549 
    550 We prove this by Mathematical induction. One fact should be known that during these operations, $S_{min} = i$ always holds for the $i$-th operation(since $S_{max} - S_{min} \gt S_{min}$).
    551 
    552 For $i=1$, it is true because $d_{1} = n$ and $n - \lceil \frac{1}{\phi} \rceil + 1 = n$.
    553 
    554 Assume for $i\le k$, it is true. Still use the fact that $d_{k+1} = d_{k}$ or $d_{k+1} = d_{k} + 1$. The necessary and sufficient condition for $d_{k+1} \gt d_{k}$ is all the numbers greater or equal to $d_{k}$ is ''used''. How many numbers are there? We have $n - d_{k} + 1$ numbers from the original multiset, and some numbers that occurs during the operations, which are the number of $j$ satisfying $d_{j} - j \ge d_{k}$. Thus, $d_{k+1} \gt d_{k}$ is equivalent to:
    555 
    556 $ \space \space \space \space \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} + n - d_{k} + 1 = k$
    557 
    558 $ \Leftrightarrow \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} = k - \lceil \frac{k}{\phi} \rceil$
    559 
    560 $\Leftrightarrow \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$
    561 
    562 $\Leftrightarrow \sum_{j=1}^{k}{[\lceil \frac{j}{\phi} + j \rceil \le \lceil \frac{k}{\phi} \rceil]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$
    563 
    564 $\Leftrightarrow \sum_{j=1}^{k}{[\lceil \frac{j(\phi + 1)}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$
    565 
    566 Note that $\frac{j(\phi + 1)}{\phi}$ is always increasing, which means that formula $\lceil \frac{j(\phi + 1)}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil$ holds for $j = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$, but does not hold for $j = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor + 1$.
    567 
    568 The first equation, $\lceil \lfloor \frac{k(\phi - 1)}{\phi} \rfloor \cdot \frac{\phi + 1}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil$ always holds. Because $\frac{\phi - 1}{\phi}\cdot \frac{\phi + 1}{\phi} = \frac{1}{\phi}$, and ofcourse $\lfloor ka \rfloor b \le kab$.
    569 
    570 Let's do the research when the second equation does not hold. Let $m_{1} = \lbrace \frac{i(\phi - 1)}{\phi} \rbrace$, and $m_{2} = \lbrace \frac{i}{\phi} \rbrace $ ($\lbrace x \rbrace = x - \lfloor x \rfloor$). Note that $m_{1} + m_{2} = 1$, since $\lbrace \frac{i(\phi - 1)}{\phi} \rbrace = \lbrace i - \frac{i}{\phi} \rbrace$. The topic we are going to research is when $\lceil (\lfloor \frac{k(\phi - 1)}{\phi} \rfloor + 1) \cdot \frac{\phi + 1}{\phi}\rceil \gt \lceil \frac{k}{\phi} \rceil$ hold(which also means, $d_{k+1} \gt d_{k}$).
    571 
    572 $\Leftrightarrow \lceil (\frac{i(\phi - 1)}{\phi} - m_{1}) \cdot \frac{\phi+1}{\phi} + \frac{\phi + 1}{\phi} \rceil \gt \lceil \frac{i}{\phi} \rceil$
    573 
    574 $\Leftrightarrow \lceil \frac{i}{\phi} - m_{1} \cdot \frac{\phi+1}{\phi} + \frac{\phi + 1}{\phi} \rceil \gt \lceil \frac{i}{\phi} \rceil$
    575 
    576 $\Leftrightarrow \lceil \frac{i}{\phi} - (1 - m_{1}) \cdot \frac{\phi+1}{\phi} \rceil \gt \lceil \frac{i}{\phi} \rceil$
    577 
    578 $\Leftrightarrow (1 - m_{1}) \cdot \frac{\phi+1}{\phi} \gt 1 - m_{2}$
    579 
    580 $\Leftrightarrow \frac{\phi+1}{\phi} \gt \frac{1}{m_{2}} - 1$
    581 
    582 $\Leftrightarrow m_{2} \gt \frac{\phi}{2\phi + 1}$
    583 
    584 Then let's focus on, if $d_{k+1} = n - \lceil \frac{k+1}{\phi} \rceil + 1$, when will $d_{k + 1} \gt d_{k}$ hold? It's easy to find when $m_{2} \gt 1 - \frac{1}{\phi}$, $d_{k+1} \gt d_{k}$ holds. And since $\phi = \frac{\sqrt{5} + 1}{2}$, we can tell $ \frac{\phi}{2\phi + 1} = 1 - \frac{1}{\phi}$. Thus, we proved the topic, for all $k \lt x$(before the $x$-th operation), $d_{k} = n - \lceil \frac{k}{\phi} \rceil + 1$.
    585 
    586 Then, by solve $n - \lceil \frac{x}{\phi} \rceil + 1 \le 2x$, we can get $x = \lceil (n+1)\frac{\phi - 1}{\phi} \rceil$. Now let's prove for $k \ge x$, $d_{k} = n - \lceil \frac{k}{\phi} \rceil + 1$ also holds !
    587 
    588 **Proof**
    589 
    590 Using the similar idea as lemma 2, find out when $d_{k + 1} \gt d_{k}$ holds. However, at this time, only $j \le x - 1$ will contribute(since for those $j \gt x - 1$, according to lemma 1, they become the minimal one and do not contribute to anything). Similarly, that is $\sum_{j=1}^{x - 1}{[d_{j} - j \ge d_{k}]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$.
    591 
    592 Seems to be different this time, but actually they are the same, because $\lfloor \frac{k(\phi - 1)}{\phi} \rfloor \le x - 1$ holds(the proving is easy, leave it as a exercise). This condition holds means that we can use the same method in lemma 2 to prove it.
    593 
    594 Till now, the lemmas told us the solving the problem is actually solving something like $\sum{(-1)^{i} \cdot (n- \lceil \frac{i}{\phi} \rceil + 1)}$. We can divide them into positive part and negtive part, and then solving $\sum{\lfloor C\cdot i \rfloor}$, where $i$ range from some $l$ to $r$, and $C$ is a irrational constant. Since $n$ is not very large, we can approximate $C$ by $\frac{a}{b}$, where $a,b$ are integers, and turn it into a traditional task. (Maybe it is called floor sum or something like, I'm not sure about the algorithm's english name).
    595 
    596 The marvelous jiangly told me $a,b$ in long long range is enough. But the tester used int128.
    597 
    598 We can dig more about the $\phi$. Let $b_{i} = S_{i+1} - S_{i}$ (sorted, before the $x$-th operation), and what we care is $b_{1} + b_{3} + b_{5}\dots$. We can find that array $b$ is actually a consecutive substring of [fibonacci string](https://oeis.org/A096270). More over, let $F_{n}$ be the starting point of array $b$ in the fibonacci string when the initial size is $n$, we have the conclusion for $n \ge 5$:
    599 
    600 $F[5 \dots inf] = [3,0],[4,1],[8,0],[12,1] \dots [f_{i+3} + (-1)^{i+1} , 1 + (-1)^{i}]$, where $f_{i} = f_{i-1} + f_{i-2} , f_{1} = f_{2} = 1$ . $[r,l]$ represents a list of numbers $[r,r-1,r-2 \dots l+1,l]$.
    601 
    602 Now the only left problem is to find the prefix sum of fibonacci string(of even positions, or of odd positions). This is quite a simple task by using any $log(n)$ or $log^2(n)$ solution.
    603 
    604 **Solution 1(floor sum)**
    605 
    606 ```
    607 #include <bits/stdc++.h>
    608  
    609 void solve(__int128 n, __int128 a, __int128 b, __int128 c, __int128 &f) {
    610     if (n < 0) { f = 0; return; }
    611     if (a >= c || b >= c) {
    612         solve(n, a % c, b % c, c, f);
    613         f += (a / c) * (n * (n + 1) / 2) + (b / c) * (n + 1);
    614     } else if (a) {
    615         __int128 m = (a * n + b) / c;
    616         solve(m - 1, c, c - b - 1, a, f);
    617         f = n * m - f;
    618     }
    619 }
    620  
    621 const long double k = (1 + sqrt((long double) 5)) / 2;
    622  
    623 int n;
    624 long long ans;
    625 __int128 a, b, c, d;
    626  
    627 int main() {
    628     int T;
    629     scanf("%d", &T);
    630     __int128 x = (__int128) 2000000000000000000ll * 1000000000;
    631     __int128 y = (__int128) 1000000000000000000ll * 1000000000;
    632     __int128 z = (__int128) 1618033988749894848ll * 1000000000 + 204586834;
    633     for (; T; T--) {
    634         scanf("%d", &n);
    635         int i = 0;
    636         for (int l = 0, r = n - 1, mid; l <= r; ) {
    637             mid = l + r >> 1;
    638             if (n - floor(mid / k) <= mid + mid) {
    639                 i = mid; r = mid - 1;
    640             } else {
    641                 l = mid + 1;
    642             }
    643         }
    644         solve((n - 1) / 2, x, 0, z, a);
    645         solve((i - 1) / 2, x, 0, z, b);
    646         solve((n - 2) / 2, x, y, z, c);
    647         solve((i - 2) / 2, x, y, z, d);
    648         ans = i + (i % 2 ? -1 : 1) * ((a - b) - (c - d));
    649         if ((n - i) % 2) { ans = n - ans; }
    650         printf("%lld\n", ans);
    651     }
    652     return 0;
    653 }
    654 ```
    655 
    656 **Solution 2(fibonacci)**
    657 
    658 ```
    659 #include<bits/stdc++.h>
    660 using namespace std;
    661 int l[500];
    662 int fib[500];
    663 int evenfib[500];
    664 int getsum(int i,int n) ///1-index
    665 {
    666     if(n == 0) return 0;
    667     if(i <= 1) return fib[i];
    668     if(n <= l[i - 2]) return getsum(i - 2,  n);
    669     return fib[i - 2] + getsum(i - 1 , n - l[i - 2]);
    670 }
    671 int getsum2(int i,int n,int p) ///n = 2*k+p, 0-index
    672 {
    673     if(i <= 0) return 0;
    674     if(i <= 1) return 1^p;
    675  
    676     if(n <= l[i - 2] - 1) return getsum2(i - 2 , n , p);
    677     int L;
    678     if(p) L = (l[i - 2] - !(l[i-2]&1));
    679     else L = (l[i- 2] - (l[i - 2] & 1));
    680     int ans ;
    681     if(p) ans = fib[i - 2] - evenfib[i - 2];
    682     else ans = evenfib[i - 2];
    683     ans += getsum2(i - 1 , n - l[i - 2] , p ^ ((l[i - 2] & 1)));
    684     return ans;
    685 }
    686 int getfib(int n) ///0-index
    687 {
    688     if(n <= 0) return 0;
    689     n++;
    690     int ans = 0;
    691     int i;
    692     for(i = 0;l[i] <= n;i++) {
    693         ans += fib[i] ; n -= l[i];
    694     }
    695     return ans + getsum(i , n);
    696 }
    697 int get_even(int n) ///n = 2*k
    698 {
    699     n++;
    700     int ans = 0;
    701     int i , lbefore = 0;
    702     for(i = 0;l[i] <= n;i++) {
    703         if(lbefore) ans += fib[i] - evenfib[i];
    704         else ans += evenfib[i];
    705         lbefore ^= (l[i]&1);
    706         n -= l[i];
    707     }
    708     if(n) ans += getsum2(i , n - 1, lbefore);
    709     return ans;
    710 }
    711 const double phi = (3 - sqrt(5)) / 2;
    712 const double eps = 1e-6;
    713 int getstart(int n)
    714 {
    715     if(n == 3) return 0;
    716     if(n == 4) return 1;
    717     n -= 4;
    718     int i;
    719     for(i = 1;1;i++) {
    720         int lft ;
    721         if(i & 1) lft = fib[i + 3] + 1;
    722         else lft = fib[i + 3] - 1;
    723         if(n <= lft) break;
    724         n -= lft;
    725     }
    726     int start ;
    727     if(i & 1) start = fib[i + 3] - n + 1;
    728     else start = fib[i + 3] - n;
    729     return start;
    730 }
    731 typedef long long ll;
    732 const int L = 95;
    733 int a[120] = {8,0,6,0,1,8,5,9,7,2,9,7,2,9,2,0,5,5,7,9,0,1,8,1,7,3,5,9,3,7,4,9,2,7,7,3,1,5,5,4,6,8,7,3,1,7,3,2,4,9,1,0,2,8,0,9,6,9,7,2,2,8,8,1,6,3,4,3,6,5,6,1,3,1,4,5,9,7,1,5,1,5,0,1,0,5,2,1,1,0,6,6,9,1,8,3};
    734 ll b[120];
    735 double cal(int n)
    736 {
    737     memset(b,0,sizeof(b));
    738     for(int i = 0;i <= L;i++) b[i] = 1LL*n*a[i];
    739     for(int i = 0;i <= L + 15;i++) {
    740         b[i + 1] += (b[i] / 10) ; b[i] %= 10;
    741     }
    742     int ans = 0;
    743     for(int i = L + 11;i >= L + 1;i--) ans = (ans * 10 + b[i]) ;
    744     return ans;
    745 }
    746 void solve(int n)
    747 {
    748     if(n <= 2) {puts("1");return;}
    749     int v = cal(n);
    750     int len = n - v;v++;
    751     int start = getstart(n);
    752     int ans = 0;
    753     if(len & 1) {
    754         ans = v; ///[start + 1 , start + 3...start + len - 2]
    755         if(start & 1) ans -= (get_even(start + len - 2) - get_even(start - 1));
    756         else ans -= (getfib(start + len - 1) - get_even(start + len - 1) - getfib(start) + get_even(start));
    757     }
    758     else {
    759         ans = getfib(start + len - 2) - getfib(start - 1);
    760         ///[start + 1 , start + len - 3]
    761         if(start & 1) ans -= (get_even(start + len - 3) - get_even(start - 1));
    762         else ans -= (getfib(start + len - 2) - get_even(start + len - 2) - getfib(start) + get_even(start));
    763     }
    764     printf("%d\n",ans);return;
    765 }
    766 int main()
    767 {
    768     l[0] = l[1] = 1;
    769     fib[0] = 0 , fib[1] = 1;
    770     evenfib[1] = 1;
    771     for(int i = 2;l[i-1] <= 1000000000;i++) {
    772         l[i] = l[i - 1] + l[i - 2];
    773         fib[i] = fib[i - 1] + fib[i - 2];
    774         if(l[i - 2] & 1) evenfib[i] = evenfib[i - 2] + fib[i - 1] - evenfib[i - 1];
    775         else evenfib[i] = evenfib[i - 2] + evenfib[i - 1];
    776     }
    777  
    778     int t;scanf("%d",&t);
    779     while(t--) {
    780         int n;scanf("%d",&n);solve(n);
    781     }
    782     return 0;
    783 }
    784 ```