What is the necessary and sufficient condition?

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.

#include<bits/stdc++.h>
using namespace std;
int a[100005];
void solve()
{
    int n;
    scanf("%d",&n);
    for(int i  =1;i <= n;i++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i++) {
        if(a[i] <= i) {
            puts("YES");
            return;
        }
    }
    puts("NO");
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

How the binary representation changes after an operation?

First, we notice that after each operation, the number of candies is always a odd number. So even numbers can not be achieved.

Then consider how the binary representation changes for a odd number $$$x$$$, after turn it into $$$2x+1$$$ or $$$2x-1$$$.

• For the $$$2x + 1$$$ operation: $$$\overline{\dots 1}$$$ turns into $$$\overline{\dots 11}$$$.

• For the $$$2x - 1$$$ operation: $$$\overline{\dots 1}$$$ turns into $$$\overline{\dots 01}$$$.

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.

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;scanf("%d",&n);
    if(n % 2 == 0) {
        puts("-1");return;
    }
    vector<int> v;
    int f = 0;
    for(int i = 29;i >= 1;i--) {
        if((n >> i) & 1) {
            f = 1;
            v.push_back(2);
        }
        else if(f) {
            v.push_back(1);
        }
    }
    printf("%d\n",v.size());
    for(auto x : v) {
        printf("%d ",x);
    }
    printf("\n");
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
    return 0;
}

Try the enumerate the length $$$n$$$ of permutation.

There're too many lengths to be checked. How to decrease the amount of $$$n$$$?

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} < a_{2} < \dots < a_{m}$$$).

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 < 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.

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.

Don't forget the special case: remove all the numbers and add a $$$1$$$.

#include<bits/stdc++.h>
using namespace std;
int p[100005];
typedef long long ll;
void solve()
{
    int n,a,b;scanf("%d%d%d",&n,&a,&b);
    set<int> st;
    ll sol = 0 , ans = 2e18;
    for(int i = 1;i <= n;i++) {
        int x;scanf("%d",&x);
        if(st.find(x) == st.end()) st.insert(x);
        else sol += a;
    }
    int c = 0;
    for(auto x : st) p[++c] = x;
    for(int i = 1;i <= c;i++) {
        ans = min(ans , 1LL*(p[i] - i)*b + 1LL*(c-i)*a);
    }
    ans = min(ans , 1LL*c*a + b) ;
    printf("%lld\n",ans+sol);
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

The possible $$$L$$$ is always an interval. How to maintain it?

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.

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 > (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]$$$ .

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.

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 < L \le (n-1)(a-b) + a$$$, and get $$$n - 2 < \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.

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$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    int q;scanf("%d",&q);
    ll L = 1 , R = 1e18;
    while(q--) {
        int op;scanf("%d",&op) ;
        if(op == 1) {
            int a,b,n;scanf("%d%d%d",&a,&b,&n);
            ll ql = 1LL*(n - 2)*(a - b) + a + 1, qr = 1LL*(n - 1)*(a - b) + a;
            if(n == 1) ql = 1 , qr = a;
            if(ql > R || qr < L) {
                puts("0");
            }
            else L = max(L , ql) , R = min(R , qr) , puts("1");
        }
        else {
            int a,b;scanf("%d%d",&a,&b);
            ll ans1 = max(1LL,(L - b - 1) / (a - b) + 1) , ans2 = max(1LL,(R - b - 1) / (a - b) + 1);
            if(ans1 == ans2) printf("%lld\n",ans1);
            else puts("-1");
        }
    }
    return;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

How to check whether it is possible to defeat all the monsters, starting from a fixed vertex $$$u$$$?

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)$$$?

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$$$.

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$$$.

Then let's move to a lemma: if $$$v \in S(u)$$$, then $$$S(v) \subseteq S(u)$$$.

Then we can tell, if $$$|S(u)| < n$$$, then for $$$v \in S(u)$$$, $$$|S(v)| < 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.

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')| > 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))$$$.

This problem has many other methods to solve. This one I think is the easiest to implement.

#include<bits/stdc++.h>
using namespace std;
int vis[200005];
int n , m;
vector<int> E[200005];
int a[200005];
int T = 1;
bool span(int u)
{
    set<pair<int,int> > st;
    st.insert(pair<int,int>{a[u] , u});
    int amt = 0 , df = 0;
    while(st.size()) {
        auto pa = (*st.begin()) ; vis[pa.second] = u;
        if(pa.first > df) {return (amt == n);}
        st.erase(st.begin());
        amt++ ; df++ ;
        for(auto v : E[pa.second]) {
            if(vis[v] < u) {
                st.insert(pair<int,int>{a[v] , v});
            }
        }
    }
    return (amt == n);
}
void solve()
{
    scanf("%d%d",&n,&m);
    for(int i= 1;i <= n;i++) scanf("%d",&a[i]) , vis[i] = 0, E[i].clear();
    for(int i = 1;i <= m;i++) {
        int u,v;scanf("%d%d",&u,&v);E[u].push_back(v) ; E[v].push_back(u);
    }
    for(int i = 1;i <= n;i++) {
        if(a[i] == 0 && !vis[i]) {
            if(span(i)){puts("YES");return;}
        }
    }
    puts("NO");
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

Can you solve a single query using binary search? How to check the answer?

Try to find a closed formula for this problem.

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$$$.

We can use the following code to calculate it.

bool check(int x)
{
    int d = 1;
    for(int i = x;i >= 1;i--){
        if(d < num[i]) return 0;
        d = (d - num[i]) * m;
    }
    return 1;
}

Since a negtive number multiplies $$$m$$$ is still a negtive number, the code can be as following:

bool check(int x)
{
    int d = 1;
    for(int i = x;i >= 1;i--){
        d = (d - num[i]) * m;
    }
    return d >= 0;
}

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.

#include<bits/stdc++.h>
using namespace std;
int n , m , q;
const int N = 2e5 + 40;
int num[N];
int a[N];
int cov[N*4 + 5] , mx[N*4 + 5] , mn[N*4 + 5];
void rec(int u)
{
    mx[u] = max(mx[u<<1|1] , mx[u<<1]) ; mn[u] = min(mn[u<<1|1] , mn[u<<1]);
}
void pd(int u)
{
    if(cov[u] != -1) {
        cov[u<<1] = mn[u<<1] = mx[u<<1] = cov[u];
        cov[u<<1|1] = mn[u<<1|1] = mx[u<<1|1] = cov[u];
        cov[u] = -1;
    }
    return;
}
void build(int u,int l,int r)
{
    cov[u] = -1;
    if(l == r) {mn[u] = mx[u] = num[l] ; return;}
    build(u<<1 , l , (l + r >> 1)) ; build(u<<1|1 , (l + r >> 1) + 1 , r);
    rec(u) ; return;
}
void modify(int u,int l,int r,int ql,int qr,int v)
{
    if(ql <= l && qr >= r) {
        cov[u] = mn[u] = mx[u] = v; return;
    }
    pd(u);
    int md = (l + r>> 1);
    if(ql <= md) modify(u<<1 , l , md , ql , qr ,v);
    if(qr > md) modify(u<<1|1 , md +1 , r , ql , qr , v);
    rec(u);
    return;
}
 
int qumax(int u,int l,int r,int ql)
{
    if(mn[u] == m &mdash; 1) return -1;
    if(l == r) return l;
    pd(u);
    int md = (l + r>> 1);
    if(ql > md) return qumax(u<<1|1 , md + 1 , r , ql);
    if(ql == l) {
        if(mn[u<<1] < m &mdash; 1) return qumax(u<<1 , l , md , ql);
        return qumax(u<<1|1 , md + 1 , r , md + 1);
    }
    int w = qumax(u<<1 , l , md , ql) ;
    if(w == -1) return qumax(u<<1|1 , md + 1 , r , md + 1);
    return w;
}
int qumin(int u,int l,int r,int ql)
{
    if(mx[u] == 0) return -1;
    if(l == r) return l;
    pd(u);
    int md = (l + r>> 1) ;
    if(ql > md) return qumin(u<<1|1 , md + 1 , r , ql);
    if(ql == l) {
        if(mx[u<<1] > 0) return qumin(u<<1 , l , md , ql);
        return qumin(u<<1|1 , md + 1 , r , md + 1);
    }
    int w = qumin(u<<1 , l , md , ql);
    if(w == -1) return qumin(u<<1|1 , md + 1 , r , md + 1);
    return w;
}
 
int qmax(int u,int l,int r,int ql,int qr)
{
    if(ql <= l && qr >= r) {
        return mx[u];
    }
    pd(u);
    int md = (l + r>> 1) , ans = 0;
    if(ql <= md) ans = max(ans , qmax(u<<1 , l , md , ql , qr ));
    if(qr > md) ans = max(ans , qmax(u<<1|1 , md +1 , r , ql , qr));
    return ans;
}
int qmin(int u,int l,int r,int ql,int qr)
{
    if(ql <= l && qr >= r) {
        return mn[u];
    }
    pd(u);
    int md = (l + r>> 1) , ans = 1e9;
    if(ql <= md) ans = min(ans , qmin(u<<1 , l , md , ql , qr ));
    if(qr > md) ans = min(ans , qmin(u<<1|1 , md +1 , r , ql , qr));
    return ans;
}
int ask(int u,int l,int r)
{
    if(l == r) return l;
    int md = (l + r >> 1);
    pd(u);
    if(mx[u<<1|1] == 0) return ask(u<<1 , l , md);
    return ask(u<<1|1 , md + 1 , r) ;
}
int get()
{
    int highbit = ask(1 , 1 , n+35);
    if(highbit == 1 || qmax(1 , 1 , n+35 , 1 , highbit &mdash; 1) == 0) return highbit;
    return highbit + 1;
}
void add(int u)
{
    int l = qumax(1 , 1 , n + 35 , u);
    if(l > u) modify(1 , 1 , n+35 , u , l &mdash; 1 , 0) ;
    modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) + 1);
    return;
}
void sub(int u)
{
    int l = qumin(1 , 1 , n + 35 , u);
    if(l > u) modify(1 , 1 , n+35 , u , l &mdash; 1 , m &mdash; 1) ;
    modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) &mdash; 1);
    return;
}
void solve()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i <= n + 35;i++) num[i] = 0;
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);num[a[i]]++;
    }
    for(int i = 1;i <= n + 35;i++) {
        num[i + 1] += num[i] / m;num[i] %= m;
    }
    build(1 , 1 , n + 35);
    while(q--) {
        int u , v;scanf("%d%d",&u,&v);
        sub(a[u]) ; a[u] = v; add(a[u]) ;
        printf("%d%c",get(), " \n"[q == 0]);
    }
    return;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
}

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}$$$.

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}$$$.

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$$$.

We also have other solutions, using inclusion-exclusion or generate function. Actually all the testers' solutions differs from each other.

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 5005;
int p[N] , q[N];
int n;
int f[N][N];
int h[N];
int fpow(int a,int b)
{
    int ans = 1;
    while(b){
        if(b & 1) ans = 1LL*ans*a%mod;
        a = 1LL*a*a%mod;b >>= 1;
    }
    return ans;
}
void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        int a,b;scanf("%d%d",&a,&b);
        p[i] = 1LL*a*fpow(b , mod - 2) % mod;
        q[i] = (1 - p[i] + mod) % mod;
    }
    for(int i = 0;i <= n;i++) scanf("%d",&h[i]);
    for(int i = 0;i <= n;i++) f[0][i] = h[i];
    for(int i = 1;i <= n;i++) {
        for(int j = 0;j <= n;j++) {
            f[i][j] = (1LL*p[i]*f[i - 1][j + 1] + 1LL*q[i]*f[i - 1][max(0 , j - 1)] ) % mod;
        }
        printf("%d ",f[i][0]);
    }
    printf("\n");
    return;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--) solve();
    return 0;
}

Actually I don't know how to hint. Try to find some rules related to $$$\frac{\sqrt{5}+1}{2}$$$, fibnacci or similar

Assume that the moment before the $$$x$$$-th operation(but after $$$i-1$$$-th), the first time we have $$$S_{max} \le 2S_{min}$$$. Let's divide the operation into two part: before $$$i$$$ and equal or after $$$i$$$.

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}}$$$.

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}$$$.