22722!
22722!
WYSI
WYFSI
22722!
22722!

Notice that the array size is even length. Usually in such problems, we would split the array into $$$2$$$ equal parts. Can you figure out what those $$$2$$$ parts are?

We sort the array and split it into the big half and the small half.

The main idea is that we can split the numbers into the two halves, the big half and small half, we can place the bigger half at the odd positions and the smaller half at the even positions.

This works because the smallest big number is larger than the biggest small number. Hence, the mean of any two small numbers is smaller than any big number, and the mean of any two big numbers is bigger than any small number.

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << 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(auto 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()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[55];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,0,2*n) cin>>arr[x];
		
		sort(arr,arr+2*n);
		
		rep(x,0,n) cout<<arr[x]<<" "<<arr[x+n]<<" ";
		cout<<endl;
	}
}

[(lambda n: (lambda arr : [print(f'{arr[i]} {arr[i+n]}', end = ' \n'[i==n-1]) for i in range(n)])(sorted(list(map(int,input().split())))))(int(input())) for _ in range(int(input()))]

Read the name of the problem ;)

$$$1111=11 \cdot 101$$$

All numbers other than $$$11$$$ and $$$111$$$ are useless.

Method 1

Notice that $$$1111=11 \cdot 100+11$$$ and similarly $$$11111=111 \cdot 100 + 11$$$. This implies that we can construct $$$1111$$$ and all bigger numbers using only $$$11$$$ and $$$111$$$. So it suffices to check whether we can construct $$$X$$$ from $$$11$$$ and $$$111$$$ only.

Suppose $$$X=A \cdot 11 + B \cdot 111$$$, where $$$A,B \geq 0$$$. Suppose $$$B=C \cdot 11 + D$$$, where $$$D \lt 11$$$. Then $$$X=(A+C \cdot 111) \cdot 11 + D \cdot 111$$$. So we can just brute force all $$$11$$$ value of $$$D$$$ to check whether $$$X$$$ can be made.

Method 2

Since $$$\gcd(11,111)=1$$$, by the Chicken McNugget Theorem, all numbers greater than $$$1099$$$ can be written as a sum of $$$11$$$ and $$$111$$$. We can use brute force to find the answer to all values less than or equal to $$$1099$$$ and answer yes for all other numbers.

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << 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(auto 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()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		int n;
		cin>>n;
		
		rep(x,0,20){
			if (n%11==0){
				cout<<"YES"<<endl;
				goto done;
			}
			
			n-=111;
			if (n<0) break;
		}
		cout<<"NO"<<endl;
		
		done:;
	}
}

[(lambda n : print("YES" if (n >= 111*(n%11)) else "NO"))(int(input())) for _ in range(int(input()))]

Try dp!

The dp states are position and number of potions drank.

Speedup dp or use greedy for full solution.

Method 1 — DP

Let's consider a dynamic programming solution. Let $$$dp[i][k]$$$ be the maximum possible health achievable if we consider only the first $$$i$$$ potions, and $$$k$$$ is the total number of potions taken.

The transition is as follows: $$$dp[i][k] = max(dp[i-1][k-1] + a_i, dp[i-1][k])$$$ if $$$dp[i-1][k-1] + a_i \geq 0$$$, and just $$$dp[i-1][k]$$$ otherwise. The first term represents the case if we take potion $$$i$$$ and the second term is when we ignore potion $$$i$$$.

This runs in $$$O(n^2)$$$ and passes the easy version.

Method 2 — Greedy 1

We iterate through the potions in non-decreasing order and drink the potion if we do not die.

For convenience, we define $$$c_i=a_i+i \cdot \epsilon$$$, where $$$\epsilon$$$ is a very small real number so that we can treat $$$c_i$$$ as distinct integers. We will show by exchange argument that our greedy is optimal.

Let $$$S$$$ be the set of potions that is an optimal solution.

Suppose $$$i \lt j$$$ and $$$c_i \lt c_j$$$. If $$$i \in S$$$ and $$$j \notin S$$$, then removing $$$i$$$ and adding $$$j$$$ into $$$S$$$ will still make $$$S$$$ a valid solution.

Now, suppose that position $$$i$$$ is not drunk. We can assume that there are no $$$k$$$ ($$$k \lt i$$$) such that $$$c_k \lt c_i$$$ and $$$k$$$ is drunk by the previous assertion. Suppose we add $$$i$$$ into $$$S$$$. If we reach a position $$$j$$$ (we possibly die at $$$j$$$) where $$$c_j \lt c_i$$$, then we can remove $$$j$$$ from $$$S$$$ and add $$$i$$$ to $$$S$$$. Otherwise, our greedy will also not choose $$$i$$$, as it was not chosen when we only consider indexes $$$k$$$ such that $$$c_k \lt c_i$$$.

Notice that we can arbitrarily define the way $$$\epsilon$$$ is added, so basically we can process $$$a_i$$$ in any non-increasing fashion.

Doing this naively is $$$O(n^2)$$$ as well. However, using a range add range max lazy propagation segment tree, we can check if a certain potion can be drunk without dying, and the solution runs in $$$O(n \log n)$$$.

Method 3 — Greedy 2 / DP 2

We process the potions from left to right. At the same time, we maintain the list of potions we have taken so far. When processing potion $$$i$$$, if we can take $$$i$$$ without dying, then we take it. Otherwise, if the most negative potion we've taken is more negative than potion $$$i$$$, then we can swap out potion $$$i$$$ for that potion. To find the most negative potion we've taken, we can maintain the values of all potions in a minimum priority_queue. This runs in $$$O(nlogn)$$$ as well

To prove that this works, let's consider best solution where we take exactly $$$k$$$ potions (best as in max total health). The solution involves taking the $$$k$$$ largest values in our priority queue. Then when considering a new potion, we should see whether swapping out the new potion for the $k$th largest potion will improve the answer.

Since the priority queue is strictly decreasing, there will be a cutoff $$$K$$$, where for $$$k$$$ at most $$$K$$$, the answer is not affected, and for larger than $$$K$$$, we swap out the $$$k$$$th largest potion. It turns out this process is equivalent to inserting the new potion's value into the priority_queue. For those positions at most $$$K$$$, they are not affected. For the positions larger than $$$K$$$, the elements get pushed back one space, meaning that the smallest element is undrinked.

This can also be seen as an efficient way to to transition from one layer of the $$$dp$$$ table to the next.

#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> ii;

struct node{
	int s, e, m;
	long long val = 0; long long lazy = 0;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void apply(long long L){
		val += L;
		lazy += L;
	}
	void push(){
		if(s == e) return;
		l->apply(lazy);
		r->apply(lazy);
		lazy = 0;
	}
	
	void update(int S, int E, long long L){
		push();
		if(s == S && E == e){
			apply(L);
			return;
		}
		else if(E <= m) l->update(S, E, L);
		else if(S >= m+1) r->update(S, E, L);
		else l->update(S, m, L), r->update(m+1, E, L);
		val = min(l->val, r->val);
	}
	
	long long query(int S, int E){
		push();
		if(s == S && E == e) return val;
		else if(E <= m) return l->query(S, E);
		else if(S >= m+1) return r->query(S, E);
		else return min(l->query(S, m), r->query(m+1, E));
	}
} *root;	


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	ii arr[n];
	for(int i = 0;i < n;i++){
		cin >> arr[i].first;
		arr[i].second = i;
	}
	
	sort(arr,arr+n);
	reverse(arr,arr+n);
	int ans = 0;
	root = new node(0, n-1);
	for(int i = 0;i < n;i++){
		int pos = arr[i].second;
		long long x = arr[i].first;
		
		if(x + root->query(pos,n-1) >= 0){
			ans++;
			root->update(pos,n-1,x);
		}
	}
	
	cout << ans;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	priority_queue<long long, vector<long long>, greater<long long> > pq;
	long long S = 0;
	
	for(int i = 1;i <= n;i++){
		long long x; cin >> x;
		S += x;
		pq.push(x);
		
		while(S < 0){
			S -= pq.top();
			pq.pop();
		}
	}
	
	cout << (int) pq.size();
}

import heapq
H = []
n=int(input())
for i in list(map(int,input().split())):
    tot = (tot+i if 'tot' in locals() or 'tot' in globals() else i)
    tot -= ((heapq.heappush(H,i) if tot >= 0 else heapq.heappushpop(H,i)) or 0)
print(len(H))

The time it takes for Anton's body to revert the string is related to inversion number.

We claim that in the optimal answer all characters of some type will appear consecutively.

So, we can try all $$$24$$$ possible strings and check the number of moves Anton's body needs to transform each string. The time limit is relaxed enough for a $$$O(n \log n)$$$ similar to 1430E - String Reversal.

But there is a $$$O(n)$$$ solution, the number of moves Anton's body needs to transform each string is given by the number of inversions in the string. But since we know that we only care about strings that have all the same characters appear consecutively, we can just keep a count of the number of inversions for each pair of characters.

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << 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(auto 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()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
string s;
int cnt[4];

ll flips[4][4];

map<char,int> id={{'A',0},{'N',1},{'O',2},{'T',3}};
string cset="ANOT";

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>s;
		n=sz(s);
		
		memset(cnt,0,sizeof(cnt));
		memset(flips,0,sizeof(flips));
		
		rep(x,0,n){
			cnt[id[s[x]]]++;
		}
		rep(a,0,4){
			int curr=0;
			rep(x,0,n){
				flips[a][id[s[x]]]+=curr;
				if (id[s[x]]==a) curr++;
			}
		}
		
		ll best=-1;
		vector<int> ans;
		
		vector<int> v={0,1,2,3};
		do{
			ll curr=0;
			rep(x,0,4){
				rep(y,x+1,4){
					curr+=flips[v[y]][v[x]];
				}
			}
			
			if (curr>best){
				best=curr;
				ans=v;
			}
		} while (next_permutation(all(v)));
		
		for (auto &it:ans) rep(x,0,cnt[it]) cout<<cset[it];
		cout<<endl;
	}
}

import itertools

TC=int(input())

m={"A":0,"N":1,"O":2,"T":3}
st="ANOT"

for _ in range(TC):
	s=input()
	arr=[]
	
	for ch in s:
		arr.append(m[ch])
	
	cnt=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
	cnt1=[0,0,0,0]
	
	for i in arr:
		for j in range(4):
			cnt[j][i]+=cnt1[j]
		cnt1[i]+=1
	
	val=-1
	best=[]
	
	for perm in itertools.permutations([0,1,2,3]):
		curr=0
		for i in range(4):
			for j in range(i+1,4):
				curr+=cnt[perm[j]][perm[i]]	
		
		if (curr>val):
			val=curr
			best=perm
			
	
	for i in range(4):
		for j in range(cnt1[best[i]]): print(st[best[i]],end="")
	
	print()

Try to solve the problem of the minimal $$$K$$$ needed to make a string with such a suffix array.

First, let's consider a simpler problem.

Is it possible to make a string with a certain suffix array given an alphabet size $$$k$$$.

Consider two adjacent suffixes in the suffix array "xy" and "ab" where $$$b$$$ and $$$y$$$ are some strings and $$$x$$$ and $$$a$$$ are some characters i.e. $$$x$$$ is the first character of that suffix and similarly for $$$a$$$. If $$$b$$$ and $$$y$$$ don't exist we consider them as \$, i.e. smaller than everything. Also, "xy" comes before "ab".

Observation: If the position of $$$b$$$ is less than the position of $$$y$$$ in the suffix array, $$$x$$$ must be less than $$$a$$$. Otherwise, $$$x$$$ must be less than or equal to $$$a$$$.

This can be easily shown as "xy" must be lexicographically smaller than "ab". This is sufficient also.

Thus we can iterate through the suffix array and check if $$$pos[arr[i]+1] \gt pos[arr[i+1]+1]$$$ where $$$arr$$$ is the suffix array and $$$pos$$$ is the position of the $$$i$$$th element in the suffix array. If this condition holds then the $$$arr[i]$$$ th character must be strictly less than the $$$arr[i+1]$$$ th character. Thus we can just count how many such pairs exist. If this count is larger than the alphabet size no such string is possible. Otherwise, such string exists. Note that special care must be taken when considering $$$arr[i]=n-1$$$ as $$$pos[n]$$$ may not be defined ($$$0$$$-indexed).

After tackling the simpler question we move on to the full question of counting how many such strings are there. If we consider the string as an array and the order of the array as the order of the suffix array meaning that the $$$i$$$ th element of this array is the $$$arr[i]$$$ th element of the string. We have now transformed the question into "Given that some elements must be greater than the previous elements while others can be equal. Count how many arrays are there such that the largest element is less than $$$k$$$".

Consider the difference array, some elements must be $$$\geq 1$$$ while some can be $$$\geq 0$$$. We add padding to the front and back of the array so as to account for the first value being non-zero and the last element being less than $$$k$$$. These two elements are both $$$\geq 0$$$. Let $$$cnt$$$ be the number of elements that must be $$$\geq 1$$$ in the difference array. Now, this becomes count how many arrays of $$$(n-1+2)=(n+1)$$$ non-negative elements sum to $$$k-cnt$$$. This can be solved using stars and bars so the final answer comes out to be $$$n+1+k-cnt \choose n$$$ which can be found easily. Note that we define $$$\binom{a}{b}=0$$$ when $$$a \lt b$$$.

Final Complexity $$$O(n\log MOD)$$$ or $$$O(n)$$$ depending on how you find the modular inverse.

Btw $$$k$$$ was chosen to also be $$$\leq 2\times 10^5$$$ so as to hide the final complexity :)

/*input
5 4
3 4 2 1 0

*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e17;
const int INF=0x3f3f3f3f;
const ll MOD=998244353;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){

    if(b<=0) return 1;
    if(a<=0) return 0;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
int arr[maxn],pos[maxn];
ll inv(ll x){
    return mypow(x,MOD-2);
}
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,k;
    cin>>n>>k;
    --k;
    REP(i,n) cin>>arr[i],pos[arr[i]]=i;
    pos[n]=-1;
    int cnt=0;
    REP(i,n-1){
        // character at arr[i] and arr[i+1] cannot be the same
        if(pos[arr[i]+1]>pos[arr[i+1]+1]){
            ++cnt;
        }
    } 
    //calculate c(k-cnt+n+1-1,n+1-1)
    k-=cnt;
    if(k<0){
        cout<<0;
        return 0;
    }
    ll ans=1;
    REP1(i,n){
        ans=mult(ans,inv(i));
        ans=mult(ans,(k+i));
    }
    cout<<ans;
}

MOD=998244353

n,k=map(int,input().split())
arr=list(map(int,input().split()))

pos=[0]*(n+1)

for i in range(n):
	pos[arr[i]]=i
pos[n]=-1

cnt=0

for i in range(n-1):
	if (pos[arr[i]+1]>pos[arr[i+1]+1]): cnt+=1

#k-cnt+n-1 choose n
num,denom=1,1

for i in range(n):
	num=num*(k-cnt+n-1-i)%MOD
	denom=denom*(i+1)%MOD

print(num*pow(denom,MOD-2,MOD)%MOD)

Find elements $$$1$$$ and $$$2$$$ in $$$N+420$$$ queries.

Find a pair $$$(a,b)$$$ such that $$$|p[b]-p[a]| \leq \frac{n}{3}-c$$$, where $$$c$$$ is some constant.

The problem can be broken into $$$2$$$ main parts:

• Finding a pair $$$(a,b)$$$ such that $$$|p[a]-p[b]|$$$ is roughly less than a third.
• Finding elements $$$1$$$ and $$$2$$$ (actually we may find $$$N$$$ and $$$N-1$$$ but it is the same).
• Find the rest of the elements

A convenient way to think about the queries, is that given $$$p[a] \lt p[b] \lt p[c]$$$, we will be returned $$$\max(p[b]-p[a],p[c]-p[b])$$$.

We will spend the first queries to find a tuple $$$(a,b,c)$$$ such that the return value of this query is at most $$$\lfloor \frac{n-4}{6} \rfloor$$$. The easiest way to do this is by randomly choosing distinct $$$a$$$,$$$b$$$,$$$c$$$ and querying it. See proof 1 for the random analysis. But there is also a deterministic solution. Choose any $$$13$$$ elements from the array, and it is guaranteed that there exists a tuple in those $$$13$$$ elements such that the return value of the query is at most $$$\lfloor \frac{n-4}{6} \rfloor$$$, see proof 2. To query all tuples in this sub-array of size $$$13$$$, it takes $$$286$$$ queries, which fits very comfortably under $$$420$$$. user14767553 conjectured that a sub-array of size $$$10$$$ works, however we are unable to prove it. You can try to hack his solution at 117685511.

Among $$$a$$$, $$$b$$$, and $$$c$$$, we choose $$$a$$$ and $$$b$$$. The important idea here is that the gap between $$$a$$$ and $$$b$$$ is small, because we have found a tuple $$$(a,b,c)$$$ is less than or equal to $$$\lfloor \frac{n-4}{6} \rfloor$$$, so $$$|p[a]-p[b]| \leq 2 \cdot \lfloor \frac{n-4}{6} \rfloor \leq \lfloor \frac{n-4}{3} \rfloor$$$. Now, we query all tuples $$$(a,b,x)$$$ for all $$$x \ne a$$$ and $$$x \ne b$$$. Since the gap between $$$a$$$ and $$$b$$$ is small, we should be able to identify either $$$(1,2)$$$ or $$$(n,n-1)$$$. This is because either $$$p[a]-1 \gt p[b]-p[a]$$$ or $$$n-p[b] \gt p[b] - p[a]$$$ (WLOG assuming $$$p[b] \gt p[a]$$$), see proof 3. Therefore, the furthest $$$x$$$ will return the largest value when querying for $$$(a,b,x)$$$. (If there's ties choose anyone).

Suppose we found element $$$1$$$, there are at most two possible candidates for element $$$2$$$, $$$y_1$$$ and $$$y_2$$$ (the other possible candidate will be either $$$n$$$ or $$$n-1$$$). We can use 2 queries to figure out which of them is element $$$2$$$. We can query $$$(1, y_1, a)$$$ and $$$(1, y_2, a)$$$. Whichever produces the smaller value is element $$$2$$$, see proof 4.

Once we have found elements $$$1$$$ and $$$2$$$, solving the rest of the problem is simple. Querying $$$(1,2,x)$$$ will always return $$$x-2$$$. And we can find the rest of the elements in another $$$n-2$$$ queries. Do not forgot about the condition that $$$p[0] \lt p[1]$$$!

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define up upper_bound

#define rep(x,start,end) for(auto 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()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(177013);

int query(int a,int b,int c){
	cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
	int temp;
	cin>>temp;
	
	return temp;
}

void sort(int &a,int &b,int &c){
	 if (a>b) swap(a,b);
	 if (b>c) swap(b,c);
	 if (a>b) swap(a,b);
}

void solve(){
	int n;
	cin>>n;
	
	vector<int> ans(n+5,0);
	
	set<tuple<int,int,int> > s;
	
	int a,b,c;
	rep(x,1,14) rep(y,x+1,14) rep(z,y+1,14){
		if (query(x,y,z)<=(n-4)/6){
			a=x,b=y,c=z;
			break;
		}
	}
	
	map<int,vector<int>,greater<int> > m;
	rep(x,1,n+1) if (x!=a && x!=b){
		m[query(a,b,x)].push_back(x);
	}
	
	int hv=(*m.begin()).fi;
	if (sz(m[hv-1])>=2){ //there must be exactly 2
		if (query(m[hv][0],m[hv-1][0],a)>
			query(m[hv][0],m[hv-1][1],a))
				swap(m[hv-1][0],m[hv-1][1]);
	}
	
	int hi=m[hv][0],hi2=m[hv-1][0];
	
	//cout<<hi2<<" "<<hi<<endl;
	
	ans[hi]=1,ans[hi2]=2;
	rep(x,1,n+1) if (x!=hi2 && x!=hi){
		ans[x]=query(hi,hi2,x)+2;
	}
	
	if (ans[1]>ans[2]) rep(x,1,n+1) ans[x]=n-ans[x]+1;
	
	cout<<"! "; rep(x,1,n+1) cout<<ans[x]<<" "; cout<<endl;
	
	cin>>n; //read stupid value
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		solve();
	}
}

import sys, random

print = sys.stdout.write
input = sys.stdin.readline

def query(a, b, c):
    print("? " + str(a+1) + " " + str(b+1) + " " + str(c+1) + "\n")
    sys.stdout.flush()
    return int(input())

def answer():
    print("! " + " ".join([str(i) for i in ans]) + "\n")
    sys.stdout.flush()
    return int(input())

T = int(input())
testVal = 13

randomQueryOrder = []
for i in range(testVal):
    for j in range(i+1, testVal):
        for k in range(j+1, testVal):
            randomQueryOrder.append((i, j, k))

for caseno in range(T):
    N = int(input())
    
    a = -1
    b = -1

    ans = [0 for i in range(N)]
    res = [0 for i in range(N)]
    order = [i for i in range(N)]
    
    minVal = N+5
    
    random.shuffle(order)
    random.shuffle(randomQueryOrder)
    for ijk in randomQueryOrder:
        i, j, k = ijk
        i = order[i]
        j = order[j]
        k = order[k]
        temp = query(i, j, k)
        
        if temp <= (N-4)//6:
            a = i
            b = j
            break
    
    assert(a != -1 and b != -1)

    ''' Now, the key thing to note is that abs(P[a]-P[b]) is less than (roughly speaking) N/3.
    Observe that the index c such that query(a, b, c) is maximum must be such that P[c] == 1 or P[c] == N (some steps skipped).
    But given the condition P[1] < P[2], we can assume either, then flip using P[i] = N+1-P[i] if condition not satisfied.
    '''

    # Now, we assume P[c] = 1
    # There always exists another index d such that query(a, b, d) = query(a, b, c)-1 and P[d] = 2
    # There can be only at most 2 d which satisfy the former, and we can check which is which by comparing query(a, c, d)

    maxVal = -1
    c = -1
    for i in range(N):
        if a == i or b == i:
            continue
        
        res[i] = query(a, b, i)
        if res[i] > maxVal:
            maxVal = res[i]
            c = i

    d2 = []
    for i in range(N):
        if a == i or b == i:
            continue
        
        if res[i] == maxVal-1:
            d2.append(i)

    d = -1
    if len(d2) == 1:
        d = d2[0]
    elif len(d2) == 2:
        temp1 = query(a, c, d2[0])
        temp2 = query(a, c, d2[1])
        if temp1 < temp2:
            d = d2[0]
        else:
            d = d2[1]
    else:
        assert(False)

    # After finding indices c and d such P[c] = 1 and P[d] = 2, we can now find the rest of the values
    ans[c] = 1
    ans[d] = 2
    for i in range(N):
        if i == c or i == d:
            continue
        ans[i] = 2 + query(c, d, i)

    # Flip since P[1] < P[2] not satisfied
    if ans[0] >= ans[1]:
        for i in range(N):
            ans[i] = N+1-ans[i]

    result = answer()

    # I dislike getting WA, hence I make my code MLE
    if result != 1:
        MLE = [1 for i in range(1<<27)]
        sys.stdout.write(MLE[0])

How can we find the largest $$$k$$$ such that the $$$k$$$-th smallest element of the array is $$$0$$$?

How can we maintain $$$k$$$?

Let's define $$$cnt$$$ to represent the number of 1s in the array.

For the modifications, if $$$a_i$$$ is already $$$1$$$ now, then we let $$$cnt \gets cnt - 1$$$. Otherwise, let $$$cnt \gets cnt + 1$$$.

For the querys, just compare $$$cnt$$$ with $$$k$$$. If $$$cnt \ge k$$$, the answer will be $$$1$$$. Otherwise, the answer will be $$$0$$$.

The complexity : $$$O(n + q)$$$.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, q, a[N], cnt;
int main()
{
    scanf("%d%d",&n,&q);
	for(int i = 1; i <= n; ++i)
	{
    	scanf("%d",a+i);
		cnt += a[i];
	}
	while(q--)
	{
		int opt, x;
		scanf("%d%d",&opt,&x);
		if(opt == 1)
		{
			if(a[x]) cnt--;
			else cnt++;
			a[x] = 1 - a[x];
		}
		else
		{
			if(cnt >= x) puts("1");
			else puts("0");
		}
	}
	return 0;
}

n, q = map(int,input().split())
a = list(map(int,input().split()))
zero = a.count(0)
one = n - zero
for _ in range(q):
    t, x = map(int,input().split())
    if t == 1:
        if a[x-1] == 1:
            zero += 1
            one -= 1
            a[x-1] = 0
        else:
            zero -= 1
            one += 1
            a[x-1] = 1
    else:
        if x<=one:
            print(1)
        else:
            print(0)

When is the answer $$$0$$$? Or rather, when do you not have to make any moves?

What happens if $$$a[i]$$$ is same for all $$$i$$$?

Consider the following situations:

• $$$\forall i \in [2,n], |a_i - a_{i - 1}| = 0$$$, then the answer will be $$$v + \min(u, v)$$$.
• $$$\exists i \in [2,n], |a_i - a_{i - 1}| \gt 1$$$, then the answer will be $$$0$$$.
• Otherwise, the answer will be $$$\min(u, v)$$$.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, a[N], ans = INT_MAX, u, v, T;
int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
	    ans = INT_MAX;
	    cin >> n >> u >> v;
	    for(int i = 1; i <= n; i++)
		    cin >> a[i];
	    for(int i = 2; i <= n; i++)
	    {
		    if(abs(a[i] - a[i - 1]) >= 2) ans = 0;
	    	if(abs(a[i] - a[i - 1]) == 1) ans = min(ans, min(u, v));
		    if(a[i] == a[i - 1]) ans = min(ans, v + min(u, v));
	    }
	    cout << ans << endl;
	}
	
	return 0;
}

Think greedily!

By exchange argument, where can Pekora start her pass in an optimal solution?

For a series of passes, we can describe it as an array $$$P$$$ where $$$P_i$$$ is the trampoline Pekora starts at in the $$$i$$$-th pass. We claim that the final state of trampolines after performing any permutation of $$$P$$$ will be the same.

Now, we can claim that there is an optimal solution with $$$P$$$ being non-decreasing. Since Pekora can only move right, we must put Pekora on the first trampoline such that $$$S_i \ne 1$$$.

However, we cannot directly simulate putting Pekora on the first trampoline such that $$$S_i \ne 1$$$. This actually uses $$$O(N^3)$$$.

However, we can simulate this in $$$O(N^2)$$$ by the following. Instead of simulating passes individually, we will combine them. The main idea is that when Pekora jumps on a trampoline of strength $$$S_i$$$, we just add another Pekora on trampoline $$$S_i+i$$$ and process it later.

So, when we process trampolines from $$$1$$$ to $$$N$$$, we keep track of how many Pekoras there are on trampoline $$$i$$$, which we will denote as $$$C_i$$$. Then, we only add extra Pekoras to trampoline $$$i$$$ if $$$S_i \gt C_i+1$$$. Now, we have some Pekoras on trampoline $$$i$$$ and we need to update other values of $$$C_i$$$.

If $$$S_i=4$$$ and $$$C_i=6$$$ for example, we would add $$$1$$$ Pekora each trampolines to $$$i+2,i+3,i+4$$$ to reduce $$$S_i$$$ to 1. Then, the rest of the Pekoras will be moved to trampoline $$$i+1$$$.

This algorithm runs in $$$O(N^2)$$$ as we only need to update $$$O(N)$$$ other trampolines at each step.

Bonus: solve this problem in $$$O(N)$$$. (This was the original constraints but it was later changed since it was too hard for its position.)

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define up upper_bound

#define rep(x,start,end) for(auto 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()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[5005];
ll curr[5005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,0,n) cin>>arr[x];
		rep(x,0,n) curr[x]=0;
		
		ll ans=0;
		
		rep(x,0,n){
			ll temp=curr[x];
			
			if (temp<arr[x]-1){
				ans+=arr[x]-1-temp;
				temp+=arr[x]-1-temp;
			}
			
			curr[x+1]+=temp-arr[x]+1;
			if (x+2<n) rep(y,x+2,min(n,x+arr[x]+1)) curr[y]++;
		}
		
		cout<<ans<<endl;
	}
}

TC=int(input())

for tc in range(TC):
    n=int(input())
    arr=list(map(int,input().split()))
    
    curr=[0]*(n+5)
    
    ans=0
    
    for x in range(n):
        temp=curr[x]
        
        if (temp<arr[x]-1):
            ans+=arr[x]-1-temp
            temp+=arr[x]-1-temp
            
        curr[x+1]+=temp-arr[x]+1
        for y in range(x+2,min(n,x+arr[x]+1)):
            curr[y]+=1
        
    print(ans)

Since $$$\&$$$ is a bitwise operation, represent the number in binary form!

We can convert any $$$u+v$$$ move to a series of $$$u+v'$$$ moves where $$$u\&v'=v'$$$ and $$$v'=2^k$$$.

Such a move converts a substring of the binary string of the form $$$01\ldots11$$$ into $$$10\ldots00$$$.

Focus on converting $$$01$$$ into $$$10$$$.

Firstly, we can show that the reachability graph is equivalent if we restrict to a directed edge between vertices $$$u$$$ and $$$u+v$$$ if $$$u\&v=v$$$ and that $$$v=2^k$$$ for some $$$k$$$.

This is because we can add each bit from $$$v$$$ from $$$u$$$ from the highest bit as adding a bit to a number will not affect lower bits.

Now, we observe that such as operation converts a binary string of the form $$$01\ldots11$$$ into $$$10\ldots00$$$ for some substring when we represent $$$u$$$ as a binary string. (more significant bits are to the left).

Now, we consider $$$s$$$ and $$$t$$$ as binary strings.

If and only if there is a matching from bits in $$$t$$$ to a lower bit in $$$s$$$ and $$$t$$$ > $$$s$$$, then $$$t$$$ is reachable from $$$s$$$.

Turning $$$01\ldots11$$$ into $$$10\ldots00$$$ means that we can move a bit ($$$01$$$->$$$10$$$) or we can squish multiple bits ($$$0111$$$->$$$1000$$$).

Let us show it is necessary. If $$$s \gt t$$$, it is impossible. And if there is no such matching, we are not able to put a position in $$$t$$$ as bits cannot move back, or there are not enough bits in $$$s$$$ to form $$$t$$$ (since the number of bits cannot increase).

Let is show it is sufficient. Since $$$s \lt t$$$ ($$$s=t$$$ is trivial), the strings have some common prefix and the most significant different bit has $$$0$$$ in $$$s$$$ and $$$1$$$ and $$$t$$$. Now, we can shift every bit in s into a position in t and squish the most significant bits.

To check if there is a matching, we find the least significant bit ($$$lsb$$$) of $$$t$$$ and $$$s$$$. if $$$lsb(t) \lt lsb(s)$$$ or if $$$s = 0$$$, then it is impossible. Else, we remove the $$$lsb$$$ from both $$$t$$$ and $$$s$$$ and repeat. If we're able to remove bits until $$$t=0$$$, then it is possible to go from $$$s$$$ to $$$t$$$.

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define up upper_bound

#define rep(x,start,end) for(auto 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()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		int a,b;
		cin>>a>>b;
		
		vector<int> va,vb;
		
		if (a>b){
			cout<<"NO"<<endl;
			goto done;
		}
		
		rep(x,0,30){
			if (a&(1<<x)) va.pub(x);
			if (b&(1<<x)) vb.pub(x);
		}
		
		if (sz(va)<sz(vb)){
			cout<<"NO"<<endl;
			goto done;
		}
		
		rep(x,0,sz(vb)){
			if (va[x]>vb[x]){
				cout<<"NO"<<endl;
				goto done;
			}
		}
		
		cout<<"YES"<<endl;
		
		done:;
	}
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;
	while(t--){
		int x,y;cin >> x >> y;
		int z=0;
		bool ok=(x<=y);
		for(int i=0; i<30 ;i++){
			if((x>>i)&1) z++;
			if((y>>i)&1) z--;
			if(z<0) ok=false;
		}
		if(ok) cout << "YES\n";
		else cout << "NO\n";
	}
}

def lsb(x):
    return x & (-x)
Q = int(input())
for q in range(Q):
    a,b = map(int,input().split(" "))
    if a > b:
        print("NO")
    else:
        can = True
        while b > 0:
            if lsb(b) < lsb(a) or a == 0:
                can = False
                break
            a -= lsb(a)
            b -= lsb(b)
        print("YES" if can else "NO")

The only pair $$$(j,k)$$$ that satisfies $$$F_i=F_j+F_k$$$ is $$$(i-1,i-2)$$$.

Firstly, we can discover that we can only cut a tree in the size of $$$f_{i}$$$ into one in size of $$$f_{i-1}$$$ and one in size of $$$f_{i-2}$$$.

However, we will have 2 ways to partition the tree sometimes. But it turns out we can cut any edge!

We will prove that if some edge cuts Fib-tree of $$$F_n$$$ vertices into trees with sizes $$$F_{n-1}$$$ and $$$F_{n-2}$$$, we can cut it, and the resulting trees are also Fib-trees.

Because the growth of Fibonacci sequence is approximately $$$O(\phi^n)$$$, we only need to cut our tree $$$O(\log_\phi n)$$$ times: every time, if we find the splitting edge, we cut it, and recurse to the resulting trees, if at some point there was no splitting edge — tree isn't Fib-tree.

Finally, we got an $$$O(n\log_\phi n)$$$ solution.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, siz[N];
vector<int> fib;
vector<pair<int, bool> > G[N];
void NO() { cout << "NO\n"; exit(0); }
void GetSize(int u, int fa)
{
    siz[u] = 1;
    for(pair<int, bool> e : G[u])
    {
        if(e.second) continue;
        int v = e.first;
        if(v == fa) continue;
        GetSize(v, u);
        siz[u] += siz[v];
    }
}
void CutEdge(int u, int fa, int k, int &pu, int &pv, int &kd)
{
    for(pair<int, bool> e : G[u])
    {
        if(pu) return;
        if(e.second) continue;
        int v = e.first;
        if(v == fa) continue;
        if(siz[v] == fib[k - 1] || siz[v] == fib[k - 2])
        {
            pu = u; pv = v;
            kd = (siz[v] == fib[k - 1]) ? k - 1 : k - 2;
            break;
        }
        CutEdge(v, u, k, pu, pv, kd);
    }
}
void Check(int u, int k)
{
//    cout << "Check " << u << ' ' << k << endl;
    if(k <= 1) return;
    GetSize(u, 0);
    int pu = 0, pv = 0, kd = 0;
    CutEdge(u, 0, k, pu, pv, kd);
//    cout << pu << ' ' << pv << ' ' << kd << endl;
    if(!pu) NO();
    for(pair<int, bool> &e : G[pu])
        if(e.first == pv) e.second = true;
    for(pair<int, bool> &e : G[pv])
        if(e.first == pu) e.second = true;
    Check(pv, kd);
    Check(pu, (kd == k - 1) ? k - 2 : k - 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    fib.push_back(1);
    fib.push_back(1);
    for(int i = 1; ; i++)
    {
        if(fib[i] >= n) break;
        int new_fib = fib[i] + fib[i - 1];
        fib.push_back(new_fib);
    }
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(make_pair(v, false));
        G[v].push_back(make_pair(u, false));
    }
    if(fib[fib.size() - 1] != n) NO();
    Check(1, fib.size() - 1);
    cout << "YES\n";
    return 0;
}

Try to construct a solution that works in $$$2n$$$ queries.

Try to find the second magnet which is not `-'.

The actual query limit is $$$n-1+\lceil\log_2n\rceil$$$.

It seems this problem needs some random technique, but here is a determinate solution:

We just try to find a not demagnetized magnet.

You can go through the following method to find one:

First put the first magnet in the left.

Then ask all the other magnets with the left pile.

If we got a non-zero answer, we find a valid magnet; else we just put this magnet in the left.

It can be proven later that we will always be able to find a valid magnet.

Then use this magnet to try on all other magnets.

This process form a solution requiring at most $$$2n-2$$$ queries.

However, when we look back at this solution we'll realize that there is a huge waste of information in the previous queries.

As all the previous answers are $$$0$$$, it's easy to prove that the magnet we found is the second one we have selected.

Since we know nothing about the right part, we can simply check the magnets in the right one by one.

However, you have known that there is only $$$1$$$ magnetic magnet in the left, so you can do a binary search to seek for the answer.

The maximum number of queries is $$$n-1+\lceil\log_2n\rceil$$$, which perfectly matches the limit.

#include<bits/stdc++.h>
int n;
std::vector<int>ans,tmp,hlf;
int main()
{
    int T;
	scanf("%d",&T);
	for(;T--;)
	{
	    ans.clear(),tmp.clear(),hlf.clear();
    	scanf("%d",&n);
    	register int i,ii;
    	int sec=0;
    	for(i=2;i<=n;i++)
    	{
    		printf("? 1 %d\n%d\n",i-1,i);
    		for(ii=1;ii<i;ii++)printf("%d ",ii);
    		puts(""),fflush(stdout);
    		int f;
    		scanf("%d",&f);
    		if(f){sec=i;break;}
    	}for(i=sec+1;i<=n;i++)
    	{
    		printf("? 1 1\n%d\n%d\n",sec,i);
    		fflush(stdout);
    		int f;
    		scanf("%d",&f);
    		if(!f)ans.push_back(i);
    	}for(i=1;i<sec;i++)tmp.push_back(i);
    	while(tmp.size()>1)
    	{
    		int md=tmp.size()>>1;
    		hlf.clear();
    		for(i=1;i<=md;i++)
    			hlf.push_back(tmp.back()),tmp.pop_back();
    		printf("? 1 %d\n%d\n",md,sec);
    		for(int t:hlf)printf("%d ",t);
    		puts(""),fflush(stdout);
    		int f;
    		scanf("%d",&f);
    		if(f)tmp=hlf;
    	}
    	for(i=1;i<sec;i++)if(tmp[0]!=i)ans.push_back(i);
    	printf("! %u",ans.size());
    	for(int t:ans)printf(" %d",t);
    	puts(""),fflush(stdout);
	}
}

Visualize this problem as graph with directed edges $$$(i,c_i)$$$.

Solve this problem where there is only $$$1$$$ big cycle.

What if a cycle has $$$2$$$ coins that are upside down? How can we force a cycle into such state?

We can visualize the problem as a graph with nodes of $$$2$$$ colors (face up — red and face down — blue). Initially, the graph has nodes with all red color and with a directed edge to $$$c_i$$$.

Firstly, any $$$2$$$ cycles with all red nodes can be converted into a single cycle with $$$2$$$ blues nodes with $$$1$$$ swap.

A cycle with $$$2$$$ blue nodes is very convenient here as swapping a blue node with a red node it is pointing to will decrease the cycle size and maintain that the cycle still has $$$2$$$ blue nodes. We can keep decreasing the cycle size until the cycle has only $$$2$$$ blue nodes and solve that in $$$1$$$ swap. Thus, solving $$$2$$$ cycles which have $$$X$$$ nodes in total uses only $$$X$$$ swaps.

Now, we simply pair the cycles and do this.

However, if there is an odd number of cycles, there are $$$2$$$ cases:

If the cycle does not cover the whole graph, we can solve the remaining cycle and a cycle of size $$$1$$$ together.

Otherwise, we can force $$$2$$$ blue nodes into the cycle with $$$2$$$ swaps (does not work for $$$n = 2$$$ so be careful).

Both cases need $$$X+1$$$ moves where $$$X$$$ is the size of the remaining cycle.

Thus, at most $$$X+1$$$ swaps is needed in this algorithm.

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define up upper_bound

#define rep(x,start,end) for(auto 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()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[200005];
bool vis[200005];
vector<ii> ans;

void cswap(int i,int j){
	swap(arr[i],arr[j]);
	arr[i]=-arr[i],arr[j]=-arr[j];
	ans.pub(ii(i,j));
}

void swap_cyc(int i,int j){
	cswap(i,j);
	
	int curr=i;
	while (arr[-arr[curr]]>0){
		cswap(curr,-arr[curr]);
	}
	
	curr=-arr[curr];
	while (arr[-arr[curr]]>0){
		cswap(curr,-arr[curr]);
	}
	
	cswap(curr,-arr[curr]);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	rep(x,1,n+1) cin>>arr[x];
	
	int p=-1;
	
	rep(x,1,n+1) if (!vis[x]){
		if (arr[x]==x) continue;
		
		int curr=x;
		do{
			vis[curr]=true;
			curr=arr[curr];
		} while (curr!=x);
		
		if (p==-1) p=x;
		else{
			swap_cyc(p,x);
			p=-1;
		}
	}
	
	if (p!=-1){
		bool can=false;
		rep(x,1,n+1) if (arr[x]==x){
			swap_cyc(p,x);
			can=true;
			break;
		}
		
		if (!can){
			int t1=arr[p],t2=arr[arr[p]];
			cswap(p,t1);
			swap_cyc(t1,t2);
		}
	}
	
	cout<<sz(ans)<<endl;
	for (auto &it:ans) cout<<it.fi<<" "<<it.se<<endl;
}

from sys import stdin, stdout

n=int(stdin.readline())

#make 1-indexed
arr=[0]+list(map(int,stdin.readline().split()))

vis=[0]*(n+1)

ans=[]

def cswap(i,j):
    arr[i],arr[j]=-arr[j],-arr[i]
    ans.append((i,j))
    
def swap_cyc(i,j):
    cswap(i,j)
    
    curr=i
    while (arr[-arr[curr]]>0):
        cswap(curr,-arr[curr])
        
    curr=-arr[curr]
    while (arr[-arr[curr]]>0):
        cswap(curr,-arr[curr])
        
    cswap(curr,-arr[curr])
    
p=-1
for i in range(1,n+1):
    if (vis[i]==1): continue
    if (arr[i]==i): continue
    
    curr=i
    while (True):
        vis[curr]=1
        curr=arr[curr]
        if (curr==i): break
        
    if (p==-1): 
        p=i
    else:
        swap_cyc(p,i)
        p=-1

if (p!=-1):
    can=False
    for i in range(1,n+1):
        if (arr[i]==i):
            swap_cyc(p,i)
            can=True
            break
        
    if (can==False):
        t1,t2=arr[p],arr[arr[p]]
        cswap(p,t1)
        swap_cyc(t1,t2)
            
print(len(ans))
[print(i[0],i[1]) for i in ans]

The complexity is $$$\mathcal O(n\sqrt{n})$$$.

Divide the nodes into $$$\sqrt{n}$$$ blocks. The $$$i$$$-th block will contain the nodes in $$$[(i-1) \sqrt{n}+1,i \sqrt{n}]$$$.

Let's define $$$f_x$$$ as an ancestor of $$$x$$$ such that $$$f_x$$$ is in the same block as $$$x$$$ and $$$a_{f_x}$$$ is not in the same block as $$$x$$$.

Notice that for a given block, if all $$$a_x$$$ is not in the same block as $$$x$$$, then $$$f_x=x$$$.

So, we do not have to re-compute all values of $$$f_x$$$ for a certain block if $$$\forall x, x-a_x \geq \sqrt n$$$ in this block.

When we update a range, we will update some ranges fully and update at most $$$2$$$ ranges partially. Let's show that only $$$O(n+q)$$$ re-computations will happen.

For a certain block, if it is completely contained in an update, the value of $$$x-a_x$$$ will increase by $$$1$$$, a single block will be re-computed by at most $$$O(\sqrt n)$$$ of such updates, which will contribute $$$O(\sqrt n \cdot \sqrt n)=O(n)$$$ re-computations.

For blocks that are partially updated by an update, such things will only happen at most $$$2q$$$ times, therefore we have a bound of $$$O(q)$$$ re-computations from such updates.

Maintaining $$$f_x$$$, querying can be easily done in $$$O(\sqrt n)$$$.

#include <bits/stdc++.h>
#define N 100005
using namespace std;

template <typename T>

void read(T &a)
{
	T x = 0,f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	a = x * f;
}

template <typename T>

void write(T x)
{
	if (x < 0) putchar('-'),x = -x;
	if (x < 10) return (void) putchar(x + '0');
	write(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>

void writeln(T x)
{
	write(x);
	putchar('\n');
}

template <typename T>

void writes(T x)
{
	write(x);
	putchar(' ');
}

template <typename T,typename... Args> 

void read(T &maxx,Args &... args)
{
	read(maxx);
	read(args...);
}

template <typename T,typename... Args>

void writeln(T maxx,Args ... args)
{
	writes(maxx);
	writes(args...);
	putchar('\n');
}

const int B = 300;
int n,q,a[N],num,bl[N],vis[N];
std::vector<int> v;

struct Block
{
	int f[B],lazy,flag,cnt,L,R;
	void update()
	{
		flag = 1;
		for (int i = L; i <= R; i++)
		{
			if (bl[i] != bl[a[i]]) f[i - L] = i;
			else f[i - L] = f[a[i] - L],flag = 0;
		}
	}
	void update(int l,int r,int x)
	{
		for (int i = l; i <= r; i++)
			a[i] = i == 1 ? 0 : max(a[i] - x,1);
		update();
	}
	void update(int x)
	{
		if (flag) lazy += x;
		else update(L,R,x);
	}
}T[(N - 1) / B + 5];

void update(int l,int r,int x)
{
	if (bl[l] == bl[r])
	{
		T[bl[l]].update(l,r,x);
		return ;
	}
	T[bl[l]].update(l,T[bl[l]].R,x);
	for (int i = bl[l] + 1; i < bl[r]; i++)
		T[i].update(x);
	T[bl[r]].update(T[bl[r]].L,r,x);
	// cout << l << ' ' << r << ' ' << x << endl;
	// cout << '0' << ' ';
	// for (int i = 2; i <= n; i++)
	// 	cout << max(a[i] - T[bl[i]].lazy,1) << ' ';
	// cout << endl;
}

void clear()
{
	for (int i = 0; i < v.size(); i++)
		vis[v[i]] = 0;
	v.clear();
}

int query(int x,int y)
{
	// cout << '0' << ' ';
	// for (int i = 2; i <= n; i++)
	// 	cout << max(a[i] - T[bl[i]].lazy,1) << ' ';
	// cout << endl;
	while (T[bl[x]].f[x - T[bl[x]].L] != T[bl[y]].f[y - T[bl[y]].L])
	{
		if (bl[x] < bl[y]) swap(x,y);
		// cout << x << ' ' << T[bl[x]].f[x - T[bl[x]].L] << endl;
		x = (T[bl[x]].f[x - T[bl[x]].L] == 1) ? 0 : max(a[T[bl[x]].f[x - T[bl[x]].L]] - T[bl[x]].lazy,1);
	}
	int qaq = (T[bl[x]].f[x - T[bl[x]].L] == 1) ? 0 : max(a[T[bl[x]].f[x - T[bl[x]].L]] - T[bl[x]].lazy,1);
	while (x != qaq)
	{
		assert(x != qaq);
		vis[x] = 1;
		v.push_back(x);
		x = (x == 1) ? 0 : max(a[x] - T[bl[x]].lazy,1);
	}
	while (y != qaq)
	{
		if (vis[y]) return clear(),y;
		y = (y == 1) ? 0 : max(a[y] - T[bl[y]].lazy,1);
	}
}

signed main()
{
	read(n,q);
	for (int i = 2; i <= n; i++) read(a[i]);
	num = (n - 1) / B + 1;
	for (int i = 1; i <= num; i++)
	{
		T[i].L = (i - 1) * B + 1;
		T[i].R = min(i * B,n);
		T[i].cnt = i * B - (i - 1) * B;
		T[i].flag = T[i].lazy = 0;
		for (int j = T[i].L; j <= T[i].R; j++)
			bl[j] = i;
	}
	for (int i = 1; i <= num; i++)
		T[i].update();
	while (q--)
	{
		int opt;
		read(opt);
		if (opt == 1)
		{
			int l,r,x;
			read(l,r,x);
			update(l,r,x);
		}
		if (opt == 2)
		{
			int u,v;
			read(u,v);
			writeln(query(u,v));
		}
	}
	// cerr << (double) clock() / CLOCKS_PER_SEC << endl;
	return 0;
}

Convert the queue into a circle.

Firstly, let's convert the queue into a circle. In our new problem, $$$n$$$ animals stand in a circle. The king fights the animal directly clockwise to it. If the king wins, he and the other person swap places, otherwise nothing happens. The animal that is king will always move 1 space clockwise regardless of what happens.

For example, in this scenario, 0 beats 1, so he stays as king. But he then loses to 2.

Call animals whose A is smaller than the B of the animal before them RED color and the rest of the animals NONRED color.

Work out the inequalities.

How do the colors of animals change?

Let's give each animal a color. An animal $$$i$$$ is RED if $$$B_{i-1}$$$ > $$$A_i$$$. In other words, and animal is red if and only if the previous animal will beat it as king. The animals that are not red are called NONRED for now.

We can assume no two animals are consecutively RED* (*will elaborate more in part 4). Suppose we have 3 animals $$$XYZ$$$ in that order, and $$$Y$$$ is red while $$$X$$$ and $$$Z$$$ are non-red. Suppose $$$X$$$ becomes king and wins $$$Y$$$ but not $$$Z$$$. As such, the final arrangement is $$$YXZ$$$. The claim here is that $$$X$$$ and $$$Z$$$ cannot become RED.

For $$$X$$$, $$$X$$$ beats $$$Y$$$, We have $$$B_X \gt A_Y$$$, but since $$$A_X \gt B_X$$$ and $$$A_Y \gt B_Y$$$, we get that $$$B_Y \lt A_X$$$. As such, $$$X$$$ cannot be RED.

For $$$Z$$$, we have $$$C_X \lt A_Z$$$ (since X lost to Z) and $$$B_X \lt C_X$$$, we hence have $$$B_X \lt A_Z$$$. As such, $$$Z$$$ cannot be RED

Finally for $$$Y$$$, it is possible that it turns from RED to NONRED.

From these we can conclude that RED cannot be created, but can be destroyed.

REDs can only be destroyed at most $$$O(n)$$$ times.

Simulate a lot "uneventful" moves at once.

Consider NONRED positions to be fixed, and the REDs rotate anti-clockwise about them.

After $$$n-1$$$ moves, what do you observe?

Do many sets of $$$n-1$$$ moves at once until a RED is destroyed or when the game ends.

How to find when a RED is destroyed or when the game ends event occurs quickly?

As such, we have the following conclusions:

• REDS are never created only destroyed
• The order of NONREDS will not change unless a RED inserts itself within the sequence
• REDS will never battle REDS (because of * assumption)

Since the number of times REDS can be destroyed is limited, we should exploit that. We define an event as either when a RED is destroyed or when the game ends. Since events can occur at most $$$O(n)$$$ times, we just need to find some way to quickly simulate the moves until the next event.

Let's visualize the moves like this: instead of the RED and NONRED swapping positions, the NONREDs are fixed in position, and the REDs move around anticlockwise.

After $$$n-1$$$ moves, every RED moves one space anticlockwise around the belt of NONREDs Then in that case, we just need to check how many sets of $$$n-1$$$ moves is needed until the first event occurs.

For convenience, let's split NONRED into BLUE and GREEN. If a NONRED beats a red in front of it, and it loses to next animal, then it is BLUE. If it wins one more time (and hence the entire game) it is GREEN.

Let's look at the conditions for the events:

1. A RED is destroyed. This occurs when $$$B_{nr} \lt A_{r}$$$ where $$$nr$$$ is any BLUE or GREEN
2. The game ends. This occurs when $$$B_{g} \gt A_{r}$$$ where $$$g$$$ is any GREEN

To find the first how many times the reds need to move anticlockwise, we could maintain a monotonic vector across the belt of NONREDs, and then for each RED, binary search the earliest position where an event occurs.

Finally, when we find the number of sets of $$$n-1$$$ we need to move backwards, we move everything manually, check if the game ends. Then we recompute the color of all animals, and repeat. If no event occurs, then it will repeat infinitely.

The step of finding the number of steps before first event occurs takes $$$O(nlogn)$$$ in total. Since REDs can disappear at most $$$O(n)$$$ times, then the total time complexity is $$$O(n^2logn)$$$.

It's worth noting that the constant factor for this algorithm is small as the number of REDs is $$$0.5n$$$ and binary search is a very fast log. Hence, it passes quite comfortably (author's solution is under 400ms) even though $$$n \leq 6000$$$.

In terms of implementation, we can run the first $$$2n$$$ by brute force just to handle some bad corner cases. In particular, it is mostly to handle the assumption "We can assume no two animals are consecutively RED".

If two animals are consecutively RED, then working out the inequalities will show that the one right before the two REDs should be able to win, and hence the game should end within $$$2n$$$ moves.

#include <bits/stdc++.h>
using namespace std;
const int RED = 0, BLUE = 1, GREEN = 2;
const long long inf = 1e16;
typedef pair<long long, long long> ii;
typedef pair<long long, ii> iii;

long long n;
struct animal{ int a, b, c, id, pos, colour, redHere; };
vector<animal> belt;
vector<animal> arr;

vector<iii> s; ///strictly increasing stack
vector<ii> reds;
void insert(long long b, long long beltPos, long long pos){
	while(!s.empty() && s.back().first >= b) s.pop_back();
	s.push_back(iii(b,ii(beltPos, pos)));
}

long long totalMoves = 0;

void brute(){
	deque<animal> q;
	animal w = arr[0];
	
	for(int i = 1;i < n;i++){
		q.push_back(arr[i]);
	}

	long long count = 1;
	for(int x = 1;;x++){
		if(x > 2*n){
			return;
		}
		
		if(count == 3){
			cout << w.id << " " << x << "\n"; // << "\n" << (int)((clock() - start));
			exit(0);
		}
			
		if(count == 1){
			if(w.b > q.front().a){
				animal y = q.front();
				q.push_back(y);
				q.pop_front();
				count++;
			}
			else{
				q.push_back(w);
				w = q.front();
				q.pop_front();
				count = 1;
			}
		}
		else{
			if(w.c > q.front().a){
				animal y = q.front();
				q.push_back(y);
				q.pop_front();
				count++;
			}
			else{
				q.push_back(w);
				w = q.front();
				q.pop_front();
				count = 1;
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 0;i < n;i++){
		int a, b, c; cin >> a >> b >> c;
		assert(a > b and b < c);
		arr.push_back({a,b,c,i,-1,1,-1});
	}
	
	if(arr[0].a > arr[1].a) swap(arr[0],arr[1]); ///settle first game
	arr.push_back(arr[0]); arr.erase(arr.begin());
	
	brute();
	
	///deciding which are RED
	for(int i = 1;i < n;i++){
		if(arr[i-1].b > arr[i].a){
			arr[i].colour = RED;
		}
	}
	
	///for non-RED, decide if it's BLUE or GREEN
	for(int i = 0;i < n;i++){
		arr[i].pos = i;
		
		if(arr[i].colour == RED) continue;
		int nxt = i+1; if(nxt == n) nxt = 0;
		if(arr[nxt].colour == RED) nxt++; if(nxt == n) nxt = 0;
		
		if(arr[i].c > arr[nxt].a) arr[i].colour = GREEN;
		else arr[i].colour = BLUE;
	}
	
	///get ready the belt
	arr.push_back(arr[0]);
	for(int i = 0;i < n;i++){
		if(arr[i].colour != RED){
			if(arr[i+1].colour == RED){
				arr[i].redHere = arr[i+1].pos;
			}
			belt.push_back(arr[i]);
		}
	}
	
	while(true){
		s.clear(); reds.clear();
		
		///Account for cyclic nature, so every element is inserted once, then later inserted again
		for(int i = 0;i < (int) belt.size();i++){
			animal A = belt[i];
			if(A.colour == BLUE) insert(A.b, A.pos, i);
			else insert(-inf, A.pos, i); ///GREEN trigger events regardless of the value of a
		}
				
		long long minMoves = inf;
		for(int i = 0;i < (int) belt.size();i++){
			animal A = belt[i];
			if(A.colour == BLUE) insert(A.b, A.pos, i);
			else insert(-inf, A.pos, i); ///GREEN trigger events regardless of the value of a
			
			///find the RED at that position, if any
			int red = A.redHere; if(red == -1) continue;
			reds.push_back(ii(red, i));
			
			///find the earliest event that triggers this RED (rightmost non-Red with nonRED.a < RED.b or rightmost GREEN)
			auto early = lower_bound(s.begin(), s.end(), iii(arr[red].a, ii(-1,-1)));
			if(early == s.begin()) continue; ///no event in this case
			early--;
			
			///Number of rotations before event (rotation = N-1 turns)
			long long distance = i - (early->second).second;
			if(distance < 0) distance += (belt.size());
			minMoves = min(distance, minMoves); ///find the minimum number of rotations
		}
		
		///No event can occur, answer last infiinite
		if(minMoves == inf){
			cout << "-1 -1";
			return 0;
		}
		else if(minMoves != 0){ ///Move the reds CCW along the belt
			totalMoves += minMoves * (n-1);
			for(ii R : reds) belt[R.second].redHere = -1;
			for(ii R : reds){
				int pos = R.second;
				pos -= minMoves; if(pos < 0) pos += belt.size();
				belt[pos].redHere = R.first;
			}
		}
		
		ii ans = ii(inf, inf);
		
		///Updating the belt
		for(int i = 0;i < (int) belt.size();i++){
			if(belt[i].redHere == -1) continue;
			animal R = arr[belt[i].redHere];
			if(belt[i].b < R.a){ ///BLUE type event occured
				belt[i].redHere = -1;		
				belt.insert(belt.begin()+(i+1), R); ///inserting in middle of vector
				
				///updating the colours of the surrounding non-REDs
				if(belt[i].c > R.a) belt[i].colour = GREEN;
				else belt[i].colour = BLUE;
				
				int nxt = i+2; if(nxt == (int) belt.size()) nxt = 0;
				if(belt[i+1].c > belt[nxt].a) belt[i+1].colour = GREEN;
				else belt[i+1].colour = BLUE;
			}
			else if(belt[i].colour == GREEN){ ///GREEN type event occured, game ends
				ans = min(ans, ii(totalMoves + R.pos + 2, belt[i].id));
			}
		}
		
		if(ans.first != inf){
			cout << ans.second << " " << ans.first;
			return 0;
		}
	}
}

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define up upper_bound

#define rep(x,start,end) for(auto 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()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct dat{
	int a,b,c;
	int idx;
};

int n;
dat head;
deque<dat> dq;

dat state[6005];
dat trans_belt[6005];
bool green[6005];

int curr;
ll moves=1;

void brute(){
	rep(x,0,1000000){
		if ((curr==0?head.a:(curr==1?head.b:head.c))>dq.front().a){
			dq.pub(dq.front());
			dq.pof();
			curr++;
			if (curr==3){
				cout<<head.idx<<" "<<moves<<endl;
				exit(0);
			}
		}
		else{
			dq.pub(head);
			head=dq.front();
			dq.pof();
			curr=1;
		}
		
		moves++;
		
		if (x>n && curr==1) break;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	
	rep(x,0,n){
		int a,b,c;
		cin>>a>>b>>c;
		
		if (!x) head={a,b,c,x};
		else dq.pub({a,b,c,x});
	}
	
	curr=0;
	brute();
	
	//convert to state
	state[0]=head;
	rep(x,1,n) state[x]=dq[x-1];
	
	while (true){
		//cout<<"move: "<<moves-1<<endl;
		//rep(x,0,n) cout<<state[x].idx<<" "; cout<<endl;
		
		vector<ii> stk;
		
		//find the first instance where state[z].b<state[x].a
		//maintain min stack of state[z].b
		
		//now, we focus on the belt itself
		//there is a case where the red does not convert to a anything but the game ends
		//we need to handle that case carefully!
		//i think lets just insert it into stack with value -1
		//then if it appears its easily handled
		
		memset(green,false,sizeof(green));
		
		int cnt=0;
		
		int pidx=-1;
		rep(x,0,n){
			if (x && state[x-1].b>state[x].a){ //red
				
			}
			else{ //not red
				if (pidx!=-1 && state[pidx].c>state[x].a){
					green[pidx]=true;
				}
				
				pidx=x;
			}
		}
		if (state[pidx].c>state[0].a) green[0]=true;
		
		rep(x,0,n){
			if (x && state[x-1].b>state[x].a){ //red
				
			}
			else{ //not red
				int temp=green[x]?-1:state[x].b;
				
				while (!stk.empty() && stk.back().fi>temp) stk.pob();
				stk.pub(ii(temp,cnt));
				cnt++;
			}
		}
		
		int best=1e9; //shortest distance until red becomes not red
		int cnt2=cnt;
		
		//cout<<"non-reds: "<<cnt<<endl;
		
		rep(x,0,n){
			if (x && state[x-1].b>state[x].a){ //red
				if (stk.front().fi>state[x].a) continue; //it wont become red here
				
				int lo=0,hi=sz(stk),mi;
				while (hi-lo>1){
					mi=hi+lo>>1;
					if (stk[mi].fi<state[x].a) lo=mi;
					else hi=mi;
				}
				
				//cout<<"debug: "<<x<<endl;
				//for (auto &it:stk) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
				//cout<<state[x].a<<endl;
				
				//cout<<"found: "<<pos[stk[hi]]<<endl;
				int dist=cnt2-stk[lo].se;
				//cout<<dist<<endl;
				if (dist<best){
					best=dist;
				}
				
				//cout<<endl;
				
			}
			else{ //not red
				int temp=green[x]?-1:state[x].b;
				
				while (!stk.empty() && stk.back().fi>temp) stk.pob();
				stk.pub(ii(temp,cnt2));
				cnt2++;
			}
		}
		
		//cout<<"number in belt: "<<cnt<<endl;
		//cout<<"d: "<<best<<" "<<idx<<endl;
		
		if (best==1e9){
			cout<<"-1 -1"<<endl;
			return 0;
		}
		
		//we simulate best-1 cycles for the reds
		
		best--;
		
		//cout<<"hmm: "<<endl;
		//cout<<best<<" "<<cnt<<endl;
		if (best>=0){
			moves+=best*(n-1);
			
			//cout<<endl;
			cnt2=0;
			rep(x,0,n){
				if (x && state[x-1].b>state[x].a){ //red
				
				}
				else{ //not red
					trans_belt[cnt2]=state[x];
					cnt2++;
				}
			}
			
			//rep(x,0,cnt2) cout<<trans_belt[x].idx<<" "; cout<<endl;
			
			rep(x,n,0){
				if (x && state[x-1].b>state[x].a){ //red
					
				}
				else{ //not red
					cnt2--;
					//cout<<x<<" "<<(cnt2-best+cnt)%cnt<<endl;
					state[x]=trans_belt[(cnt2-best+cnt)%cnt];
				}
			}
		}
		
		//cout<<cnt<<endl;
		//cout<<"move: "<<moves-1<<endl;
		//rep(x,0,n) cout<<state[x].idx<<" "; cout<<endl;
		
		head=state[0];
		dq.clear();
		rep(x,1,n) dq.pub(state[x]);
		
		curr=1;
		brute();
		
		//convert to state
		state[0]=head;
		rep(x,1,n) state[x]=dq[x-1];
		
		//cout<<"move: "<<moves-1<<endl;
		//rep(x,0,n) cout<<state[x].idx<<" "; cout<<endl;
		//cout<<endl;
		
		//break;
	}
}

We don't even need to build the permutation tree for this question. We will use the $$$Q$$$ array described earlier. Every time we insert a new value, we just need to count the number of values which are set to 0.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << x << endl;

#define rep(x,start,end) for(auto 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()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	ll val=0,lazy=0,num;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		num=e-s+1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val+=lazy;
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
	
	void update(int i,int j,ll k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			
			val=min(l->val,r->val);
			num=(l->val==val?l->num:0)+(r->val==val?r->num:0);
		}
	}
	
	ll query(int i,int j){
		propo();
		
		if (s==i && e==j){
			if (val==0) return num;
			else return 0;
		}
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return l->query(i,m)+r->query(m+1,j);
	}
}*root=new node(0,300005);

int n;
int arr[300005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n){
		int a,b;
		cin>>a>>b;
		arr[a-1]=b;
	}
	
	vector<int> mx={-1},mn={-1};
	ll ans=0;
	
	rep(x,0,n){
		while (mx.back()!=-1 && arr[mx.back()]<arr[x]){
			int temp=mx.back();
			mx.pop_back();
			root->update(mx.back()+1,temp,arr[x]-arr[temp]);
		}
		mx.push_back(x);
		
		while (mn.back()!=-1 && arr[mn.back()]>arr[x]){
			int temp=mn.back();
			mn.pop_back();
			root->update(mn.back()+1,temp,arr[temp]-arr[x]);
		}
		mn.push_back(x);
		
		ans+=root->query(0,x);
		
		root->update(0,x,-1);
	}
	
	cout<<ans<<endl;
}

We build the permutation tree and do 2k decomp on the nodes. For each query, we go to a arbitrary node that is contained in the query then using binary lifting, jump to the lowest node that contains the given query. This can also be done by finding the LCA of the left and right endpoints.

Furthermore, when the lowest node that contains the given query is a join node, we still need to binary search again to remove as many left and right endpoints to get the smallest interval.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#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 << " is " << x << endl;

#define rep(x,start,end) for(auto 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()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	ll val=0,lazy=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val+=lazy;
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
	
	void update(int i,int j,ll k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=min(l->val,r->val);
		}
	}
	
	ll query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return min(l->query(i,m),r->query(m+1,j));
	}
};

int n,q;
int arr[100005];
ii range[200005];
ii span[200005];
vector<int> children[200005];
int parent[200005];
int typ[200005];
int idx; //new index to assign to nodes

ii get_range(ii i,ii j){
	return ii(min(i.fi,j.fi),max(i.se,j.se));
}

void add_edge(int u,int v){ //u is parent of v
	parent[v]=u;
	children[u].push_back(v);
}

bool adj(int i,int j){
	return range[i].se==range[j].fi-1;
}

int length(int i){
	return range[i].se-range[i].fi+1;
}

void build(){
	idx=n;
	memset(parent,-1,sizeof(parent));
	
	node *root=new node(0,100005);
	vector<int> mx={-1},mn={-1}; //stacks for max and min
	
	vector<int> nodes; //stack of cut and join nodes
	
	rep(x,0,n){
		//update Q values
		while (mx.back()!=-1 && arr[mx.back()]<arr[x]){
			int temp=mx.back();
			mx.pop_back();
			root->update(mx.back()+1,temp,arr[x]-arr[temp]);
		}
		mx.push_back(x);
		
		while (mn.back()!=-1 && arr[mn.back()]>arr[x]){
			int temp=mn.back();
			mn.pop_back();
			root->update(mn.back()+1,temp,arr[temp]-arr[x]);
		}
		mn.push_back(x);
		
		//handle stack updates
		range[x]=ii(arr[x],arr[x]);
		span[x]=ii(x,x);
		int curr=x;
		
		while (true){
			if (!nodes.empty() && (adj(nodes.back(),curr) || adj(curr,nodes.back()))){
				if ((adj(nodes.back(),curr) && typ[nodes.back()]==1)||
				  (adj(curr,nodes.back()) && typ[nodes.back()]==2)){
					add_edge(nodes.back(),curr);
					
					range[nodes.back()]=get_range(range[nodes.back()],range[curr]);
					span[nodes.back()]=get_range(span[nodes.back()],span[curr]);
					
					curr=nodes.back();
					nodes.pop_back();
				}
				else{ //make a new join node
					typ[idx]=(adj(nodes.back(),curr) ? 1:2);
					add_edge(idx,nodes.back());
					add_edge(idx,curr);
					
					range[idx]=get_range(range[nodes.back()],range[curr]);
					span[idx]=get_range(span[nodes.back()],span[curr]);
					
					nodes.pop_back();
					curr=idx++;
				}
			}
			else if (x-(length(curr)-1) && root->query(0,x-length(curr))==0){
				int len=length(curr);
				ii r=range[curr];
				ii s=span[curr];
				
				add_edge(idx,curr);
				
				do{
					len+=length(nodes.back());
					r=get_range(r,range[nodes.back()]);
					s=get_range(s,span[nodes.back()]);
					
					add_edge(idx,nodes.back());
					
					nodes.pop_back();
				} while (r.se-r.fi+1!=len);
				
				reverse(all(children[idx]));
				range[idx]=r;
				span[idx]=s;
				curr=idx++;
			}
			else{
				break;
			}
		}
		
		nodes.push_back(curr);
		root->update(0,x,-1);
	}
}

int tkd[200005][20];

void dfs(int i){
	for (auto &it:children[i]){
		int curr=tkd[it][0]=i;
		for (int x=0;curr!=-1;x++){
			curr=tkd[it][x+1]=tkd[curr][x];
		}
		
		dfs(it);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x];
	
	build();
	
	memset(tkd,-1,sizeof(tkd));
	rep(x,0,idx){
		if (parent[x]==-1) dfs(x);
	}
	
	cin>>q;
	int a,b;
	while (q--){
		cin>>a>>b;
		
		if (a==b){
			cout<<a<<" "<<b<<endl;
			continue;
		}
		
		a--,b--;
		int curr=a;
		
		rep(x,20,0){
			if (tkd[curr][x]!=-1 && span[tkd[curr][x]].se<b) curr=tkd[curr][x];
		}
		
		curr=tkd[curr][0];
		if (typ[curr]==0) cout<<span[curr].fi+1<<" "<<span[curr].se+1<<endl;
		else{
			int lo=-1,hi=sz(children[curr]);
			
			rep(x,20,0){
				if (lo+(1<<x)<sz(children[curr]) && span[children[curr][lo+(1<<x)]].se<a) lo+=(1<<x);
				if (0<=hi-(1<<x) && b<span[children[curr][hi-(1<<x)]].fi) hi-=(1<<x);
			}
			
			cout<<span[children[curr][lo+1]].fi+1<<" "<<span[children[curr][hi-1]].se+1<<endl;
		}
	}
	
}