In the first stage of most solutions, they are using $$$n$$$ splitting the minerals into $$$2$$$ piles, such that each pair of minerals have $$$1$$$ mineral in each pile.

However, they do not obtain any additional information from this stage. Let's fix that!

This is my first optimization. Let us randomly shuffle the minerals. Consider the minerals only in $$$[1,n]$$$, we will split them into $$$2$$$ piles $$$A$$$,$$$B$$$ and $$$C$$$ such that for minerals who has $$$2$$$ occurances in $$$[1,n]$$$, one of them in pile $$$A$$$ and $$$B$$$. While for minerals who has only $$$1$$$ occurance in $$$[1,n]$$$, they are in pile $$$C$$$. We can find these piles in $$$2n-|A|$$$ queries. However, we only need to do our "matching" on piles $$$A$$$ and $$$B$$$ now. Then we match $$$C$$$ with the corresponding $$$C$$$ of $$$[n+1,2n]$$$. The expected size of $$$|C|$$$ is $$$\frac{1}{2} n$$$. So with an additional $$$\frac{3}{2} n$$$ queries, we split our matchings into sizes $$$\frac{1}{4}n$$$,$$$\frac{1}{4}n$$$,$$$\frac{1}{2}n$$$. This saves around $$$\frac{3}{4} n$$$ queries.

The second optimization is to realize that if we order $$$A$$$ and $$$B$$$ by their index, then we should expect that the first $$$\frac{1}{4}$$$ of $$$B$$$ should only correspond to the first $$$\frac{3}{4}$$$ of $$$A$$$. So this gives us an optimization. Let us label the first and last $$$\frac{1}{4}$$$ $$$A$$$ with the same labels in our matching. For example, with $$$n=8$$$, we label them $$$[1,2,3,4,5,6,1,2]$$$. If we are lucky, one of the label points to a mineral in the first $$$\frac{1}{4}$$$ of $$$B$$$ and we save $$$2$$$ queries whenever this happens. I estimate this happens $$$\frac{1}{12} n$$$ of the time, so we save about $$$\frac{1}{6} n$$$ queries from this optimization.

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n=50000;
int arr[100005];

signed main(){
	for (int x=0;x<2*n;x++) arr[x]=x+1;
	shuffle(arr,arr+2*n,rng);
	
	cout<<n<<endl;
	for (int x=0;x<n;x++) cout<<arr[2*x]<<" "<<arr[2*x+1]<<endl;
}

struct node{
	int BUF=1000005;
	int val[2000010],lazy[2000010];
	
	void get(int i){ val[i]=max(val[i<<1],val[i<<1|1])+lazy[i]; }
	
	void update(int i,int j,int k){ //[i,j]
		i+=BUF-1,j+=BUF+1; //(i,j)
		while (i|j){
			if (j-i>1){
				if (~i&1) val[i^1]+=k,lazy[i^1]+=k;
				if (j&1) val[j^1]+=k,lazy[j^1]+=k;
			}
			i>>=1,j>>=1;
			get(i),get(j);
		}
	}
	
	int query(int i,int j){ //[i,j]
		i+=BUF-1,j+=BUF+1; //(i,j)
		int resl=-1e18,resr=-1e18;
		while (i|j){
			if (j-i>1){
				if (~i&1) resl=max(resl,val[i^1]);
				if (j&1) resr=max(resr,val[j^1]);
			}
			i>>=1,j>>=1;
			resl+=lazy[i],resr+=lazy[j];
		}
		return max(resl,resr);
	}
};

#include "testlib.h"

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

int main(int argc, char* argv[]){
    registerGen(argc, argv, 1);
	
	int n=atoi(argv[1]),q=atoi(argv[2]),wn=atoi(argv[3]),qt=atoi(argv[4]);
	
	vector<pair<int,int> > edges;
	for (int x=1;x<n;x++) edges.push_back({rnd.wnext(x,wn),x});
	
	shuffle(edges.begin(),edges.end());
	vector<int> perm(n);
	iota(perm.begin(),perm.end(),1);
	shuffle(perm.begin(),perm.end());
	
	cout<<n<<" "<<q<<endl;
	for (auto [a,b]:edges){
		if (rnd.next(2)) cout<<perm[a]<<" "<<perm[b]<<endl;
		else cout<<perm[b]<<" "<<perm[a]<<endl;
	}
	
	for (int x=0;x<q;x++){
		int a=rnd.next(1,qt);
		if (a==1){
			int u=rnd.next(1,n),v=rnd.next(1,n),w=rnd.next(1,1000000000);
			cout<<a<<" "<<u<<" "<<v<<" "<<w<<endl;
		}
		else if (a==2){
			int u=rnd.next(1,n),v=rnd.next(1,n);
			cout<<a<<" "<<u<<" "<<v<<endl;
		}
		else if (a==3){
			int u=rnd.next(1,n),w=rnd.next(1,1000000000);
			cout<<a<<" "<<u<<" "<<w<<endl;
		}
		else{
			int u=rnd.next(1,n);
			cout<<a<<" "<<u<<endl;
		}
	}
}

#include "testlib.h"

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

int main(int argc, char* argv[]){
    registerGen(argc, argv, 1);
	
	int n=atoi(argv[1]),q=atoi(argv[2]),k=atoi(argv[3]),qt=atoi(argv[4]);
	
	vector<pair<int,int> > edges;
	queue<int> qu;
	qu.push(0),qu.push(0);
	int IDX=0;
	
	while (IDX<n-1){
		int u=qu.front();
		qu.pop();
		
		for (int x=0;x<k;x++){
			edges.push_back({u,++IDX});
			u=IDX;
			if (IDX==n-1) break;
		}
		qu.push(IDX),qu.push(IDX);
	}
	
	shuffle(edges.begin(),edges.end());
	vector<int> perm(n);
	iota(perm.begin(),perm.end(),1);
	shuffle(perm.begin()+1,perm.end()); //keep 1 as the root
	
	cout<<n<<" "<<q<<endl;
	for (auto [a,b]:edges){
		if (rnd.next(2)) cout<<perm[a]<<" "<<perm[b]<<endl;
		else cout<<perm[b]<<" "<<perm[a]<<endl;
	}
	
	for (int x=0;x<q;x++){
		int a=rnd.next(1,qt);
		if (a==1){
			int u=rnd.next(1,n),v=rnd.next(1,n),w=rnd.next(1,1000000000);
			cout<<a<<" "<<u<<" "<<v<<" "<<w<<endl;
		}
		else if (a==2){
			int u=rnd.next(1,n),v=rnd.next(1,n);
			cout<<a<<" "<<u<<" "<<v<<endl;
		}
		else if (a==3){
			int u=rnd.next(1,n),w=rnd.next(1,1000000000);
			cout<<a<<" "<<u<<" "<<w<<endl;
		}
		else{
			int u=rnd.next(1,n);
			cout<<a<<" "<<u<<endl;
		}
	}
}

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

struct node{
	int BUF=1000005;
	int val[2000010],lazy[2000010];
	
	void get(int i){ val[i]=max(val[i<<1],val[i<<1|1])+lazy[i]; }
	
	void update(int i,int j,int k){ //[i,j]
		i+=BUF-1,j+=BUF+1; //(i,j)
		while (i|j){
			if (j-i>1){
				if (~i&1) val[i^1]+=k,lazy[i^1]+=k;
				if (j&1) val[j^1]+=k,lazy[j^1]+=k;
			}
			i>>=1,j>>=1;
			get(i),get(j);
		}
	}
	
	int query(int i,int j){ //[i,j]
		i+=BUF-1,j+=BUF+1; //(i,j)
		int resl=-1e18,resr=-1e18;
		while (i|j){
			if (j-i>1){
				if (~i&1) resl=max(resl,val[i^1]);
				if (j&1) resr=max(resr,val[j^1]);
			}
			i>>=1,j>>=1;
			resl+=lazy[i],resr+=lazy[j];
		}
		return max(resl,resr);
	}
} root;

int n,q;
vector<int> al[1000005];

int ss[1000005];
int in[1000005];
int out[1000005];
int d[1000005];
int pp[1000005];
int hp[1000005];

int _TIME=0;

void dfs_ss(int i,int p){
	ss[i]=1;
	for (auto &it:al[i]){
		if (it==p) continue;
		dfs_ss(it,i);
		ss[i]+=ss[it];
		if (al[i][0]==p || ss[al[i][0]]<ss[it]) swap(al[i][0],it);
	}
}

void dfs_hld(int i,int p){
	in[i]=++_TIME;
	
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		if (it==al[i][0]) hp[it]=hp[i];
		else hp[it]=it;
		pp[it]=i;
		
		dfs_hld(it,i);
	}
	
	out[i]=_TIME;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	
	int a,b,c;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	dfs_ss(1,-1);
	hp[1]=1;
	dfs_hld(1,-1);
	
	while (q--){
		cin>>a;
		
		if (a==1){
			cin>>a>>b>>c;
			while (hp[a]!=hp[b]){
				if (d[hp[a]]<d[hp[b]]) swap(a,b);
				root.update(in[hp[a]],in[a],c);
				a=pp[hp[a]];
			}
			if (d[a]>d[b]) swap(a,b);
			root.update(in[a],in[b],c);
		}
		else if (a==2){
			cin>>a>>b;
			int res=-1e18;
			while (hp[a]!=hp[b]){
				if (d[hp[a]]<d[hp[b]]) swap(a,b);
				res=max(res,root.query(in[hp[a]],in[a]));
				a=pp[hp[a]];
			}
			if (d[a]>d[b]) swap(a,b);
			res=max(res,root.query(in[a],in[b]));
			
			cout<<res<<endl;
		}
		else if (a==3){
			cin>>a>>c;
			root.update(in[a],out[a],c);
		}
		else{
			cin>>a;
			cout<<root.query(in[a],out[a])<<endl;
		}
	}
}

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int __dat[8000005];
int *ptr=__dat;

struct node{
	int BUF;
	int *val,*lazy;
	
	node(){}
	node(int n){
		n++;
		
		BUF=n;
		val=ptr; ptr+=n<<1;
		lazy=ptr; ptr+=n<<1;
	}
	
	void get(int i){ val[i]=max(val[i<<1],val[i<<1|1])+lazy[i]; }
	
	void update(int i,int j,int k){
		i+=BUF-1,j+=BUF+1; //(i,j)
		while (i|j){
			if (j-i>1){
				if (~i&1) val[i^1]+=k,lazy[i^1]+=k;
				if (j&1) val[j^1]+=k,lazy[j^1]+=k;
			}
			i>>=1,j>>=1;
			get(i),get(j);
		}
	}
	
	int query(int i,int j){
		i+=BUF-1,j+=BUF+1; //(i,j)
		int resl=-1e18,resr=-1e18;
		while (i|j){
			if (j-i>1){
				if (~i&1) resl=max(resl,val[i^1]);
				if (j&1) resr=max(resr,val[j^1]);
			}
			i>>=1,j>>=1;
			resl+=lazy[i],resr+=lazy[j];
		}
		return max(resl,resr);
	}
};

int n,q;
vector<int> al[1000005];

int ss[1000005];
int in[1000005];
int d[1000005];
int pp[1000005];
int hp[1000005];
int num[1000005];

void dfs_ss(int i,int p){
	ss[i]=1;
	for (auto &it:al[i]){
		if (it==p) continue;
		dfs_ss(it,i);
		ss[i]+=ss[it];
		if (al[i][0]==p || ss[al[i][0]]<ss[it]) swap(al[i][0],it);
	}
}

void dfs_hld(int i,int p){
	num[hp[i]]++;
	
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		if (it==al[i][0]) hp[it]=hp[i],in[it]=in[i]+1;
		else hp[it]=it;
		pp[it]=i;
		
		dfs_hld(it,i);
	}
}

node root[1000005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	
	int a,b,c;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	dfs_ss(1,-1);
	hp[1]=1;
	dfs_hld(1,-1);
	
	rep(x,1,n+1) if (hp[x]==x) root[x]=node(num[x]);
	
	while (q--){
		cin>>a;
		
		if (a==1){
			cin>>a>>b>>c;
			while (hp[a]!=hp[b]){
				if (d[hp[a]]<d[hp[b]]) swap(a,b);
				root[hp[a]].update(0,in[a],c);
				a=pp[hp[a]];
			}
			if (d[a]>d[b]) swap(a,b);
			root[hp[a]].update(in[a],in[b],c);
		}
		else{
			cin>>a>>b;
			int res=-1e18;
			while (hp[a]!=hp[b]){
				if (d[hp[a]]<d[hp[b]]) swap(a,b);
				res=max(res,root[hp[a]].query(0,in[a]));
				a=pp[hp[a]];
			}
			if (d[a]>d[b]) swap(a,b);
			res=max(res,root[hp[a]].query(in[a],in[b]));
			
			cout<<res<<endl;
		}
	}
}

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

using S=int;
using F=int;

S op(S l,S r){ return max(l,r); }
S e(){ return 0; }
S mapping(F l,S r){ return l+r; }
F composition(F l,F r){ return l+r; }
F id(){ return 0; }
using segtree=lazy_segtree<S, op, e, F, mapping, composition, id>;

int n,q;
vector<int> al[1000005];

int ss[1000005];
int in[1000005];
int d[1000005];
int pp[1000005];
int hp[1000005];
int num[1000005];

void dfs_ss(int i,int p){
	ss[i]=1;
	for (auto &it:al[i]){
		if (it==p) continue;
		dfs_ss(it,i);
		ss[i]+=ss[it];
		if (al[i][0]==p || ss[al[i][0]]<ss[it]) swap(al[i][0],it);
	}
}

void dfs_hld(int i,int p){
	num[hp[i]]++;
	
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		if (it==al[i][0]) hp[it]=hp[i],in[it]=in[i]+1;
		else hp[it]=it;
		pp[it]=i;
		
		dfs_hld(it,i);
	}
}

segtree root[1000005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	
	int a,b,c;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	dfs_ss(1,-1);
	hp[1]=1;
	dfs_hld(1,-1);
	
	rep(x,1,n+1) if (hp[x]==x) root[x]=segtree(num[x]);
	
	while (q--){
		cin>>a;
		
		if (a==1){
			cin>>a>>b>>c;
			while (hp[a]!=hp[b]){
				if (d[hp[a]]<d[hp[b]]) swap(a,b);
				root[hp[a]].apply(0,in[a]+1,c);
				a=pp[hp[a]];
			}
			if (d[a]>d[b]) swap(a,b);
			root[hp[a]].apply(in[a],in[b]+1,c);
		}
		else{
			cin>>a>>b;
			int res=-1e18;
			while (hp[a]!=hp[b]){
				if (d[hp[a]]<d[hp[b]]) swap(a,b);
				res=max(res,root[hp[a]].prod(0,in[a]+1));
				a=pp[hp[a]];
			}
			if (d[a]>d[b]) swap(a,b);
			res=max(res,root[hp[a]].prod(in[a],in[b]+1));
			
			cout<<res<<endl;
		}
	}
}

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

struct node{
	node *p=nullptr; bool head=true;
	node *l=nullptr,*r=nullptr; //only store real children
	int val=0,mx=0,lazy=0;
	
	node (node *_p){
		p=_p;
	}
	
	bool dir(){
		return this==p->l;
	}
	
	void propo(){
		if (lazy==0) return;
		
		val+=lazy;
		mx+=lazy;
		if (l) l->lazy+=lazy;
		if (r) r->lazy+=lazy;
		lazy=0;
	}
	
	void upd(){
		mx=max({
			val,
			l==nullptr?0:l->mx+l->lazy,
			r==nullptr?0:r->mx+r->lazy
		});
	}
};

void rotate(node *u){
	node *par=u->p;
	bool dir=u->dir();
	
	par->propo();
	u->propo();
	
	u->p=par->p;
	if (!par->head){
		if (par->dir()) par->p->l=u;
		else par->p->r=u;
	}
	swap(u->head,par->head);
	
	if (dir){
		node *child=u->r;
		par->l=child;
		if (child) child->p=par;
		
		u->r=par;
		par->p=u;
	}
	else{
		node *child=u->l;
		par->r=child;
		if (child) child->p=par;
		u->l=par;
		par->p=u;
	}
	
	par->upd();
	u->upd();
}

void splay(node *u){
	while (!u->head){
		if (u->p->head){ //almost root
			rotate(u);
		}
		else if (u->dir()==u->p->dir()){
			rotate(u->p);
			rotate(u);
		}
		else{
			rotate(u);
			rotate(u);
		}
	}
	u->propo();
}

node* access(node *u){
	splay(u);
	if (u->r!=nullptr){
		u->r->head=true;
		u->r=nullptr;
		u->upd();
	}
	while (u->p){
		node *par=u->p;
		splay(par);
		if (par->r) par->r->head=true;
		u->head=false;
		par->r=u;
		par->upd();
		u=par;
	}
	
	return u;
}

int n,q;
vector<int> al[1000005];
int d[1000005];
node *root[1000005];

void dfs(int i,int p){
	root[i]=new node(p==-1?nullptr:root[p]);
	for (auto it:al[i]){
		if (it==p) continue;
		d[it]=d[i]+1;
		dfs(it,i);
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	
	int a,b,c;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	dfs(1,-1);
	
	while (q--){
		cin>>a;
		
		if (a==1){
			cin>>a>>b>>c;
			
			if (d[a]>d[b]) swap(a,b);
			access(root[a]);
			node *temp=access(root[b]);
			splay(root[a]);
			
			if (root[a]->p) root[a]->lazy+=c;
			temp->val+=c;
			if (temp->r) temp->r->lazy+=c;
			temp->upd();
		}
		else{
			cin>>a>>b;
			
			if (d[a]>d[b]) swap(a,b);
			access(root[a]);
			node *temp=access(root[b]);
			splay(root[a]);
			
			int ans=max({
				root[a]->p?(root[a]->mx)+(root[a]->lazy):0,
				temp->val+temp->lazy,
				temp->r?temp->r->mx+temp->r->lazy+temp->lazy:0
			});
			
			cout<<ans<<endl;
		}
	}
}

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

struct node{
	node *p=nullptr;
	node *l=nullptr,*r=nullptr; //only store real children
	int val=0,mx=0,lazy=0;
	
	node (node *_p){
		p=_p;
	}
	
	bool dir(){
		return this==p->l;
	}
	
	void propo(){
		if (lazy==0) return;
		
		val+=lazy;
		mx+=lazy;
		if (l) l->lazy+=lazy;
		if (r) r->lazy+=lazy;
		lazy=0;
	}
	
	void upd(){
		mx=max({
			val,
			l==nullptr?0:l->mx+l->lazy,
			r==nullptr?0:r->mx+r->lazy
		});
	}
};

void rotate(node *u){
	node *par=u->p;
	bool dir=u->dir();
	
	par->propo();
	u->propo();
	
	u->p=par->p;
	if (par->p){
		if (par->dir()) par->p->l=u;
		else par->p->r=u;
	}
	
	if (dir){
		node *child=u->r;
		par->l=child;
		if (child) child->p=par;
		
		u->r=par;
		par->p=u;
	}
	else{
		node *child=u->l;
		par->r=child;
		if (child) child->p=par;
		u->l=par;
		par->p=u;
	}
	
	par->upd();
	u->upd();
}

void splay(node *u){
	while (u->p){
		if (u->p->p==nullptr){ //almost root
			rotate(u);
		}
		else if (u->dir()==u->p->dir()){
			rotate(u->p);
			rotate(u);
		}
		else{
			rotate(u);
			rotate(u);
		}
	}
	u->propo();
}

int n,q;
vector<int> al[1000005];

int ss[1000005];
int d[1000005];
int pp[1000005];
int hp[1000005];
int num[1000005];
node* root[1000005];

void dfs_ss(int i,int p){
	ss[i]=1;
	for (auto &it:al[i]){
		if (it==p) continue;
		dfs_ss(it,i);
		ss[i]+=ss[it];
		if (al[i][0]==p || ss[al[i][0]]<ss[it]) swap(al[i][0],it);
	}
}

void dfs_hld(int i,int p){
	num[hp[i]]++;
	
	if (hp[i]==i) root[i]=new node(nullptr);
	else root[i]=new node(root[p]);
	
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		if (it==al[i][0]) hp[it]=hp[i];
		else hp[it]=it;
		pp[it]=i;
		
		dfs_hld(it,i);
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	
	int a,b,c;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	dfs_ss(1,-1);
	hp[1]=1;
	dfs_hld(1,-1);
	
	while (q--){
		cin>>a;
		
		if (a==1){
			cin>>a>>b>>c;
			while (hp[a]!=hp[b]){
				if (d[hp[a]]<d[hp[b]]) swap(a,b);
				splay(root[a]);
				root[a]->val+=c;
				if (root[a]->l) root[a]->l->lazy+=c;
				root[a]->upd();
				a=pp[hp[a]];
			}
			if (d[a]>d[b]) swap(a,b);
			if (a==b){
				splay(root[a]);
				root[a]->val+=c;
				root[a]->upd();
			}
			else{
				splay(root[b]);
				splay(root[a]);
				if (root[b]->p!=root[a]) rotate(root[b]);
				
				if (root[b]->l) root[b]->l->lazy+=c;
				root[a]->val+=c;
				root[b]->val+=c;
				
				root[b]->upd();
				root[a]->upd();
			}
		}
		else{
			cin>>a>>b;
			int res=-1e18;
			
			while (hp[a]!=hp[b]){
				if (d[hp[a]]<d[hp[b]]) swap(a,b);
				splay(root[a]);
				res=max(res,root[a]->val+root[a]->lazy);
				if (root[a]->l) res=max(res,root[a]->l->mx+root[a]->l->lazy+root[a]->lazy);
				a=pp[hp[a]];
			}
			if (d[a]>d[b]) swap(a,b);
			if (a==b){
				splay(root[a]);
				res=max(res,root[a]->val+root[a]->lazy);
			}
			else{
				splay(root[b]);
				splay(root[a]);
				if (root[b]->p!=root[a]) rotate(root[b]);
				res=max(res,root[a]->val+root[a]->lazy);
				res=max(res,root[b]->val+root[a]->lazy+root[b]->lazy);
				if (root[b]->l) res=max(res,root[b]->l->mx+root[a]->lazy+root[b]->lazy+root[b]->l->lazy);
			}
			
			cout<<res<<endl;
		}
	}
}

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n,q;
vector<int> al[1000005];

int ss[1000005];
int pp[1000005];
int hp[1000005];

int ss2[1000005]; //size of other childs
vector<int> chain[1000005];

void dfs_ss(int i,int p){
	ss[i]=1;
	for (auto &it:al[i]){
		if (it==p) continue;
		dfs_ss(it,i);
		ss[i]+=ss[it];
		if (al[i][0]==p || ss[al[i][0]]<ss[it]) swap(al[i][0],it);
	}
}

int TIME=0;
int in[1000005];

void dfs_hld(int i,int p){
	in[i]=TIME++;
	
	ss2[i]=1;
	chain[hp[i]].pub(i);
	
	for (auto it:al[i]){
		if (it==p) continue;
		
		if (it==al[i][0]) hp[it]=hp[i];
		else hp[it]=it;
		pp[it]=i;
		
		dfs_hld(it,i);
		if (hp[it]!=hp[i]) ss2[i]+=ss[it];
	}
}

int d[1000005];
int hd[1000005];
int par[1000005];
int childs[1000005][2];

int dfs_chain(int i,int l,int r,int p,int depth,int hdepth){
	int tot=0;
	rep(x,l,r+1) tot+=ss2[chain[i][x]];
	
	int curr=0;
	rep(x,l,r+1){
		curr+=ss2[chain[i][x]];
		if (curr>=(tot+1)/2){ //centroid
			int u=chain[i][x];
			d[u]=depth;
			hd[u]=hdepth;
			par[u]=p;
			if (l!=x) childs[u][0]=dfs_chain(i,l,x-1,u,depth+1,hdepth);
			if (r!=x) childs[u][1]=dfs_chain(i,x+1,r,u,depth+1,hdepth);
			for (auto it:al[u]) if (hp[it]!=hp[u] && it!=pp[u]){
				dfs_chain(it,0,sz(chain[it])-1,u,depth+1,depth+1);
			}
			return u;
		}
	}
}

int lazy[1000005];
int val[1000005];
int mx[1000005];

void upd(int i){
	mx[i]=val[i];
	rep(z,0,2) if (childs[i][z]!=-1) mx[i]=max(mx[i],mx[childs[i][z]]);
	mx[i]+=lazy[i];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	
	int a,b,c;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	dfs_ss(1,-1);
	hp[1]=1;
	dfs_hld(1,-1);
	
	memset(par,-1,sizeof(par));
	memset(childs,-1,sizeof(childs));
	dfs_chain(1,0,sz(chain[1])-1,-1,0,0);
	
	while (q--){
		cin>>a;
		
		if (a==1){
			cin>>a>>b>>c;
			
			while (hp[a]!=hp[b]){
				if (hd[a]<hd[b]) swap(a,b);
				
				int oa=a;
				while (hp[a]==hp[oa]){
					if (in[a]<=in[oa]){
						val[a]+=c;
						if (childs[a][0]!=-1){
							lazy[childs[a][0]]+=c;
							mx[childs[a][0]]+=c;
						}
					}
					upd(a);
					a=par[a];
				}
			}
			
			if (in[a]>in[b]) swap(a,b);
			int oa=a,ob=b;
			while (a!=b){
				int md=max(d[a],d[b]);
				if (d[a]>=md){
					if (in[oa]<=in[a]){
						val[a]+=c;
						if (childs[a][1]!=-1){
							lazy[childs[a][1]]+=c;
							mx[childs[a][1]]+=c;
						}
					}
					upd(a);
					a=par[a];
				}
				if (d[b]>=md){
					if (in[b]<=in[ob]){
						val[b]+=c;
						if (childs[b][0]!=-1){
							lazy[childs[b][0]]+=c;
							mx[childs[b][0]]+=c;
						}
					}
					upd(b);
					b=par[b];
				}
			}
			
			val[a]+=c;
			while (a!=-1 && hp[oa]==hp[a]){
				upd(a);
				a=par[a];
			}
		}
		else{
			cin>>a>>b;
			
			int ans=0;
			while (hp[a]!=hp[b]){
				if (hd[a]<hd[b]) swap(a,b);
				
				int curr=0;
				int oa=a;
				while (hp[a]==hp[oa]){
					if (in[a]<=in[oa]){
						curr=max(curr,val[a]);
						if (childs[a][0]!=-1) curr=max(curr,mx[childs[a][0]]);
					}
					curr+=lazy[a];
					a=par[a];
				}
				ans=max(ans,curr);
			}
			
			if (in[a]>in[b]) swap(a,b);
			int oa=a,ob=b;
			int currl=0,currr=0;
			while (a!=b){
				int md=max(d[a],d[b]);
				if (d[a]>=md){
					if (in[oa]<=in[a]){
						currl=max(currl,val[a]);
						if (childs[a][1]!=-1) currl=max(currl,mx[childs[a][1]]);
					}
					currl+=lazy[a];
					a=par[a];
				}
				if (d[b]>=md){
					if (in[b]<=in[ob]){
						currr=max(currr,val[b]);
						if (childs[b][0]!=-1) currr=max(currr,mx[childs[b][0]]);
					}
					currr+=lazy[b];
					b=par[b];
				}
			}
			
			currl=max({currl,currr,val[a]});
			
			while (a!=-1 && hp[oa]==hp[a]){
				currl+=lazy[a];
				a=par[a];
			}
			
			ans=max(ans,currl);
			cout<<ans<<endl;
		}
	}
}

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n,q;
vector<int> al[2000005];

int ss[2000005];
int hp[2000005];

int ss2[2000005]; //size of other childs
vector<int> chain[2000005];

int FAKE_IDX;
int rp[2000005]; //real vertex for fake vertices

void dfs_ss(int i,int p){
	if (p!=-1 && i<=n){
		for (auto &it:al[i]) if (it==p || it==rp[p]) swap(it,al[i].back());
		al[i].pob();
	}
	
	int curr=i;
	while (sz(al[curr])>2){
		swap(al[curr],al[FAKE_IDX]);
		al[curr]={al[FAKE_IDX].back(),FAKE_IDX};
		al[FAKE_IDX].pob();
		rp[FAKE_IDX]=i;
		curr=FAKE_IDX;
		FAKE_IDX++;
	}
	
	ss[i]=1;
	for (auto &it:al[i]){
		dfs_ss(it,i);
		ss[i]+=ss[it];
		if (ss[al[i][0]]<ss[it]) swap(al[i][0],it);
	}
}

int TIME=0;
int in[2000005];

void dfs_hld(int i,int p){
	in[i]=TIME++;
	
	ss2[i]=1;
	chain[hp[i]].pub(i);
	
	for (auto it:al[i]){
		if (it==al[i][0]) hp[it]=hp[i];
		else hp[it]=it;
		
		dfs_hld(it,i);
		if (hp[it]!=hp[i]) ss2[i]+=ss[it];
	}
}

int d[2000005];
int hd[2000005];
int par[2000005];
int childs[2000005][3]; //(left,right,fake)

int dfs_chain(int i,int l,int r,int p,int depth,int hdepth){
	int tot=0;
	rep(x,l,r+1) tot+=ss2[chain[i][x]];
	
	int curr=0;
	rep(x,l,r+1){
		curr+=ss2[chain[i][x]];
		if (curr>=(tot+1)/2){ //centroid
			int u=chain[i][x];
			d[u]=depth;
			hd[u]=hdepth;
			par[u]=p;
			if (l!=x) childs[u][0]=dfs_chain(i,l,x-1,u,depth+1,hdepth);
			if (r!=x) childs[u][1]=dfs_chain(i,x+1,r,u,depth+1,hdepth);
			for (auto it:al[u]) if (hp[it]!=hp[u]){
				childs[u][2]=dfs_chain(it,0,sz(chain[it])-1,u,depth+1,depth+1);
			}
			return u;
		}
	}
}

int lazy1[2000005]; //only propogate on real tree
int lazy2[2000005]; //propogate on both real and fake tree
int val[2000005];
ii mx[2000005]; //(real,fake)

void upd(int i){
	mx[i]={val[i],0};
	rep(z,0,3){
		if (childs[i][z]!=-1){
			if (z!=2) mx[i].fi=max(mx[i].fi,mx[childs[i][z]].fi);
			else mx[i].se=max(mx[i].se,mx[childs[i][z]].fi);
			mx[i].se=max(mx[i].se,mx[childs[i][z]].se);
		}
	}
	mx[i].fi+=lazy1[i]+lazy2[i]; mx[i].se+=lazy2[i];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	
	int a,b,c;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	memset(rp,-1,sizeof(rp));
	FAKE_IDX=n+1;
	dfs_ss(1,-1);
	hp[1]=1;
	dfs_hld(1,-1);
	
	memset(par,-1,sizeof(par));
	memset(childs,-1,sizeof(childs));
	dfs_chain(1,0,sz(chain[1])-1,-1,0,0);
	
	// rep(x,1,FAKE_IDX) cout<<hp[x]<<" "; cout<<endl;
	// rep(x,1,FAKE_IDX) cout<<childs[x][0]<<" "; cout<<endl;
	// rep(x,1,FAKE_IDX) cout<<childs[x][1]<<" "; cout<<endl;
	// rep(x,1,FAKE_IDX) cout<<childs[x][2]<<" "; cout<<endl;
	
	while (q--){
		cin>>a;
		
		if (a==1){
			cin>>a>>b>>c;
			
			while (hp[a]!=hp[b]){
				if (hd[a]<hd[b]) swap(a,b);
				
				int oa=a;
				while (hp[a]==hp[oa]){
					if (in[a]<=in[oa]){
						val[a]+=c;
						if (childs[a][0]!=-1){
							lazy1[childs[a][0]]+=c;
							mx[childs[a][0]].fi+=c;
						}
					}
					upd(a);
					a=par[a];
				}
			}
			
			if (in[a]>in[b]) swap(a,b);
			
			if (rp[a]!=-1){ //lca is a fake vertex
				int g=rp[a];
				val[g]+=c;
				while (g!=-1){
					upd(g);
					g=par[g];
				}
			}
			
			int oa=a,ob=b;
			while (a!=b){
				int md=max(d[a],d[b]);
				if (d[a]>=md){
					if (in[oa]<=in[a]){
						val[a]+=c;
						if (childs[a][1]!=-1){
							lazy1[childs[a][1]]+=c;
							mx[childs[a][1]].fi+=c;
						}
					}
					upd(a);
					a=par[a];
				}
				if (d[b]>=md){
					if (in[b]<=in[ob]){
						val[b]+=c;
						if (childs[b][0]!=-1){
							lazy1[childs[b][0]]+=c;
							mx[childs[b][0]].fi+=c;
						}
					}
					upd(b);
					b=par[b];
				}
			}
			
			val[a]+=c;
			while (a!=-1){
				upd(a);
				a=par[a];
			}
		}
		else if (a==2){
			cin>>a>>b;
			
			int ans=0,ansl=0,ansr=0;
			while (hp[a]!=hp[b]){
				if (hd[a]<hd[b]) swap(a,b),swap(ansl,ansr);
				
				int curr=0;
				int oa=a;
				while (hp[a]==hp[oa]){
					if (in[a]<=in[oa]){
						curr=max(curr,val[a]);
						if (childs[a][0]!=-1) curr=max(curr,mx[childs[a][0]].fi);
					}
					curr+=lazy1[a]+lazy2[a];
					ansl+=lazy2[a];
					a=par[a];
				}
				ansl=max(ansl,curr);
			}
			
			if (in[a]>in[b]) swap(a,b),swap(ansl,ansr);
			
			if (rp[a]!=-1){ //lca is a fake vertex
				int g=rp[a],curr=val[rp[a]];
				while (g!=-1){
					if (hp[g]==hp[rp[a]]) curr+=lazy1[g];
					curr+=lazy2[g];
					g=par[g];
				}
				ans=max(ans,curr);
			}
			
			int oa=a,ob=b;
			int currl=0,currr=0;
			while (a!=b){
				int md=max(d[a],d[b]);
				if (d[a]>=md){
					if (in[oa]<=in[a]){
						currl=max(currl,val[a]);
						if (childs[a][1]!=-1) currl=max(currl,mx[childs[a][1]].fi);
					}
					currl+=lazy1[a]+lazy2[a];
					ansl+=lazy2[a];
					a=par[a];
				}
				if (d[b]>=md){
					if (in[b]<=in[ob]){
						currr=max(currr,val[b]);
						if (childs[b][0]!=-1) currr=max(currr,mx[childs[b][0]].fi);
					}
					currr+=lazy1[b]+lazy2[b];
					ansr+=lazy2[b];
					b=par[b];
				}
			}
			
			currl=max({currl,currr,val[a]});
			ansl=max(ansl,ansr);
			
			while (a!=-1){
				if (hp[a]==hp[oa]) currl+=lazy1[a];
				currl+=lazy2[a];
				ansl+=lazy2[a];
				a=par[a];
			}
			
			cout<<max({ans,currl,ansl})<<endl;
		}
		else if (a==3){
			cin>>a>>c;
			
			int oa=a;
			while (a!=-1){
				if (in[oa]<=in[a]){
					val[a]+=c;
					rep(z,1,3) if (childs[a][z]!=-1){ //update both right and light children
						lazy2[childs[a][z]]+=c;
						mx[childs[a][z]].fi+=c;
						mx[childs[a][z]].se+=c;
					}
				}
				upd(a);
				a=par[a];
			}
		}
		else{
			cin>>a;
			
			int oa=a,ans=0,curr=0;
			while (a!=-1){
				if (in[oa]<=in[a]){
					curr=max(curr,val[a]);
					rep(z,1,3) if (childs[a][z]!=-1){
						if (z==1) curr=max(curr,mx[childs[a][z]].fi);
						else ans=max(ans,mx[childs[a][z]].fi);
						ans=max(ans,mx[childs[a][z]].se);
					}
				}
				if (hp[a]==hp[oa]) curr+=lazy1[a];
				curr+=lazy2[a];
				ans+=lazy2[a];
				
				a=par[a];
			}
			
			cout<<max(ans,curr)<<endl;
		}
	}
}

import subprocess

#compile everything
subprocess.run("g++ gen_random.cpp -o bin/gen_random -O2 -std=c++17",shell=True)
subprocess.run("g++ gen_binary.cpp -o bin/gen_binary -O2 -std=c++17",shell=True)

tests=[
	"gen_random 1000000 5000000 0",
	"gen_random 1000000 5000000 -10",
	"gen_random 1000000 5000000 10",
	"gen_binary 1000000 5000000 1",
	"gen_binary 1000000 5000000 5"
]

solutions=[
	"hld_single",
	"hld_many",
	"hld_many_ACL",
	"linkcut",
	"hld_splay",
	"binary_tree",
	"binary_tree2"
]

for i in solutions:
	subprocess.run("g++ {}.cpp -o bin/{} -O2 -std=c++17".format(i,i),shell=True)

print("compilation done")

for test in tests:
	print(test)
	subprocess.run("./bin/{} 2 > in".format(test),shell=True)
	
	for x in range(7):
		print(solutions[x],subprocess.run("time ./bin/{} < in > out".format(solutions[x]),shell=True,capture_output=True).stderr)
	print()

for test in tests:
	print(test)
	subprocess.run("./bin/{} 4 > in".format(test),shell=True)
	
	for x in [0,6]:
		print(solutions[x],subprocess.run("time ./bin/{} < in > out".format(solutions[x]),shell=True,capture_output=True).stderr)
	print()

First, we remove all factors of the polynomial with degree $$$\leq 20$$$. After that, there are $$$3$$$ cases for the remaining polynomial, it is prime, it is square, it is product of two prime polynomials. We can brute force the degrees for all cases and test them, which should run in time.

Consider the solutions of $$$f(x)^{q-1}-1$$$. Any $$$u \in GF(q)$$$ satisfies $$$x^{q-1}=1$$$, so $$$f(x)^{q-1}-1 = \prod\limits_{u \in GF(q) \setminus\{0\}} (f(x)-u)= \prod\limits_{u \in GF(q) \setminus\{0\}} (f(x)+u)$$$

By adding the extra of $$$(f(x)+0)$$$ term on both sides, we easily arrive at $$$f(x)^q-f(x)=\prod\limits_{u \in GF(q)} (f(x)+u)$$$.

Note that $$$GF(q)$$$ has characteristic $$$p$$$.

Consider fully expanding $$$(a_0+a_1+\ldots+a_k)^p$$$. Let us consider how many times $$$a_0^{i_0}a_1^{i_1}\ldots a_k^{i_k}$$$ appears in the final product. It is $$$\frac{p!}{(i_0)!(i_1)!\ldots(i_k)!}$$$. Unless there is $$$i_j=p$$$, the denominator will not be $$$0$$$ and the whole product will be $$$0$$$, otherwise the product is $$$1$$$. Therefore, we have $$$(a_0+a_1+\ldots+a_k)^p = a_0^p + a_1^p + \ldots + a_k^p$$$.

One can see that $$$f(x)^p=(c_0x^0+c_1x^1 + \ldots c_k x^k)^p = c_0x^{0p} + c_1x^{1p}+\ldots +c_kx^{kp}=f(x^p)$$$, since the field has characteristic $$$p$$$. So we have proven that $$$f(x)^p=f(x^q)$$$. By applying $$$x \to x^p$$$ a total of $$$k$$$ times, we see that $$$f(x)^q=f(x^q)$$$ is true.

Let us define the special index $$$s_p$$$ as the index ($$$0$$$-indexed) of the leftmost minimum value of the prefix sum. For example, $$$\texttt{)())(()}$$$ gives us $$$p=[-1,0,-1,-2,-1,0,-1]$$$, $$$s_p=3$$$. By definition the $$$s_p$$$ is the unique index such that $$$p_i > p_{s_p}$$$ if $$$i<s_p$$$ and $$$p_{s_p} \leq p_i$$$ if $$$s_p<i$$$.

Claim: when we perform a right rotation on the string, the special index will be updated like $$$s_p \gets (s_p+1) \% (2n+1)$$$. Loosely, the special index shifts along with the string.

Let us consider that currently our prefix sum is $$$p=[p_1,p_2,\ldots,p_k]$$$. After a single right rotation, it will become $$$p'=[0+(p_k-p_{k-1}),p_1+(p_k-p_{k-1}),p_2+(p_k-p_{k-1}),\ldots,p_{k-1}+(p_k-p_{k-1})]$$$. That is, we append $$$0$$$ to the beginning of $$$p$$$, delete the last element of $$$p$$$, then add $$$p_k-p_{k-1}$$$ to all elements.

We want to show that $$$s_{p'}= (s_p+1) \% (2n+1)$$$. We will split into two cases.

Note that $$$p_k$$$ is $$$-1$$$, since there are $$$n$$$ $$$\texttt{(}$$$s and $$$n+1$$$ $$$\texttt{)}$$$s. Furthermore, we can more easily consider $$$p'=[0,p_1,p_2,\ldots,p_{k-1}]$$$ since adding a constant all elements of $$$p'$$$ does not change $$$s_{p'}$$$.

Case 1

Suppose that $$$s_p < 2n$$$, then $$$s_{p'} = s_{p}+1$$$. From our assumption that $$$s_p$$$ is the special index of $$$p$$$, we already have that $$$p'_i > p'_{s_p+1}$$$ if $$$1 \leq i<s_{p}+1$$$ and $$$p_{s_p+1} \leq p_i$$$ if $$$s_p+1<i$$$. It only remains to prove that $$$p'_0 > p'_{s_p+1}$$$.

Since $$$p_k=-1$$$, it must be true that $$$p_{s_p} \leq -1$$$. We obtain $$$p'_0=0>-1\geq p_{s_p}$$$. Therefore, $$$p'_0 > p'_{s_p+1}$$$ and $$$s_{p'}=s_p+1$$$ is the special index of $$$p'$$$.

Case 2

Suppose that $$$s_p = 2n$$$. We only have to prove that all elements of $$$p'$$$ are non-negative to claim that $$$s_{p'}=0$$$. This is easy by contradiction. Suppose that $$$p'_j < 0$$$. Then it is impossible that $$$0 > p_{j-1} > p_{2n}=-1$$$. $$$\blacksquare$$$

In fact, our claim is a modified version of cycle lemma where we have $$$m=n+1$$$ and $$$k=1$$$ (see, for instance, $$$[3]$$$ for two nice proofs -- one by arranging the sequence on a circle and removing certain segments, and the other using an idea similar to the prefix sum idea presented above).

Now, let us rotate the string until $$$s_p=2n$$$. By our above claim, there is a unique position that satisfies this. since there are $$$n$$$ $$$\texttt{(}$$$s and $$$n+1$$$ $$$\texttt{)}$$$s, we have $$$p_{2n}=p_{s_p}=-1$$$. So, $$$p_i \geq 0$$$ for all $$$0 \leq i < 2n$$$. That is, the first $$$2n$$$ characters of the string is now a valid bracket sequence.

This translation is extremely abridged because I do not want to translate some stupid story line about the main characters from Chū-2 playing Yu-Gi-Oh.

There are $$$m$$$ cards. An array $$$a$$$ of length $$$n \leq m$$$ describes these cards where $$$m = \sum\limits_{i=1}^n a_i$$$. If $$$i \leq n$$$, then the $$$i$$$-th card has the string $$$\underbrace{\texttt{((}\ldots\texttt{(}}_{a_i-1 \ \text{times}}$$$. Otherwise, the $$$i$$$-th card has the string $$$\texttt{)}$$$. Out of all $$$m!$$$ ways to order the cards, find the number of valid orderings such that the cards, when read left to right, forms a valid bracket sequence.

Constraints:

• $$$1 \leq n \leq 40$$$
• $$$1 \leq a_i \leq 10^5$$$

Let's do the same set-up as earlier by adding an extra card that has the string $$$)$$$. Then we define the equivalence class in the same way, except now each equivalence class only has $$$m+1$$$ elements (well, we only have $$$m+1$$$ cards). I claim that each equivalence class still has exactly $$$1$$$ valid rotation.

Let's pretend that the cards don't exist for a while and we are just dealing with strings of length $$$2(n-m)+1$$$. We know that out of the $$$2(n-m)+1$$$ rotations, exactly one is valid, so our only concern is that this valid rotation is not present when we add on constraint about rotation with the "barriers" of the cards. But this will never happen because the string will be of this form $$$\texttt{(}X\texttt{))}$$$.

It is not too hard to show that each of the $$$3$$$ brackets belong to different cards due to the types of string that can be written on each cards. That is, we first have a valid rotation out of the possible $$$m+1$$$ rotations when accounting for the "barriers" of the cards, and the last character corresponds to a single card, so we can simply remove it.

Let's count first the number of ways with the addition of the extra card (remember that even if two cards have the same string, they are distinguishable). We have two types of cards — $$$\texttt{((}\ldots\texttt{(}$$$ and $$$\texttt{)}$$$. We have $$$n$$$ cards of the first type and $$$m-n+1$$$ cards of the second types. Overall, we have $$$\frac{1}{m+1} (m+1)! = m!$$$ valid ways to arrange them.

However, we have overcounted as we added our extra card. But no problems, it is easy to see that we counted each unique sequence $$$m-n+1$$$ times since each card of type $$$)$$$ has equal probability to be the last card that is removed. So, just divide our answer by $$$m-n+1$$$ and we get the answer of $$$\frac{m!}{m-n+1}$$$.

We are enumerating balanced bracket sequences that have length $$$2n$$$ and the first $$$k$$$ elements are $$$\texttt{(}$$$. This is equivalent to enumerating the bracket sequence which have $$$n-k$$$ $$$\texttt{(}$$$s and $$$n$$$ $$$\texttt{)}$$$s where $$$p_i \geq -k$$$.

Let us study the distinct binary strings with $$$n-k$$$ $$$\texttt{(}$$$s and $$$n+1$$$ $$$\texttt{)}$$$s. Instead of defining a special index, let us define a special set of indices $$$s_p$$$. Let $$$mn$$$ be the minimum value of the prefix sum. We will store the special leftmost index with values in the range $$$[mn,mn+k]$$$, so we are storing $$$k+1$$$ indices in our set. Note that $$$k+1$$$ is equal to the difference between the number of $$$\texttt{(}$$$ s and $$$\texttt{)}$$$ s.

Now, with a similar case work to our original solution, we can show that this set similarly rotates with our string (exercise to reader). The claim is now that if and only if $$$2n-k \in s_p$$$, then the concatenation of $$$\underbrace{\texttt{((}\ldots\texttt{(}}_{k \ \text{times}}$$$ with the first $$$2n-k$$$ characters of the string gives us a balanced bracket sequence.

Suppose that $$$2n-k \in s_p$$$. Since $$$p_{2n-k}=-k-1$$$, then we have $$$p_i \geq -k$$$ for $$$0 \leq i < 2n-k$$$. Suppose that this is not true, that is we have $$$p_j < -k$$$ for some $$$j$$$, Let us define $$$p_{-1}=0$$$ for convinience. By the definition of prefix sum, we have $$$|p_i-p_{i-1}| =1$$$ for $$$0 \leq i < 2n-k$$$. Since $$$p_{-1}=0$$$ and $$$p_j < -k$$$, by discrete intermediate value theorem, there exists $$$p_z = -k$$$ for some $$$0 \leq z < j$$$. This contradicts the fact that $$$2n-k$$$ was the leftmost index with value $$$-k-1$$$. So it is proven for this case.

Suppose that $$$2n-k \notin s_p$$$. Either $$$-k-1 \notin [mn,mn+k]$$$ or $$$2n-k$$$ is not the leftmost index with value $$$-k-1$$$. Both of these contradict our statement. So it is proven for this case too.

Now, let us study a single equivalence class defined by the same equivalence relation of $$$s \sim_R t$$$ when $$$s$$$ is a cyclic shift of $$$t$$$. But we need to note here that not all equivalence classes have the same size. Indeed, let $$$n=3$$$ and $$$k=1$$$. Then we are studying strings that are a permutation of $$$\texttt{(())))}$$$. In the equivalence class containing $$$\texttt{())())}$$$, there are only $$$3$$$ elements, while in the equivalence class containing $$$\texttt{(())))}$$$, there are $$$6$$$ elements. But this is actually fine.

Given a string $$$s$$$, choose the shortest string $$$t$$$ such that $$$s$$$ is the concatenation of some copies of $$$t$$$. Then, the number of elements in the equivalence class containing $$$s$$$ is $$$|t|$$$.

We now want to show that of those $$$|t|$$$ elements, $$$\frac{k+1}{n+1} \cdot \frac{|t|}{|s|}$$$ of them satisfy $$$2n-k \in s_p$$$.

I claim that if $$$x \in s_p$$$, then $$$(x+|t|) \% (2n-k+1) \in s_p$$$. It is not too hard to prove this by noting that $$$p_{|t|}<0$$$, since the ratio of bracket types in $$$s$$$ and $$$t$$$ are the same.

Therefore, pick any element in the equivalence class. By the property of elements of $$$s_p$$$ being rotated while we rotate the string, the number of strings that correspond to valid bracket sequences is the number of elements in $$$(2n-k-|t|,2n-k] \cap s_p$$$. Since, we know that if $$$x \in s_p$$$, then $$$(x+|t|) \% (2n-k+1) \in s_p$$$, we have $$$\sum\limits_{i=0}^\frac{|s|}{|t|} |(-1+i \cdot |t|,-1+(i+1) \cdot |t|] \cap s_p| = |s_p| = \frac{|s|}{|t|} \cdot |(2n-k-|t|,2n-k] \cap s_p|$$$.

Therefore, we conclucde that $$$|(2n-k-|t|,2n-k] \cap s_p| = (k+1) \cdot \frac{|t|}{|s|}$$$. That is to say, in each equivalence class, there is a $$$\frac{k+1}{|s|}= \frac{k+1}{2n-k+1}$$$ probability that some element corresponds to a bracket sequence.

Since there are $$$\binom{2n-k+1}{n-k}$$$ elements total, there are $$$\frac{k+1}{2n-k+1} \binom{2n-k+1}{n-k}$$$ elements that correspond to bracket sequences where the first $$$k$$$ elements are $$$\texttt{(}$$$ s.

In fact, this gives us a way to generate a uniform random balanced bracket sequence of length $$$2n$$$ where the first $$$k$$$ elements are $$$\texttt{(}$$$ s. Generate a random string with $$$n-k$$$ $$$\texttt{(}$$$ s and $$$n+1$$$ $$$\texttt{)}$$$ s. The equivalence class that this string will be in is obviously proportional to the number of elements in said equivalence class. Now, we could pick a random element of $$$(2n-k-|t|,2n-k] \cap s_p$$$, but you can simply pick a random element of $$$s_p$$$ and it will be equivalent.

Oh course, we could use the method of incrementally placing $$$\texttt{(}$$$ or $$$\texttt{)}$$$ by their correct ratio, but this is way cooler.

#include <bits/stdc++.h>

#include "testlib.h"

std::string balanced_bracket_sequence_v1(int n) {
    auto res = std::string(n, '(') + std::string(n + 1, ')');
    shuffle(res.begin(), res.end());
    std::vector<int> pref(2 * n + 2, 0);
    for (int x = 0; x < 2 * n + 1; x++)
        pref[x + 1] = pref[x] + (res[x] == '(' ? 1 : -1);
    int idx =
        int(std::min_element(pref.begin(), pref.end()) - pref.begin());
    std::rotate(res.begin(), res.begin() + idx, res.end());
    return res.substr(0, 2 * n);
}

std::string balanced_bracket_sequence_v2(int n) {
    auto a = std::string(n, '(') + std::string(n, ')');
    shuffle(a.begin(), a.end());
    auto output = a;
    for (int l_in = 0, l_out = 0, r_in = 2 * n; l_in < r_in;) {
        int pos = l_in;
        int balance = 0;
        for (; pos != r_in; ++pos)
            if ((balance += (a[pos] == '(' ? +1 : -1)) == 0) break;
        if (a[l_in] == '(') {
            for (; l_in <= pos; ++l_in, ++l_out) output[l_out] = a[l_in];
        } else {
            const int sz_u = r_in - pos - 1, r_out = l_out + sz_u + 1;
            output[l_out] = '(', output[r_out] = ')';
            for (int i = l_in + 1, j = r_out + 1; i != pos; ++i, ++j)
                output[j] = (a[i] == '(' ? ')' : '(');
            l_in = pos + 1;
            l_out++;
        }
    }
    return output;
}

std::string balanced_bracket_sequence_v3(int n) {
    long long a = 0, b = 0;
    std::string res;
    for (int x = 0; x < 2 * n; x++) {
        if (rnd.next((2 * n - a - b) * (a - b + 1)) <
            (n - a) * (a - b + 2)) {
            res += '(';
            a++;
        } else {
            res += ')';
            b++;
        }
    }
    return res;
}

struct tree {
    int node;
    tree *l, *r;
    tree(int node_, tree* l_, tree* r_) : node{node_}, l{l_}, r{r_} {}
};

int get_value(tree* t) {
    if (t) return t->node;
    return -1;
}

using representation_t = std::vector<std::tuple<int, int, char>>;

auto representation(tree* t) {
    representation_t repr;
    auto dfs = [&repr](auto self, tree* a) -> void {
        if (!a) return;
        repr.emplace_back(a->node, get_value(a->l), 'L');
        repr.emplace_back(a->node, get_value(a->r), 'R');
        self(self, a->l);
        self(self, a->r);
    };
    dfs(dfs, t);
    return repr;
}

auto shuffled_representation(int n, representation_t r) {
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    shuffle(p.begin(), p.end());  // shuffle vertex labels
    for (auto& [n1, n2, dir] : r) {
        if (n1 != -1) n1 = p[n1];
        if (n2 != -1) n2 = p[n2];
    }
    shuffle(r.begin(), r.end());  // shuffle edge order
    return r;
}

tree* binary_tree_from_balanced_bracket_sequence(const std::string& s) {
    int n = int(s.size()) / 2;
    std::vector<int> nxt(2 * n, -1);
    std::vector<int> stk;
    for (int x = 0; x < 2 * n; x++) {
        if (s[x] == '(') {
            stk.push_back(x);
        } else {
            nxt[stk.back()] = x;
            stk.pop_back();
        }
    }
    int node = 0;
    std::vector<tree*> roots(2 * n, nullptr);
    for (int x = 2 * n - 1; x >= 0; x--) {
        if (s[x] == '(') {
            tree *left = nullptr, *right = nullptr;
            if (s[x + 1] == '(') left = roots[x + 1];        // left child
            if (nxt[x] + 1 < 2 * n && s[nxt[x] + 1] == '(')  // right child
                right = roots[nxt[x] + 1];
            roots[x] = new tree(node++, left, right);
        }
    }
    return roots[0];
}

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    int n = opt<int>("n");
    int t = opt<int>("t");
    std::cout << t << '\n';
    for (int test = 1; test <= t; ++test) {
        std::cout << n << '\n';
        auto rep = shuffled_representation(
            n, representation(binary_tree_from_balanced_bracket_sequence(
                   balanced_bracket_sequence_v1(n))));
        for (auto [parent, child, direction] : rep)
            std::cout << parent + 1 << ' ' << child + 1 << ' ' << direction
                      << '\n';
    }
}

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

string bSeq(int n,int k) {
    string res=string(n-k,'(')+string(n+1,')');
    shuffle(res.begin(),res.end());
    deque<int> dq(k+1);
    
    int mn=0;
    int curr=0;
    for (int x=0;x<=2*n-k;x++){
    	curr+=(res[x]=='('?1:-1);
    	if (curr<mn){
    		mn=curr;
    		dq.push_back(x);
    		dq.pop_front();
    	}
    }
    
	rotate(res.begin(),res.begin()+dq[rnd.next(k+1)]+1,res.end());
    return string(k,'(')+res.substr(0,2*n-k);
}

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    int n=atoi(argv[1]),k=atoi(argv[2]);
    
    cout<<bSeq(n,k)<<endl;
}

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

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dist(0.0, 1.0);

double cat[10000005];
double t[10000005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cat[0]=1;
	rep(x,0,10000000) cat[x+1]=(double)(x+0.5)/(x+2)*cat[x];
	
	rep(x,1,100000){
		double tot=0;
		rep(y,0,x){
			double prob=cat[y]*cat[x-y-1]/(4*cat[x]);
			t[x]+=prob*(t[y]+t[x-y-1]+min(y,x-y-1));
			tot+=prob*min(y,x-y-1);
		}
	}
	
	rep(x,1,100000) cout<<x<<" "<<t[x]<<endl;
}

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

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dist(0.0, 1.0);
 
long long time(){
	return chrono::system_clock::now().time_since_epoch().count();
}
 
double cat[10000005];

void solve(int pl,int pr,string &s){
	if (pl==pr) return;
	
	double temp=dist(rng);
	int n=(pr-pl)/2;
	
	double curr=0;
	int l=0,r=n-1;
	int ss;
	
	while (true){
		{ //add l
			curr+=cat[l]*cat[n-1-l]/(4*cat[n]);
			if (temp<curr){ ss=l; break; }
			l++;
		}
		{ //add r
			curr+=cat[r]*cat[n-1-r]/(4*cat[n]);
			if (temp<curr){ ss=r; break; }
			r--;
		}
	}
	
	s[pl+1+2*ss]=')';
	solve(pl+1,pl+1+2*ss,s);
	solve(pl+2+2*ss,pr,s);
}

string gen(int n){
	cat[0]=1;
	rep(x,0,n) cat[x+1]=(double)(x+0.5)/(x+2)*cat[x];
	
	string res(2*n,'(');
	solve(0,2*n,res);
	return res;
}

signed main(int argc, char *argv[]){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	rep(x,0,24){
		long long start=time();
		long long num=0;
		while (time()-start<10000000000){
			gen(1<<x);
			num++;
		}
		
		long long end=time();
		cout<<(1<<x)<<" "<<num<<" "<<end-start<<" "<<(double)(end-start)/(num*(1<<x))<<endl;
	}
}

1 266547240 10000000078 37.5168
2 187154707 10000000050 26.7159
4 102058691 10000000091 24.4957
8 47076531 10000000131 26.5525
16 22151581 10000000151 28.2147
32 10758623 10000000660 29.0465
64 5403745 10000009142 28.9152
128 2734025 10000000066 28.5751
256 1338297 10000004834 29.1882
512 660750 10000010888 29.5592
1024 328150 10000004632 29.7597
2048 158510 10000011967 30.8045
4096 77867 10000111333 31.3539
8192 38048 10000260495 32.0841
16384 18565 10000365194 32.8777
32768 9273 10000355466 32.9113
65536 4657 10000484304 32.7669
131072 2277 10004361811 33.521
262144 1104 10004416345 34.5687
524288 548 10006717357 34.829
1048576 270 10012533429 35.3655
2097152 130 10035361701 36.8095
4194304 65 10088588940 37.0047
8388608 33 10127937055 36.5862

Monogon: Because div1 people are not the target audience of div2AB

dario2994: Because it matters a lot for the remaining 95% of contestants.

isaf27: Because we should care about all participants. For the majority of them first problems are very important, because they solve only these 1/2/3 problems during the contest, it is normal.

74TrAkToR: d2AB is not needed by people from div1, but in general we have a codeforces site, so it seems normal to me to start with easy tasks and gradually move to difficult ones, trying to do everything quickly

Monogon: I don't have any rule of thumb from just the statement, I use intuition. If my intuition is wrong, that's why we have low rated testers. I should expect almost all testers to solve A, most testers solve B but lower rated users take longer, and C will stump some testers.

Um_nik: ask for lower rated users opinions

isaf27: I often fail too, testing helps a lot :) When I estimate the difficulty of the simple problems I try think what helps me to solve the problem: my experience, or I will solve the problem in the same way, if I won't have my problem solving experience. If the problem is very simple and follows the second case, it is d2a. But sometimes more skilled participants find d2b/d2c easier, because they can solve it faster using their experience.

74TrAkToR: I somehow do not have any special problems to distinguish them. Anyway, as a rule, you solve d2A faster than d2B and d2C. Again, it all depends on the idea and implementation. On testing if you can make sure of everything)

darkkcyan: Testing. Making a problem is like making a puzzle, which is hard. Things seem to be trivial to the authors, but that's usually not the case for non authors (coordinators included). That's why the coordinator is the first barrier for filtering the problems. But testing will be more accurate.

-is-this-fft-: approachable for beginners, no troll (you have to understand the solution to get the solution), still very easy, not annoying at all, and somehow manages to also be a bit interesting besides that

antontrygubO_o: great A, solved with small observations

dario2994: Slightly hard for an A, no computer science involved, requires to know that $$$3|n$$$ iff $$$3|\text{sumdigits}(n)$$$. (accepted)

Um_nik: the story is really awful, the problem is ok-ish, although it might be a bit too hard for A

Monogon: a little too hard since it requires multiple observations (just needs to be multiple of 4 and 3 and 5, remember divisibility tests for each, consider how they interact with each other)

darkkcyan: This problem seems to be between div2A and B difficulty. About the idea which is the divisibility of some numbers, I think it was elementary. So yes it could be a bit unfair for people with no or little math background. But it does introduce the topic.

isaf27: great d2a, follows my philosophy

kIee: artifically long, small redundant details like extra leading 0s, very artificial in converting output answer to red and cyan

sus: I wouldn't mind haivng to solve problems like this as a div2AB because its just brute force and checking certain conditions that are easy enough to think about (e.g. what are the factors of 60, how can I use this information to help me solve this task). However, the conditions are quite niche such as chinese remainder theorem and most newbie/pupils dont know it. Not the best for a div2AB but if it was more generalized, a similar problem would be better. This problem is a [3/10] but a similar, easier and more common version would be a [6/10]

-is-this-fft-: again i see nothing wrong with it. instantly approachable and not at all tedious. to get more than 8 it would need to be more interesting

antontrygubO_o: problem tells to implement the statement

dario2994: "Implement what is written in the statement", nice statement, very easy. (rejected)

Um_nik: implement what is written in statement, this is not a problem

Monogon: difficulty is good and it requires some observation about how only last character matters or it forces you to do a non-trivial implementation of handling the case when the string is too short to grab a suffix of length k. However the problem is probably not that interesting so I only put it at 7.

darkkcyan: Seems to be a problem with annoying case work at first, but there is a solution that checks only the last character. This problem allows newbies to push forward, but still teaches some observation (if the those newbies read the editorial or rethink about it of-course). I give a small minus point on the statement about using some buzz words like machine learning tho, which might confuse people with no background.

isaf27: Simple, but definitely not interesting problem + "just write what is asked in the statement"

kIee: statement is very clear, use of listing to show the differences is clear, dont like how it talks about three/four suffixes, a little confusing on first read

sus: This is a good div 3A. I dont know what its doing in a div2AB but its way too easy to even be enjoyable enough to solve.

-is-this-fft-: almost perfect. approachable, easy and interesting. the missing 1 point is from it being just a little bit guessable

antontrygubO_o: may be too mathy, and a bit hard for A, but it's still quite easy to see the pattern after drawing for some time. Also I believe that a lot of people would enjoy realizing that answer is just print(input()), so problem would leave positive emotions.

dario2994: Involved statement, interesting problem, no computer science involved. (accepted)

Um_nik: very nice

Monogon: This is a timeless masterpiece, what more can I say? However, no one should ever do this again.

darkkcyan: At the first glance, for me this is really trivial. But seems like I underestimated it. This problem does require that one trivial observation to solve, which is not obvious to everyone. I have open the last page of the standing page. There, people did totally random stuffs. So I give the problem 9, because it is really easy, but still teaches observation. I might give it 10, but it too easy (for me at least).

isaf27: A bit hard to understand statement, a formula problem

kIee: short statement, very clear with illustrations, qn is pretty cool too

sus: Even though this answer is just n, its was still fun figureing out how to reach that answer. Great div2AB. It is simple to understand the problem, fun to solve and challenging to see the answer.

-is-this-fft-: falls squarely under "troll" problems

antontrygubO_o: Ok, this one is too much, but it's the best troll problem in the history

dario2994: "who cares" statement, "who cares" solution, necessary to know or-operator, no computer science. (rejected)

Um_nik: weird but ok

Monogon: It's pretty funny that any permutation works, but unlike 1339A i don't think most people who solve this will understand why it's correct.

darkkcyan: his problem suited B more than A. But if it was B then it might be 8. The participant need to know OR operation in order to understand the statement. The participant will then try random permutation and prove it. The old me some how use the identity permutation, but the another solution I have thought of now is to put the biggest element in the middle of the array, dividing the array into two half, and solve two half recursively. But yes, since every array works, the solutions does not really mater. But I think the amount of time for this problem, either to think fast then code slow, or either to think slow, then code fast, is not really suitable for A.

isaf27: Too joke

kIee: firstly the OR statement directs to a external page(thus factor of internet connection, and understanding what OR is for those who may not be familiar), 2ndly its just a bad problem...

sus: I dont like it because it has an obvious answer. It doesn't make you think at all

-is-this-fft-: Too hard and teaches beginners to guess.

antontrygubO_o: The observation here is great, but it's kind of too mathy. Also, many people may be new to modulo operations, I don't think that they are very suitable for an A.

dario2994: Natural statement, requires no knowledge, interesting, too hard for an A but ok for a B, no computer science involved, requires to know modulo operations. (accepted as a B)

Um_nik: counting anything modulo is probably a bit hard for div2A, but this one is one simple observation, so maybe fine

Monogon: I think modular arithmetic is too advanced for div2A. Also the main idea itself is probably too tricky for div2A. It's probably only rated 800 because people who couldn't solve it just quit the contest, we can see it had much fewer solves than a typical A. Anyway it's a good problem, just a bad fit for A

darkkcyan: This problem could be A, but it seems harder than usual. The observation is about the symmetry between the good and non-good permutation. If there is no example, then I think I might stuck, and I only guess the solution using the sample. It could be 8 or 9 if it is B instead.

isaf27: Nice idea. Maybe not ideal, because it is a formula problem

kIee: statement quite clear, but problem is quite lame

sus: I don't like it because confusing problem statement and it makes me want to close the tab. Whats so fun about permutations guys. Leave them alone for div2ABs. These problems are unoriginal and boring

-is-this-fft-: falls squarely under "troll" problems

dario2994: Interesting natural statement, requires to know trees. (accepted)

Um_nik: ok problem about reading statements and understanding how trees work

Monogon: I think graph/tree problems shouldn't appear until C. Even though this problem doesn't require a DFS, it's a bit too difficult for B.

darkkcyan: It is a good B, but I remember that I have stuck there for a quite a while (compared to normal B) when solving this problem. It is harder than usual B, but seems too easy to be C.

isaf27: Good, but a bit too joke constructive

kIee: problem is unnecessarily long, example of a tree is misleading, the idea that $$$m < n$$$ is very hidden, redeeming factor is that problem is quite nice

sus: Pretty hard but it is a B problem, so I think its ok. Pretty interesting, I have never seen a B problem that has to deal with nodes or trees. It is a good start to introduce beginner programmers to the world of trees in the case they have never seen them before. Solid and unique problem

-is-this-fft-: Yeah, I don't mind such problems, especially in an educational round. A is a warmup problem, it doesn't need to be something extremely original. The problem is okay because it is instantly approachable for a beginner, which is something that many problems here lack.

antontrygubO_o: Nothing outstanding, but nothing wrong, people need to "invent" dfs for 2*n grids

dario2994: Just perfect, maybe slightly hard for an A. (accepted)

Um_nik: I highly doubt that's the first time this problem is used, otherwise it's fine

Monogon: you can use a simple observation or you can use a DFS if you really really want to, it seems correct difficulty and not boring

darkkcyan: Again, still look harder than usual, but with simple observation on how the maze works, the coding part is not bad. Other people still come up with bfs or dp solutions though, but that's fine, because at least they can push forward.

isaf27: It can be solved in many ways, and it is very good for d2a problem

kIee: cool problem, statement quite clear, would be better with a picture

sus: Good problem because it can be solved with either graphs or just logic, which is a good thing in beginner problemsets because it can show people that there are multiple ways to reach the same end goal. People who know graphs can use graphs and people who don't know can either use logic or after contest spend some time learning graphs.

-is-this-fft-: This would probably be higher at like 5/10 or 6/10, but the fact that the rather unintuitive possibility of $$$k=0$$$ was not mentioned or hinted at in any way makes this very bad. "Gotchas" like this can be considered in harder problems, but in problem A, they are simply unacceptable. Not 1/10, that would probably be something completely inappropriate.

antontrygubO_o: I would prefer to remove the $$$(1, 1)$$$ case now, then it would be 8/10, with this case it's 6/10.

dario2994: No computer science, very hard for an A, easy to guess, interesting. (accepted)

Monogon: pretty good, but I think it's likely many people can guess the answer without understanding why.

darkkcyan: This is a case work problem, but it requires understanding about Manhattan distance. It is a good problem because the participant can come up with the strategy with pen and paper.

isaf27: Formula problem, a bit joke

kIee: cool but the trap is quite bad

sus: I actually solved this in contest and didn't like it too much. It is logic heavy and requires a lot of time to think about it and in the end it is just a few lines of code created through tons of guess and checks.

-is-this-fft-: Again troll problem with weird restriction and random simple observation.

antontrygubO_o: very cute observation.

dario2994: Requires to know xor, involved statement. (rejected)

Um_nik: overcomplicated, the problem doesn't bring anything interesting

Monogon: the even/odd invariant is so overused and this looks like a very lazy application of it. Besides not being very interesting, it seems that it turned out to be too hard for B.

darkkcyan: Good problem in general, and the required knowledge is kinda ok. A minus point about the hack part, since it might expose somethings.

isaf27: Great d2b for my opinion

kIee: artificially long and confusing statement.

sus: I solved this too after spending CLOSE TO HALF AN HOUR. I hate bitwise problems personally so my opinion on these problems is biased. I hate them because bitwise is such a niche thing that almost no one knows when they start out programming but then there are so many cp problems based around bitwise.

-is-this-fft-: This one doesn't suffer from the problems I see in most easy problems here, but it gets a lower score because it is somewhat tedious and also not very interesting.

antontrygubO_o: ok problem, observation + some intuition, but the statement is a bit hard for beginners

dario2994: Ok problem. (accepted)

Monogon: maybe a bit hard for A but it's actually pretty nice and simple. Maybe the statement takes slightly too long to understand.

darkkcyan: The difficulty is ok. For me it is not that fun to solve, but for div2A, this problem is fine.

isaf27: Just not very interesting problem

kIee: simple statement with nice illustration. implementation not so fun.

sus: Solved this one too. Really enjoyed it because it was unique, fun, and creative. The pictures are also really nice and helpful as I was able to figure out a solution just by looking at them. I actually like these sorts of problems now because of just this one. If you are able to create a problem that makes other people like those types of problems from that point on, you have succeeded as a problem setter

The main idea of my solution is to keep splitting the query range in half. Suppose we know that $$$l \leq L \leq R \leq r$$$. Let $$$m=\frac{l+r}{2}$$$.

Then there are $$$3$$$ cases:

1. answer $$$m$$$
2. recurse to $$$[l,m)$$$
3. recurse to $$$(m,r]$$$

Let us put a bit on position $$$m$$$. If that bit is activated, then it is case 1. Otherwise, we need to differentiate case 2 and 3. Notice that in the array $$$[1,2,1,4,1,2,1]$$$, all the subarrays have non-zero xor-sums. So we can put this array on the left side. If there exists any bit that is activated in that range, it is case 2. Otherwise, it is case 3.

In total, this uses something like $$$2+3+4+\ldots+\log N$$$ bits.

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

#define ll long long
#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()

const int L=18;
int n=1<<(L+1);
vector<bitset<192>> v;

void dnc(int l,int r,int idx,int d){
	if (d==0) return;
	
	int m=l+r>>1;
	
	v[m][idx]=1;
	idx-=d;
	rep(x,l,m){
		v[x][idx+__builtin_ctz(x+1-l)]=1;
	}
	
	dnc(l,m-1,idx-1,d-1);
	dnc(m+1,r,idx-1,d-1);
}

vector<bitset<192>> init(){
	rep(x,0,n) v.push_back(bitset<192>(0));
	dnc(0,n-2,191,L);
	
	v[n-1][0]=1;
	return v;
}

int answer(bitset<192> v){
	if (v[0]) return n-1;
	
	int l=0,r=n-1;
	int idx=191,d=L;
	
	while (d){
		int m=l+r>>1;
		if (v[idx]) return m;
		bool flag=false;
		rep(x,idx-d,idx) if (v[x]) flag=true;
		
		if (flag) r=m-1;
		else l=m+1;
		idx-=d+1;
		d--;
	}
	
	return l;
}

(this was written by oolimry)

Let $$$B = \sqrt N$$$, we split it into $$$B$$$ buckets of size $$$B$$$ each. There are $$$3$$$ layers.

We generate $$$B$$$ random $$$36$$$-bit numbers such that all $$$O(B^2)$$$ ranges have unique xors, which we can store all unique xors into a map. Let $$$R[i]$$$ be i-th the random $$$36$$$ bit number. This will be used in layer 1 and layer 2.

For layer 1 ($$$36$$$ bits), the position is blank if $$$i \text{ mod } B != 0$$$. Else if $$$i \text{ mod } B == 0$$$ (i.e the boundary between two buckets), the position has the value $$$R[i/B]$$$ for those 36 bits.

Layer 2 ($$$36$$$ bits), the position has value $$$R[i \text{ mod } B]$$$.

If the range extends across more than $$$1$$$ bucket, layer 1 can detect it. Otherwise, layer 2 will tell us that the range is of the form $$$L + kB$$$ to $$$R + kB$$$ for some $$$k$$$, where $$$k$$$ is the bucket number. Now we use layer 3 to determine which bucket.

Layer 3 ($$$38$$$ bits) is assigned to all positions and can just be assigned randomly. To find the value of $$$k$$$, just check all B buckets and verify if the range xor matches. Layer 3 serves as a random checksum.

[The values of 36 and 38 are arbitrary]

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint, lint> ii;
typedef pair<lint, ii> iii;


mt19937_64 rng(time(0));
int n;

lint arr[2005];
bitset<192> arrb[2005];
vector<iii> M;

lint bitsA = 38;
lint bucket = 2000;

lint bitsD = 36;
bitset<192> brr[2005];


bitset<192> firstmask;
bitset<192> secondmask;
bitset<192> thirdmask;

vector<bitset<192> > toset;
vector<bitset<192> > prefxor;
pair<int, vector<bitset<192> > > init(){
    int n = 1<<19;
    toset.resize(n);
    prefxor.resize(n);
    
    rng.seed(1633860579000212400);
    for(int i = 0;i < bucket;i++){
        arr[i] = rng() & ((1LL<<bitsA) - 1LL);
    }
    
    for(int l = 0;l < bucket;l++){
        lint X = 0;
        for(int r = l;r < bucket;r++){
            X ^= arr[r];
            M.push_back(iii(X, ii(l,r)));
        }
    }
    
    sort(all(M));
    
    for(int i = 0;i < bucket;i++){
        bitset<192> bs(arr[i]);
        arrb[i] = bs;
    }
        
    for(int i = 0;i < n;i++){
        toset[i] |= arrb[i%bucket];
        
        if(i%bucket == 0){
            toset[i] |= (arrb[i/bucket] << bitsA);
        }
        
        bitset<192> bs(rng()&((1LL<<bitsD)-1));
        bs <<= (2*bitsA);
        toset[i] |= bs;
    }
        
    for(int i = 0;i < n;i++){
        prefxor[i] = toset[i];
        if(i != 0) prefxor[i] ^= prefxor[i-1];
    }
    
    return {n, toset};
}

int answer(bitset<192> bs){
    lint B = 0;
    for(int b = 0;b < bitsA;b++){
        if(bs[b+bitsA]) B |= (1LL<<b);
    }
    
    auto it = lower_bound(all(M), iii(B, ii(-1,-1)));
    if(it != M.end() and it->first == B){
        return (it->second.first) * bucket;
    }
    
    lint A = 0;
    for(int d = 0;d < bitsA;d++){
        if(bs[d]) A |= (1LL<<d);
    }
    auto it2 = lower_bound(all(M), iii(A, ii(-1,-1)));
        
    
    for(int b = 0;b < bucket;b++){        
        int L = b*bucket + (it2->second).first;
        int R =    b*bucket + (it2->second).second;
        
        
        bitset<192> BBS = prefxor[R];
        if(L > 0) BBS ^= prefxor[L-1];
        
        if(BBS == bs){
            return L;
        }
    }
    
    assert(false);
}

(this was written by errorgorn so might be a gross oversimplication :P)

If we randomly assign bits such that they were periodic with period $$$T$$$ and their xor-sum of a subarray with length $$$T$$$ was $$$0$$$, then we could find several candidates for $$$(l \text{ mod } T,r \text{ mod } T)$$$. We can store these bits for several coprime values of $$$T$$$ then we have another checksum to ensure that our candidate is correct.

Do note that this solution actually recovers the original subarray!

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

const int N = (1<<19);
vector<bitset<192>> V;

const int m0 = 801;
const int m[3] = {797, 787, 773};

const int bits = 21;

mt19937 gen(0); //Standard mersenne_twister_engine seeded with rd()
uniform_int_distribution<> distrib(1, (1<<bits)-1);

int crt0[m0+2][m0+2];
int crt1[m0+2][m0+2];
int crt2[m0+2][m0+2];

int ctr[(1<<bits)+1];
pair<short,short> p[m0*m0];

int next_random() {
    return distrib(gen);
}

const bitset<192> mask = bitset<192>((1<<22)-1);

vector<bitset<192>> init() {
    V.resize(N);
    for(int i=0; i<N; i++) V[i].reset();
    vector<int> v;
    v.push_back(0);
    set<int> s;
    while(v.size() <= m[0]) {
        int x;
        do {
            x = next_random();
        } while(s.find(x)!=s.end()); // make sure x does not already exist
        s.insert(x);
        v.push_back(x);
    }
    for(int i=0; i<m[0]; i++) {
        for(int j=0; j<i; j++) {
            ctr[v[i]^v[j]]++;
        }
    }

    for(int i=1; i<=(1<<bits); i++) {
        ctr[i] += ctr[i-1];
    }
    for(int i=0; i<m[0]; i++) {
        for(int j=0; j<i; j++) {
            int* pt = &(ctr[v[i]^v[j]]);
            (*pt)--;
            p[*pt] = make_pair(i,j);
        }
    }
    for(int a=0; a<3; a++) {

        v[m[a]] = 0;
        //v.push_back(0);
        for(int i=0; i<N; i++) {
            int r = i % m[a];
            int d = v[r+1] ^ v[r]; // copy the bits of d into V[i]
            V[i] |= ((bitset<192>)(d))<<(a*22);
        }
        // counting sort (i,j) based on (v[i]^v[j])


    }
    for(int i=0; i<N; i++) {
        long long tmp = (79143LL*i) ^ (79143LL*(i+1));
        V[i] |= ((bitset<192>)(tmp)) << 66;
    }

    for(int i=1; i<=N; i++) {
        crt1[i%m[0]][i%m[2]] = i;
        crt2[i%m[0]][i%m[1]] = i;
    }
    return V;
}



int answer(bitset<192> x) {
    // extract the lowest 66 bits into a number

    int a[3];
    a[0] = static_cast<int>((x&mask).to_ulong());
    a[1] = static_cast<int>(((x>>22)&mask).to_ulong());
    a[2] = static_cast<int>(((x>>44)&mask).to_ulong());
    long long z = (((x>>66)).to_ullong());
    if(a[2]==0) {
        int b = 0;
        int c = 1;
        for(int i1=ctr[a[b]]; i1 < ctr[a[b]+1]; i1++) {
            pair<short,short> p0 = p[i1];
            for(int i2=ctr[a[c]]; i2 < ctr[a[c]+1]; i2++) {
                pair<short,short> p1 = p[i2];
                int st = crt2[p0.first][p1.first];
                int en = crt2[p0.second][p1.second];
                if(st<=N && en<=N && (z ^(79143LL*st) ^ (79143LL*en))==0) {
                    return (st+en)/2;
                }
                swap(p1.first, p1.second);
                st = crt2[p0.first][p1.first];
                en = crt2[p0.second][p1.second];
                if(st<=N && en<=N && (z ^(79143LL*st) ^ (79143LL*en))==0) {
                    return (st+en)/2;
                }
            }
        }
    }
    if(a[1]==0) {
        int b = 0;
        int c = 2;
        for(int i1=ctr[a[b]]; i1 < ctr[a[b]+1]; i1++) {
            pair<short,short> p0 = p[i1];
            for(int i2=ctr[a[c]]; i2 < ctr[a[c]+1]; i2++) {
                pair<short,short> p1 = p[i2];
                int st = crt1[p0.first][p1.first];
                int en = crt1[p0.second][p1.second];
                if(st<=N && en<=N && (z ^(79143LL*st) ^ (79143LL*en))==0) {
                    return (st+en)/2;
                }
                swap(p1.first, p1.second);
                st = crt1[p0.first][p1.first];
                en = crt1[p0.second][p1.second];
                if(st<=N && en<=N && (z ^(79143LL*st) ^ (79143LL*en))==0) {
                    return (st+en)/2;
                }
            }
        }
    }
    if(true) {
        int b = 1;
        int c = 2;
        for(int i1=ctr[a[b]]; i1 < ctr[a[b]+1]; i1++) {
            pair<short,short> p0 = p[i1];
            for(int i2=ctr[a[c]]; i2 < ctr[a[c]+1]; i2++) {
                pair<short,short> p1 = p[i2];
                //int st = crt0[p0.first][p1.first];
                //int en = crt0[p0.second][p1.second];
                int st = static_cast<int>((391139LL * p1.first) + (217213LL * p0.first)) % (m[1]*m[2]);
                int en = static_cast<int>((391139LL * p1.second) + (217213LL * p0.second)) % (m[1]*m[2]);

                if(st<=N && en<=N && (z ^(79143LL*st) ^ (79143LL*en))==0) {
                    return (st+en)/2;
                }
                swap(p1.first, p1.second);

                st = static_cast<int>((391139LL * p1.first) + (217213LL * p0.first)) % (m[1]*m[2]);
                en = static_cast<int>((391139LL * p1.second) + (217213LL * p0.second)) % (m[1]*m[2]);
                if(st<=N && en<=N && (z ^(79143LL*st) ^ (79143LL*en))==0) {
                    return (st+en)/2;
                }
            }
        }
    }
    assert(false);
    return 0;
}

// smawck for max
template<class F>
std::vector<int> smawck(F f, const std::vector<int> &rows, const std::vector<int> &cols) {
    std::vector<int> ans(rows.size(), -1);
    if((int) std::max(rows.size(), cols.size()) <= 2) {
        for(int i = 0; i < (int) rows.size(); i++) {
            for(auto j : cols) {
                if(ans[i] == -1 || f(rows[i], ans[i], j)) {
                    ans[i] = j;
                }
            }
        }
    } else if(rows.size() < cols.size()) {
        // reduce
        std::vector<int> st;
        for(int j : cols) {
            while(1) {
                if(st.empty()) {
                    st.push_back(j);
                    break;
                } else if(f(rows[(int) st.size() - 1], st.back(), j)) {
                    st.pop_back();
                } else if(st.size() < rows.size()) {
                    st.push_back(j);
                    break;
                } else {
                    break;
                }
            }
        }
        ans = smawck(f, rows, st);
    } else {
        std::vector<int> newRows;
        for(int i = 1; i < (int) rows.size(); i += 2) {
            newRows.push_back(rows[i]);
        }
        auto otherAns = smawck(f, newRows, cols);
        for(int i = 0; i < (int) newRows.size(); i++) {
            ans[2*i+1] = otherAns[i];
        }
        for(int i = 0, l = 0, r = 0; i < (int) rows.size(); i += 2) {
            if(i+1 == (int) rows.size()) r = (int) cols.size();
            while(r < (int) cols.size() && cols[r] <= ans[i+1]) r++;
            ans[i] = cols[l++];
            for(; l < r; l++) {
                if(f(rows[i], ans[i], cols[l])) {
                    ans[i] = cols[l];
                }
            }
            l--;
        }
    }
    return ans;
}

// max smawck
// F(i, j, k) checks if M[i][j] <= M[i][k]
// another interpretations is: 
// F(i, j, k) checks if M[i][k] is at least as good as M[i][j]
// higher == better
// when comparing 2 columns as vectors
// for j < k, column j can start better than column k
// as soon as column k is at least as good, it's always at least as good
template<class F>
std::vector<int> smawck(F f, int n, int m) {
    std::vector<int> rows(n), cols(m);
    for(int i = 0; i < n; i++) rows[i] = i;
    for(int i = 0; i < m; i++) cols[i] = i;
    return smawck(f, rows, cols);
}

template<class T>
std::vector<T> MaxConvolutionWithConvexShape(std::vector<T> anyShape, const std::vector<T> &convexShape) {
    if((int) convexShape.size() <= 1) return anyShape;
    if(anyShape.empty()) anyShape.push_back(0);
    int n = (int) anyShape.size(), m = (int) convexShape.size();
    auto function = [&](int i, int j) {
        return anyShape[j] + convexShape[i-j];
    };
    auto comparator = [&](int i, int j, int k) {
        if(i < k) return false;
        if(i - j >= m) return true;
        return function(i, j) <= function(i, k);
    };
    const std::vector<int> best = smawck(comparator, n + m - 1, n);
    std::vector<T> ans(n + m - 1);
    for(int i = 0; i < n + m - 1; i++) {
        ans[i] = function(i, best[i]);
    }
    return ans;
}

We will prove this by induction. Assume that before the $$$i$$$-th iteration of the for loop, for all $$$1 \leq j < i$$$, $$$V_j=0$$$. We want to show that after the iteration, the condition of $$$V_j=0$$$ also applies to $$$j=i$$$.

Case 1: $$$V_i=0$$$

$$$V$$$ is not changed and $$$V_i=0$$$ holds by definition.

Case 2: lines 7 to 11

Since $$$g=\gcd(V_i,m)$$$, there exists integer $$$k$$$ such that $$$V_i=gk$$$. We observe that $$$V_i \times \frac{m}{g} = gk \times \frac{m}{g}=0$$$, so $$$V_i=0$$$ at the end of $$$i$$$-th iteration.

Case 3: lines 12 to 14

$$$V_i - A_{i,i} \times \frac{V_i}{A_{i,i}} = 0$$$, so $$$V_i=0$$$ at the end of $$$i$$$-th iteration.

Case 4: lines 15 to 23

Similar to case $$$3$$$.

Consider how $$$span(S)$$$ changes after a call to \AV{$$$V$$$}. $$$x \in span(S \cup V)$$$ implies that there exists $$$y \in span(S)$$$ and $$$\lambda \in (\mathbb{Z}/k\mathbb{Z})$$$ such that $$$x=y+\mu V$$$. Let $$$x=y+\mu V=\lambda_1 A_1 + \lambda_2 A_2 + \ldots + \lambda_d A_d + \lambda V$$$.

Case 1: lines 7 to 11

Let $$$g=\gcd(V_i,m)$$$, $$$(s,t)=\texttt{Extended-Euclidean}(V_i,m)$$$ and $$$m'=\frac{m}{g}$$$.

Let $$$A_i' = V \times s$$$ and $$$V' = V \times m'$$$.

We want to find $$$\lambda_i'$$$ and $$$\mu'$$$ such that $$$\lambda_i' A_i' + \mu'V'=\lambda_iA_i+\mu V$$$. Since $$$A_{i,i}=0$$$, we can see that $$$\lambda_iA_i=0$$$ and we can rewrite the above equation as $$$\lambda_i' \cdot s+\mu' \cdot m'=\mu$$$.

Since $$$s \cdot V_i + t \cdot m = g$$$, we have $$$\gcd(s \cdot V_i,m)=\gcd(s \cdot V_i + t \cdot m,m)=\gcd(g,m)=g$$$, which implies that $$$\gcd(s \cdot \frac{V_i}{g},\frac{m}{g})=1$$$.

Therefore, $$$\gcd(s,m')=\gcd(s,\frac{m}{g})=1$$$, by Bezout's lemma, we can find that there is a solution for $$$(\Lambda'_i,\lambda')$$$ for any value of $$$\mu$$$.

Case 2: lines 12 to 14

Let $$$V'=V-A_i \times \frac{V_i}{A_{i,i}}$$$.

We want to find $$$\lambda_i'$$$ and $$$\mu'$$$ such that $$$\lambda_i' A_i + \mu'V'=\lambda_iA_i+\mu V$$$.

$$$\lambda_i' A_i + \mu' V'=(\lambda_i'+\mu' \frac{V_i}{A_{i,i}})A_i+\mu' V=\lambda_iA_i+\mu V$$$.

$$$(\lambda', \Lambda_i')=(\lambda,\Lambda_i-\lambda\frac{V_i}{A_{i,i}})$$$ satisfies the equation.

Case 3: lines 15 to 23

Let $$$g=\gcd(V_i,A_{i,i})$$$, $$$(s,t)=\texttt{Extended-Euclidean}(V_i,A_{i,i})$$$, $$$A_{i}'=V \times s+A_{i} \times t$$$, $$$V'=V-A_{i}' \frac{V_i}{A_{i,i}'}$$$, $$$W=A_i-A_{i}' \frac{A_{i,i}}{A_{i,i}'}$$$. Note that $$$A_{i,i}'=g$$$.

$$$A_i'=\begin{pmatrix} s & t \end{pmatrix} \cdot \begin{pmatrix} V \\ A_i \end{pmatrix}$$$

$$$V'=\begin{pmatrix} 1-s\frac{V_i}{g} & -t\frac{V_i}{g} \end{pmatrix} \cdot \begin{pmatrix} V \\ A_i \end{pmatrix}$$$

$$$W=\begin{pmatrix} -s\frac{A_{i,i}}{g} & 1-t\frac{A_{i,i}}{g} \end{pmatrix} \cdot \begin{pmatrix} V \\ A_i \end{pmatrix}$$$

We want to find $$$\Lambda_i' A_i'+\lambda'V'+\lambda_w' W=\Lambda_i A_i+\lambda V$$$.

Let $$$M=\begin{pmatrix} s & t \\ 1-s\frac{V_i}{g} & -t\frac{V_i}{g} \\ -s\frac{A_{i,i}}{g} & 1-t\frac{A_{i,i}}{g} \end{pmatrix}$$$

$$$\begin{pmatrix} \Lambda_i' & \lambda' & \lambda_w' \end{pmatrix} M = \begin{pmatrix} \lambda & \Lambda_i \end{pmatrix}$$$

Observe that $$$\begin{pmatrix} \frac{V_i}{g} & 1 & 0 \end{pmatrix} M = \begin{pmatrix} 1 & 0 \end{pmatrix}$$$ and $$$\begin{pmatrix} \frac{A_{i,i}}{g} & 0 & 1 \end{pmatrix} M = \begin{pmatrix} 0 & 1 \end{pmatrix}$$$.

$$$(\Lambda_i', \lambda',\lambda_w')=(\frac{V_i}{g}\lambda+\frac{A_{i,i}}{g}\Lambda_i,\lambda,\Lambda_i)$$$ satisfies the equation.

When $$$A$$$ has all elements set to $$$0$$$, this lemma holds.

Case 1: lines 7 to 11

$$$V$$$ will be changed to $$$\frac{m}{A_{i,i}} V$$$ after the $$$i$$$-th iteration. By corollary 1, we can find $$$\lambda_{i+1}',\lambda_{i+2}',\ldots,\lambda_d'$$$ after $$$\texttt{Add-Vector}$$$ has returned such that $$$\frac{m}{A_{i,i}} V = \sum\limits_{k=i+1}^d \lambda_k' A_k$$$.

Let $$$(s,t)=\texttt{Extended-Euclidean}(V_i,m)$$$.

Since, $$$A_i=V \times s$$$, we have $$$\frac{m}{A_{i,i}} A_i = (\sum\limits_{k=i+1}^d \lambda_k' A_k)s$$$.

Case 2: lines 12 to 14

$$$A_i$$$ does not change. Trivial.

Case 3: lines 15 to 23

$$$\texttt{Add-Vector}(\frac{m}{A_{i,i}}A_i)$$$ is called. Trivial by corollary 1.

We proceed by induction. Let $$$P(z)$$$ be the statement there exists $$$\mu_z, \mu_{z+1}, \ldots,\mu_d \in (\mathbb{Z}/m\mathbb{Z})$$$ such that $$$V=\sum\limits_{k=z}^d \mu_k A_k$$$ then there exists $$$\lambda_z, \lambda_{z+1}, \ldots, \lambda_d \in (\mathbb{Z}/m\mathbb{Z})$$$ such that $$$V=\sum\limits_{k=z}^d \lambda_k A_k$$$ and $$$\lambda_i=0 $$$ if $$$A_{i,i}=0$$$ and $$$0 \leq \lambda_i < \frac{m}{A_{i,i}}$$$ otherwise.

$$$P(d)$$$ is clearly true as $$$A_d ={0,0,\ldots,0,A_{d,d}}$$$ and $$$\frac{m}{A_{d,d}}A_d={0,0,\ldots,0,0}$$$.

Assume $$$P(z+1)$$$ is true where $$$z \geq 1$$$. We will show that this implies that $$$P(z)$$$ is also true. If $$$A_{z,z}=0$$$, it is trivial.

From here, we assume that $$$A_{z,z} \neq 0$$$.

Let $$$V=\sum\limits_{k=z}^d \mu_k A_k$$$ and $$$\mu_{z}=\alpha+\frac{k}{A_{z,z}} \beta$$$ where $$$0 \leq \alpha < \frac{m}{A_{z,z}}$$$.

$$$A_{z}=(0,0,\ldots,0,A_{z,z},A_{z,z+1}, \ldots,A_{z,d})$$$. So $$$\frac{m}{A_{z,z}} A_z=(0,0,\ldots,0,0,\frac{m}{A_{z,z}}A_{z,z+1}, \ldots, \frac{m}{A_{z,z}}A_{z,d})$$$.

By theorem 2, there exists $$$\mu_{z+1}',\mu_{z+2}',\ldots,\mu_d' \in (\mathbb{Z}/m\mathbb{Z})$$$ such that $$$\frac{m}{A_{z,z}} A_z = \sum\limits_{k=z+1}^d \mu_k' A_k$$$.

$$$V=\sum\limits_{k=z}^d \mu_k A_k = \mu_z A_z + \sum\limits_{k=z+1}^d \mu_k A_k = (\alpha+\frac{m}{A_{z,z}} \beta) A_z + \sum\limits_{k=z+1}^d \mu_k A_k= \alpha A_z + \sum\limits_{k=z+1}^d (\mu_k+\beta\mu_k') A_k$$$

Since $$$P(z+1)$$$ is true, we can conclude that there exists $$$\lambda_{z+1}, \lambda_{z+2}, \ldots, \lambda_d \in (\mathbb{Z}/m\mathbb{Z})$$$ such that $$$\sum\limits_{k=z+1}^d (\mu_k+\beta\mu_k') A_k = \sum\limits_{k=z+1}^d \lambda_k A_k$$$ if $$$A_{i,i}=0$$$ and $$$0 \leq \lambda_i < \frac{m}{A_{i,i}}$$$ otherwise.

Since $$$\alpha < \frac{m}{A_{z,z}}$$$, we can conclude that $$$P(z)$$$ is true.

Recall that $$$V \in S$$$ implies that there exists $$$\mu_1, \mu_2, \ldots,\mu_w \in (\mathbb{Z}/m\mathbb{Z})$$$ such that $$$V=\sum\limits_{k=1}^w \mu_i s_i$$$. By theorem 1 and 3, there exists $$$\lambda_1, \lambda_2, \ldots, \lambda_d \in (\mathbb{Z}/m\mathbb{Z})$$$ that satisfies $$$V=\sum\limits_{k=1}^d \lambda_k A_k$$$ and $$$\lambda_i=0 $$$ if $$$A_{i,i}=0$$$ and $$$0 \leq \lambda_i < \frac{m}{A_{i,i}}$$$ otherwise.

There is a greedy way to select $$$\lambda_i$$$ from $$$i=1$$$ to $$$d$$$.

Suppose we are at $$$i=n$$$ and we have already chosen $$$\lambda_1, \lambda_2, \ldots, \lambda_n-1$$$. Consider $$$W=V-\sum\limits_{k=1}^{n-1} \lambda_k A_k$$$. We must pick $$$\lambda_n$$$ such that $$$W_n - \lambda_n A_{n,n}=0$$$. Suppose otherwise, then $$$\sum\limits_{k=1}^d \lambda_k A_{k,n} = \sum\limits_{k=1}^n \lambda_k A_{k,n} \neq V_i$$$ by lemma 2.

Now, we have to find $$$\lambda_n$$$ such that $$$W_n - \lambda_n A_{n,n}=0$$$. Suppose that $$$A_{n,n}=0$$$, then it does not matter what value of $$$\lambda_n$$$ we pick as $$$A_{n,i}=0$$$ for all $$$1 \leq i \leq n$$$ by lemma 3. Suppose otherwise, we can pick $$$\lambda_n = \frac{W_n}{A_{n,n}} < \frac{m}{A_{n,n}}$$$ by lemma 4.

If $$$V \notin S$$$, it is easy to see that $$$\texttt{Inside-Basis}(V)$$$ will return false.

Consider the set $$$\Lambda$$$ of vectors $$$(\lambda_1,\lambda_2, \ldots, \lambda_d) \in (\mathbb{Z}/m\mathbb{Z})^d$$$ such that $$$\lambda_i=0 $$$ if $$$A_{i,i}=0$$$ and $$$0 \leq \lambda_i < \frac{m}{A_{i,i}}$$$ otherwise. It is clear that the size of $$$|\Lambda|=\prod\limits_{k=1}^d c(A_{k,k})$$$ and there is an surjection $$$f$$$ from $$$\Lambda$$$ to the set of representable vectors where $$$f(\lambda_1,\lambda_2, \ldots, \lambda_d) = \sum\limits_{k=1}^d \lambda_k A_k$$$ by theorem 3.

We shall prove that $$$f$$$ is a bijection. We will show that $$$f$$$ is injective. Let $$$V,W \in \Lambda$$$, then we will show that $$$f(V)=f(W) \implies V=W$$$.

We will prove by contrapositive. Suppose that $$$V \neq W$$$, then there exists $$$i$$$ such that $$$V_i \neq W_i$$$, we will choose the minimum $$$i$$$. Consider $$$f(V)-f(W)$$$, $$$(f(V)-f(W))_i=\sum\limits_{k=1}^d (V_k-W_k) A_{k,i}$$$. $$$\sum\limits_{k=1}^{i-1} (V_k-W_k) A_{k,i}=0$$$ since we have chosen the minimum $$$i$$$. $$$\sum\limits_{k=i+1}^d (V_k-W_k) A_{k,i}=0$$$ by lemma 2. Therefore, $$$(f(V)-f(W))_i=(V_i-W_i) A_{i,i}$$$. Since $$$V_i \neq W_i$$$, $$$f(V)-f(W) \neq (0,0,\ldots,0)$$$ and we conclude that $$$f(V) \neq f(W)$$$.

Therefore, $$$f$$$ is a bijection.

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

#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 << ": " << 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());

const int MOD=998244353;

ll q,d,m;
vector<ll> arr[105];

ll fix(ll i){
	i%=m;
	if (i<0) i+=m;
	return i;
}

pair<ll,ll> euclidean(ll a,ll b){ 
	//returns {s,t}
	
	if (b==0) return {1,0};
	else{
		ll x,y;
		tie(x,y)=euclidean(b,a%b);
		return {y,fix(x-(a/b)*y)};
	}
}

void add_vector(vector<ll> v){
	rep(x,0,d) if (v[x]){
		ll s,t;
		if (arr[x][x]==0){
			tie(s,t)=euclidean(v[x],m);
			rep(y,0,d) arr[x][y]=v[y]*s%m;
			ll temp=m/arr[x][x];
			rep(y,0,d) v[y]=v[y]*temp%m;
		}
		else if (v[x]%arr[x][x]==0){
			ll mul=m-(v[x]/arr[x][x]);
			rep(y,0,d) v[y]=(v[y]+arr[x][y]*mul)%m;
		}
		else{
			vector<ll> w=arr[x];
			tie(s,t)=euclidean(v[x],w[x]);
			rep(y,0,d) arr[x][y]=(v[y]*s+w[y]*t)%m;
			ll mul1=m-(v[x]/arr[x][x]),mul2=m-(w[x]/arr[x][x]);
			rep(y,0,d) v[y]=(v[y]+arr[x][y]*mul1)%m;
			rep(y,0,d) w[y]=(w[y]+arr[x][y]*mul2)%m;
			add_vector(w);
			
			vector<ll> v2=arr[x];
			ll mul=m/arr[x][x];
			rep(y,0,d) v2[y]=v2[y]*mul%m;
			add_vector(v2);
		}
	}
}

bool inside(vector<ll> v){
	rep(x,0,d){
		if (arr[x][x]!=0 && v[x]%arr[x][x]==0){
			ll mul=m-(v[x]/arr[x][x]);
			rep(y,0,d) v[y]=(v[y]+arr[x][y]*mul)%m;
		}
		if (v[x]) return false;
	}
	return true;
}

vector<ll> largest(){
	vector<ll> res(d,0);
	rep(x,0,d) if (arr[x][x]){
		ll mul=(m-1-res[x])/arr[x][x];
		rep(y,0,d) res[y]=(res[y]+arr[x][y]*mul)%m;
	}
	return res;
}

ll count(){
	ll res=1;
	rep(x,0,d) if (arr[x][x]){
		res=(res*(m/arr[x][x]))%MOD;
	}
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>q>>d>>m;
	
	rep(x,0,d) arr[x]=vector<ll>(d,0);
	
	int a;
	vector<ll> v(d);
	while (q--){
		cin>>a;
		
		if (a<=2) rep(x,0,d) cin>>v[x];
		
		if (a==1){
			add_vector(v);
		}
		else if (a==2){
			cout<<inside(v)<<endl;
		}
		else if (a==3){
			v=largest();
			rep(x,0,d) cout<<v[x]<<" "; cout<<endl;
		}
		else{
			cout<<count()<<endl;
		}
	}
}

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

const int MOD=1000000007;

int n,k;
int memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	rep(x,n+1,1) if (k>=x) rep(y,k+1,x){
		assert(y-x>=0);
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

const int MOD=1000000007;

int n,k;
int memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	rep(x,n+1,1) if (k>=x) rep(y,k+1,x){
		//assert(y-x>=0);
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

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

//#pragma GCC optimize("O3")

const int MOD=1000000007;

int n,k;
int memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	for (int x=n;x>=1;x--) for (int y=k;y>=x;y--){
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

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

#pragma GCC optimize("O3")

const int MOD=1000000007;

int n,k;
int memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	for (int x=n;x>=1;x--) for (int y=k;y>=x;y--){
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

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

#pragma GCC optimize("O3")

const int MOD=1000000007;

int n,k;
long long memo[5005];

int main(){
	cin>>n>>k;
	
	memo[k]=1;
	
	for (int x=n;x>=1;x--) for (int y=k;y>=x;y--){
		memo[y-x]=(memo[y-x]+memo[y])%MOD;
	}
	
	cout<<memo[0]<<endl;
}

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 < 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<j$$$ and $$$c_i<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<i$$$) such that $$$c_k<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<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<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]>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<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]<p[b]<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 > p[b]-p[a]$$$ or $$$n-p[b] > p[b] - p[a]$$$ (WLOG assuming $$$p[b] > 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]<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}| > 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>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>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<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) < 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 > A_Y$$$, but since $$$A_X > B_X$$$ and $$$A_Y > B_Y$$$, we get that $$$B_Y < A_X$$$. As such, $$$X$$$ cannot be RED.

For $$$Z$$$, we have $$$C_X < A_Z$$$ (since X lost to Z) and $$$B_X < C_X$$$, we hence have $$$B_X < 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} < A_{r}$$$ where $$$nr$$$ is any BLUE or GREEN
2. The game ends. This occurs when $$$B_{g} > 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;
		}
	}
	
}