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