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


int main() {

    #ifdef ABHISHEK_SRIVASTAVA
        freopen("Input.txt", "r", stdin);
        freopen("Output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n, k, curr = 1, cost = 0;
        cin >> n >> k;
        bool change = 0;
        while (k > 0) {
            k--;
            cost += curr;
            if (change)
                curr++;
            change = 1 - change;            
        }
        cout << cost << '\n';
    }

    return 0;

}

• For $$$k=0$$$, we don't color any cell;

• For $$$k=1$$$, we color cell $$$(1,1)$$$;

• For $$$k=2$$$, we color cells $$$(1,1),(n,n)$$$;

• For $$$k=3$$$, we color cells $$$(1,1),(n,n),(1,2),(2,1)$$$;

• For $$$k=4$$$, we color cells $$$(1,1),(n,n),(1,2),(2,1),(n-1,n),(n,n-1)$$$;

• $$$\ldots$$$

#include<bits/stdc++.h>
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
vector<int> v[200010];
int a[200010]; 
void solve(){
	int n,m,po=-1,ans=1,b;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
		v[a[i]].clear();
	}
	for(int i=0;i<m;i++){
		cin>>b;
		v[b].eb(i);
	}
	for(int i=0;i<n;i++){
		if(!v[a[i]].size()){
			cout<<"-1\n";
			return;
		}
		int p=upper_bound(v[a[i]].begin(),v[a[i]].end(),po)-v[a[i]].begin();
		if(p==v[a[i]].size()){
			po=v[a[i]][0];
			ans++;
		}
		else po=v[a[i]][p];
	}
	cout<<ans<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

We use vectors $$$pos_i$$$ to represent all positions (in increasing order) of elements with value $$$i$$$ in array $$$b$$$.

Let's start from $$$a_1$$$. We can greedily choose the smallest $$$p$$$ such that $$$b_p = a_1$$$, and match $$$a_1$$$ with $$$b_p$$$.

Assume we have matched $$$a_{1,2, \dots ,i}$$$, and $$$p$$$ satisfies $$$a_i = b_p$$$.

Next, we want to match $$$a_{i+1}$$$. Again, we can greedily choose $$$pos_{a_{i+1}}.\text{upper_bound}(p)$$$. If there is no such $$$p$$$, then $$$ans++$$$, and $$$p = pos_{a_{i+1}}.\text{head()}$$$.

The case with no solution can be easily determined using the above method.

#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int mod=998244353;
//give sin(),cos() radian, and asin(),acos() gives you radian
void solve(){
	ll n,ans=1,sum,p;
	cin>>n;
	if(n%2){
		sum=8;
		p=3;
	}
	else{
		sum=4;
		p=2;
	}
	for(ll i=n/2;i>0;i--){
		ans*=sum;
		ans%=mod;
		sum--;
		ans*=sum;
		ans%=mod;
		sum--;
		sum+=((2*p)+2)*2;
		sum%=mod;
		p+=2;
	}
	cout<<ans<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

Consider $$$m = 1, 2, \ldots, \left\lfloor \frac{n}{2} \right\rfloor$$$(Here area $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ refers to the rectangular region with ($$$x_1$$$,$$$y_1$$$) as the top-left corner and ($$$x_2$$$,$$$y_2$$$) as the bottom-right corner ).

• $$$1$$$ can be put anywhere;

• $$$2$$$ can be covered by at most $$$4$$$ submatrices. To achieve the maximum, it can only be put in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$;

• $$$3$$$ can be covered by at most $$$9$$$ submatrices. To achieve the maximum, it can only be put in area $$$(3,3)$$$ to $$$(n-2,n-2)$$$;

• $$$\ldots$$$

Consider $$$m = n, n-1, \ldots, \left\lfloor \frac{n}{2} \right\rfloor + 1$$$.

• $$$n$$$ can be put anywhere;

• Consider $$$(n-1)$$$. The intersection of all $$$(n-1) \times (n-1)$$$ submatrices is in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$ so it can only be put in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$;

• $$$(n-2)$$$ can only be put in area $$$(3,3)$$$ to $$$(n-2,n-2)$$$;

• $$$\ldots$$$

Afterward, the problem transforms into a classic counting problem. We start placing numbers within a central $$$k \times k$$$ matrix (if $$$n$$$ is odd, $$$k=1$$$; otherwise $$$k=2$$$); subsequently, numbers are placed within a $$$(k+2) \times (k+2)$$$ matrix centered around the previous one, and so on.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
vector<vector<ll>> adj,vv;
vector<ll> a,comp;

void dfs(ll x, ll p, ll val){
    for(auto i:adj[x]){
        if(i!=p){
            dfs(i,x,val);
            if(a[i]==a[x] && a[i]==val && comp[i]!=comp[x]){
                ll xxx=comp[i];
                for(auto j:vv[comp[i]]){
                    vv[comp[x]].push_back(j);
                    comp[j]=comp[x];
                }
                vv[xxx].clear();
                for(auto j:vv[comp[x]]){
                    a[j]=2*a[j];
                }
            }
        }
    }
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        a.clear();
        a.resize(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        ll mini=*min_element(a.begin(),a.end());
        bool ok=true;
        for(ll i=0;i<n;i++){
            if(a[i]%mini!=0) ok=false;
            a[i]=a[i]/mini;
        }
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        if(!ok) cout<<"NO\n";
        else{
            comp.clear();
            comp.resize(n);
            for(ll i=0;i<n;i++) comp[i]=i;
            vv.clear();
            vv.resize(n);
            for(ll i=0;i<n;i++) vv[i].push_back(i);
            ll i=1;
            while(i<=1e9){
                dfs(0,-1,i);
                i=i*2;
            }
            ll cnt=count(a.begin(),a.end(),a[0]);
            if(cnt==n) cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=200010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
int a[N],fa[N];
ll sum[N];
vector<int>  v;
vector<int>  G[N];
unordered_map<int,int> del[N];

void DFS(int x,int pr)
{
	v.push_back(x); 
	fa[x]=pr;
	sum[x]=a[x];
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(y==pr||del[x][y]) continue;
		DFS(y,x);
		sum[x]+=sum[y];
	}
}

int split(int x)
{
	v.clear();
	DFS(x,0);
	int y=0;
	if(v.size()==1) return 1;
	for(int i=0;i<v.size();i++) if(2*sum[v[i]]==sum[x]) y=v[i];
	if(y)
	{
		del[y][fa[y]]=del[fa[y]][y]=1;
		return 1;
	}
	else return 0;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) G[i].clear(),del[i].clear();		
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		int flg=1;
		for(int i=1;i<LOGN;i++){
			for(int j=1;j<=n;j++){
			    flg&=split(j);
			    if(!flg) break;
			}
		}
		printf("%s\n",flg?"YES":"NO");
	}
	
	return 0;
}

By observation, we can see that all values are in the form of $$$x \cdot 2^k$$$ (if not, then there is definitely no solution). For convenience, we convert all values to the form of $$$2^k$$$.

We consider each $$$k$$$ from small to large. We arbitrarily choose a root node for DFS. For a fixed $$$k$$$, if a node $$$x$$$ has a value of $$$2^k$$$ and it has the maximum depth, $$$x$$$ can only merge with its parent, otherwise there is definitely no solution. We only need to bruteforce merge $$$x$$$ with its parent.

What is the complexity?

Consider each edge. If an edge is involved in the merge process, the value of one endpoint of the edge will double. So, one edge can be merged up to $$$2\log n$$$ times.

The total time complexity is $$$O(n \log n)$$$.

Use reverse thinking.

Let's denote the sum of all node values as $$$sum$$$. The last step of merging must be to merge two nodes with values of $$$\frac{sum}{2}$$$.

This implies that there must be a subtree in the original tree with a sum of $$$\frac{sum}{2}$$$, regardless of which node we choose as the root.

We choose any node as the root and find the node $$$x$$$ with a subtree sum of $$$\frac{sum}{2}$$$. We then remove the edge between $$$x$$$ and its parent.

For the subtrees obtained after splitting, we recursively solve the problem on these subtrees, until there's no edges in this graph.

The total time complexity is $$$O(n \log n)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,q;
ll   ans;
char s[N];
int  S[N];
set<int> ST[N];

//---------------------------------------------------------- 
//Segtree 1 

struct nod
{
	int l,r,mn;
	nod *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree() {}
	
	void init()
	{
		build(&root,0,n,S);
	}
	
	void newnod(nod **p,int l,int r)
	{
		*p=new nod;
		(*p)->l=l;(*p)->r=r;(*p)->mn=0;
		(*p)->lc=(*p)->rc=NULL;
	}

	void build(nod **p,int L,int R,int x[])
	{
		newnod(p,L,R);
		if(L==R)
		{
			(*p)->mn=x[L];
			return ;
		}
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M,x);
		build(&(*p)->rc,M+1,R,x);
		(*p)->mn=min((*p)->lc->mn,(*p)->rc->mn);
	}
	
	void add(int x,int v)
	{
		_add(root,x,v);
	}
	
	void _add(nod *p,int x,int v)
	{
		if(p->l==p->r)
		{
			p->mn+=v;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(x<=M)     _add(p->lc,x,v);
		else 		 _add(p->rc,x,v);
		p->mn=min(p->lc->mn,p->rc->mn);
	}
	
	int querymn(int L,int R)
	{
		return _querymn(root,L,R);
	}
	
	int _querymn(nod *p,int L,int R)
	{
		if(p->l==L&&p->r==R) return p->mn;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _querymn(p->lc,L,R);
		else if(L>M) return _querymn(p->rc,L,R);
		else return min(_querymn(p->lc,L,M),_querymn(p->rc,M+1,R));
	}
}TR;

//---------------------------------------------------------- 

//---------------------------------------------------------- 
//Segtree 2

struct Dnod
{
	int l,r,sum;
	Dnod *lc,*rc;
};

struct Dynamic_Segtree
{
	Dnod *root;
	
 	Dynamic_Segtree() 
	{
		root=NULL;
	}
	
	void newnod(Dnod **p,int l,int r)
	{
		*p=new Dnod;
		(*p)->l=l;(*p)->r=r;(*p)->sum=0;
		(*p)->lc=(*p)->rc=NULL;
	}

	void add(int p,int v)
	{
		_add(&root,0,n,p,v);
	}
	
	void _add(Dnod **p,int L,int R,int pos,int val)
	{
		if(*p==NULL) newnod(p,L,R);
		if(L==R)
		{
			(*p)->sum+=val;
			return ;
		}
		int M=(L+R)>>1;
		if(pos<=M) _add(&(*p)->lc,L,M,pos,val);
		else       _add(&(*p)->rc,M+1,R,pos,val);
		(*p)->sum=0;
		if((*p)->lc!=NULL) (*p)->sum+=(*p)->lc->sum;
		if((*p)->rc!=NULL) (*p)->sum+=(*p)->rc->sum;
	}
	
	int getsum(int L,int R)
	{
		return _getsum(root,L,R);
	}
	
	int _getsum(Dnod *p,int L,int R)
	{
		if(p==NULL) return 0;
		if(p->l==L&&p->r==R) return p->sum;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _getsum(p->lc,L,R);
		else if(L>M) return _getsum(p->rc,L,R);
		else return _getsum(p->lc,L,M)+_getsum(p->rc,M+1,R);
	}
}DT[N];

//---------------------------------------------------------- 

int LBS(int pos,int val)
{
	int L=-1,R=pos,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(TR.querymn(M,pos)<val) L=M;
		else R=M;
	}
	return R;
}

int RBS(int pos,int val)
{
	int L=pos,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(TR.querymn(pos,M)<val) R=M;
		else L=M;
	}
	return L;
}

int countk(int l,int r,int k)
{
	return DT[k+n].getsum(l,r);
}

int main()
{
	scanf("%d%d%s",&n,&q,s);
	for(int i=1;i<=n;i++) S[i]=S[i-1]+(s[i-1]=='('?1:-1);
	TR.init();
	for(int i=0;i<=n;i++) DT[S[i]+n].add(i,1);
	for(int i=1;i<=n;i++)
		ans+=countk(LBS(i,S[i]),i,S[i])-1;
	for(int i=1;i<=q;i++)
	{
		int p;
		scanf("%d",&p);
		if(s[p-1]==s[p]) 
		{
			printf("%I64d%c",ans,i==q?'\n':' ');
			continue;
		}
		swap(s[p-1],s[p]);
		if(s[p]==')')	
		{
			int l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans-=(L+R);
			DT[S[p]+n].add(p,-1);
			S[p]+=2;
			TR.add(p,2);
			DT[S[p]+n].add(p,1);
			l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans+=(ll)L*R;
			l=LBS(p,S[p]-1),r=RBS(p,S[p]-1),L=countk(l,p,S[p]-1),R=countk(p,r,S[p]-1);
			ans+=(ll)L*R;
		}
		else
		{
			int l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans-=(ll)L*R;
			l=LBS(p,S[p]-1),r=RBS(p,S[p]-1),L=countk(l,p,S[p]-1),R=countk(p,r,S[p]-1);
			ans-=(ll)L*R;
			DT[S[p]+n].add(p,-1);
			S[p]-=2;
			TR.add(p,-2);
			DT[S[p]+n].add(p,1);
			l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans+=(L+R);
		}
		printf("%I64d%c",ans,i==q?'\n':' ');
	}

	return 0;
}

Note $$$S$$$ as the prefix sum of $$$s$$$ (consider '(' as $$$1$$$ and ')' as $$$-1$$$). Firstly, we can easily calculate the initial answer $$$ans$$$.

We can see substring $$$s_{l+1,...,r}$$$ is regular if and only if $$$S_{l}==S_{r}$$$ and $$$\min(S_{l},...,S_{r})=S_{r}$$$.

Let’s see how swapping influences $$$S$$$ and $$$ans$$$.

①If we swap "()",then $$$S_{p_i} -= 2$$$, and $$$s_{l+1,...,r}$$$ will become irregular from regular if

• $$$l < p_i < r$$$;

• $$$S_{l} = S_{r} = S_{p_i} + 2$$$, or $$$S_{l} = S_{r} = S_{p_i} + 1$$$ (here $$$S_{p_i}$$$ has been subtracted by $$$2$$$);

• Before swapping, $$$\min(S_{l},...,S_{r}) = S_{l} = S_{r}$$$.

② If we swap ")(",then $$$S_{p_i} += 2$$$, and $$$s_{l+1,...,r}$$$ will become regular from irregular if

• $$$l < p_i < r$$$;

• $$$S_{l} = S_{r} = S_{p_i}$$$, or $$$S_{l} = S_{r} = S_{p_i} - 1$$$ (here $$$S_{p_i}$$$ has been added by $$$2$$$);

• After swapping, $$$\min(S_{l},...,S_{r}) = S_{l} = S_{r}$$$.

We can use binary search+segtree to maintain $$$S$$$ and update $$$ans$$$.

In addition, we find regular $$$s_{x,...,p_i}$$$ and $$$s_{p_i,...,y}$$$ similarly after each swap.

To achieve the above operations, we need to maintain two data structures that support the following operations:

1. Single Point modification;

2. Range minimum value query;

3. Query how many numbers in a range are equal to $$$k$$$.

Operations 1 and 2 can be done by using a common segment tree. For operation 3, we build $$$n$$$ dynamic segment trees $$$DT_{value}$$$ for all values.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,q;
int a[N],x[N],pre_height[N],suf_height[N];
vector<pair<int,int> > pr;

//---------------------------------------------------------------------
//ST-Table Template

int lg2[N];
int mn[N][LOGN],mnpos[N][LOGN];

void build_ST()
{
	for(int i=1;i<=n;i++) lg2[i]=(int)log2(i);
	for(int i=1;i<=n;i++) mn[i][0]=pr[i].second,mnpos[i][0]=i;
	for(int i=1;i<LOGN;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int p=j+(1<<(i-1));
			if(p>n) mn[j][i]=mn[j][i-1],mnpos[j][i]=mnpos[j][i-1];
			else    
			{
				mn[j][i]=min(mn[j][i-1],mn[p][i-1]);
				mnpos[j][i]=(mn[j][i-1]<mn[p][i-1])?mnpos[j][i-1]:mnpos[p][i-1];
			}
		}
	}
}

int getmin(int L,int R)
{
	int t=lg2[R-L+1];
	return min(mn[L][t],mn[R-(1<<t)+1][t]);
} 

int getminpos(int L,int R)
{
	int t=lg2[R-L+1];
	return mn[L][t]<mn[R-(1<<t)+1][t]?mnpos[L][t]:mnpos[R-(1<<t)+1][t];
} 
//---------------------------------------------------------------------

//---------------------------------------------------------------------
//Euler Sequence Template
int cnt;
int fa[N],dep[N],inid[N],ouid[N],euler_seq[N];
vector<int> G[N];

void DFS(int x,int pr)
{
	fa[x]=pr;
	dep[x]=dep[fa[x]]+1;
	inid[x]=(++cnt);
	euler_seq[inid[x]]=x;
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(y==fa[x]) continue;
		DFS(y,x);
	}
	ouid[x]=(++cnt);
	euler_seq[ouid[x]]=x;
}
//---------------------------------------------------------------------

//---------------------------------------------------------------------
//Segtree Template

struct nod
{
	int l,r,mx,tag;
	nod *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree(int sz,int x[])
	{
		build(&root,1,sz,x);
	}
	
	void newnod(nod **p,int l,int r)
	{
		*p=new nod;
		(*p)->l=l;(*p)->r=r;(*p)->mx=(*p)->tag=0;
		(*p)->lc=(*p)->rc=NULL;
	}
	
	void pushdown(nod *p)
	{
		if(p->tag)
		{
			p->mx+=p->tag;
			if(p->l!=p->r) p->lc->tag+=p->tag,p->rc->tag+=p->tag;
			p->tag=0;
		}
	}
	
	void build(nod **p,int L,int R,int x[])
	{
		newnod(p,L,R);
		if(L==R)
		{
			(*p)->mx=dep[x[L]];	
			return ;
		}
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M,x);
		build(&(*p)->rc,M+1,R,x);
		(*p)->mx=max((*p)->lc->mx,(*p)->rc->mx);
	}
	
	void add(int L,int R,int v)
	{
		modify(L,R,v);
	}
	
	void modify(int L,int R,int v)
	{
		_modify(root,L,R,v);
	}
	
	void _modify(nod *p,int L,int R,int v)
	{
		pushdown(p);
		if(p->l==L&&p->r==R)
		{
			p->tag=v;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(R<=M)     _modify(p->lc,L,R,v);
		else if(L>M) _modify(p->rc,L,R,v);
		else
		{
			_modify(p->lc,L,M,v);
			_modify(p->rc,M+1,R,v);
		}
		pushdown(p->lc);
		pushdown(p->rc);
		p->mx=max(p->lc->mx,p->rc->mx);
	}
	
	int getmax(int L,int R)
	{
		return _querymx(root,L,R);
	}
	
	int _querymx(nod *p,int L,int R)
	{
		pushdown(p);
		if(p->l==L&&p->r==R) return p->mx;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _querymx(p->lc,L,R);
		else if(L>M) return _querymx(p->rc,L,R);
		else return max(_querymx(p->lc,L,M),_querymx(p->rc,M+1,R));
	}
};

//---------------------------------------------------------------------

void input()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=q;i++) scanf("%d",&x[i]);
	pr.clear();
	pr.push_back(make_pair(0,0));
	for(int i=1;i<=n;i++) pr.push_back(make_pair(a[i],i));
	sort(pr.begin(),pr.end());
}

void cal_fa(int L,int R,int FA)
{
	if(L>R) return ;
	int p=getminpos(L,R);
	fa[pr[p].second]=FA;
	cal_fa(L,p-1,pr[p].second);
	cal_fa(p+1,R,pr[p].second);
}

void build_tree()
{
	for(int i=1;i<=n;i++) G[i].clear();
	cal_fa(1,n,0);
	for(int i=2;i<=n;i++)
		G[i].push_back(fa[i]),G[fa[i]].push_back(i);
	cnt=0;	
	DFS(1,0);
}

void cal_pre()
{
	Segtree TR(2*n,euler_seq);
	for(int i=n;i;i--)
	{
		pre_height[i]=TR.getmax(1,2*n);
		int t=pr[i].second;
		TR.add(inid[t],inid[t],-n);
		TR.add(ouid[t],ouid[t],-n);
		TR.add(inid[t],ouid[t],-1);
	}
}

void cal_suf()
{
	Segtree TR(2*n,euler_seq);
	for(int i=1;i<=n;i++)
	{
		suf_height[i]=TR.getmax(1,2*n);
		int t=pr[i].second;
		TR.add(inid[t],inid[t],-n);
		TR.add(ouid[t],ouid[t],-n);
		TR.add(inid[t],ouid[t],-1);
	}
}

void solve()
{
	for(int i=1;i<=q;i++)
	{
		int L=0,R=n+1,M;
		while(L+1!=R)
		{
			M=(L+R)>>1;
			if(pr[M].first<x[i]) L=M;
			else R=M;
		}
		if(L==0) printf("%d",suf_height[1]);
		else if(L==n) printf("%d",pre_height[n]);
		else printf("%d",max(pre_height[L],suf_height[R]));
		printf("%c",i==q?'\n':' ');
	}
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
	 	input();
	 	build_ST();
	 	build_tree();
	 	cal_pre();
	 	cal_suf();
	 	solve();
	}
	
	return 0;
}

First sort $$$a_{1,\ldots,n}$$$ (let's call it $$$b_{1,\ldots,n}$$$).

For a fixed $$$x_j$$$, let's say $$$b_i < x_j < b_{i+1}$$$. The answer is $$$\max(\text{tree_height}(b_{1, \ldots ,i}), \text{tree_height}(b_{i+1, \ldots ,n})) + 1$$$. Here, $$$\text{tree_height}(b_{1,\ldots ,i})$$$ represents the height of the BST corresponding to $$$b_{1,\ldots,i}$$$ (the insertion order is based on their occurrence order in $$$a$$$).

So we want to get the $$$\text{tree_height}(b_{1,\ldots,i})$$$ for $$$1 \leq i \leq n$$$, and $$$\text{tree_height}(b_{i+1,\ldots,n})$$$ similarly.

At first,we can build the BST for $$$b_{1,\ldots,n}$$$ and its Euler sequence as well.

void cal_fa(int L,int R,int FA)
{
	if(L>R) return ;
	int p=getminpos(L,R);
	fa[pr[p].second]=FA;
	cal_fa(L,p-1,pr[p].second);
	cal_fa(p+1,R,pr[p].second);
}

Then we delete one node for each step. When we want to delete node $$$x$$$, we set $$$\text{dep}_x = 0$$$ and subtract $$$1$$$ in the subtree of $$$x$$$. This approach is based on classical Euler sequence and segment tree.

The total complexity is $$$O(n \log n)$$$.

If you think in terms of $$$k$$$, it might be hard to find the solution. Maybe it will be helpful if you fix $$$d$$$ and find the $$$k$$$ which will be swapped with $$$d$$$.

Try bruteforcing for, say, $$$n \le 20$$$. Do you see a pattern?

On $$$n=1$$$, the answer is trivially $$$1$$$.

On $$$n=2$$$, index $$$1$$$ and $$$2$$$ are swapped. The answer is therefore $$$2$$$.

For $$$n>2$$$, let us assume the element $$$1$$$ is on index $$$a$$$ and it will be swapped with index $$$k$$$. Then, $$$a$$$ must be $$$k/2$$$. We will prove this by contradiction. Let us assume that there is no divisor greater than $$$a$$$, and $$$a$$$ is lesser than $$$k/2$$$. But then, as $$$a$$$ is a multiple of $$$2$$$ in the base condition, $$$k$$$ must be a multiple of $$$2$$$, and $$$k/2$$$ is a divisor of $$$k$$$. This contradicts the assumption. By induction we can see that $$$a$$$ is always a multiple of $$$2$$$, and this proof will always hold. The element $$$1$$$ will move only when $$$k/2=a$$$.

Therefore, we can find the largest value of $$$v$$$ such that $$$2^v \le n$$$. The answer turns out to be $$$2^v$$$.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    ll q;cin>>q;
    while(q--)
    {
        ll n,p=1;cin>>n;
        while(p*2<=n)p<<=1;
        cout<<p<<"\n";
    }
}

Let’s call path $$$(1,1) \rightarrow \ldots \rightarrow (1,i)\rightarrow(2,i) \rightarrow \ldots \rightarrow (2,n)$$$ the $$$i$$$-th path. What's the difference between the $$$i$$$-th path and the $$$(i+1)$$$-th path?

What if $$$a_{2i}=1$$$ and $$$a_{1(i+1)}=0$$$ ?

What if $$$a_{2i}=0$$$ and $$$a_{1(i+1)}=1$$$ ?

• Let the string achieved by moving down on the $$$i$$$-th column be $$$S_i$$$. Then, for any $$$1 \le k < n$$$, one can observe that $$$S_k$$$ and $$$S_{k+1}$$$ can only differ by at most one index, which is index $$$k+1$$$. Thus, comparing $$$S_k$$$ and $$$S_{k+1}$$$ lexicographically can be done in $$$O(1)$$$, by comparing this one index.

• After finding the lexicographically smallest string, counting the occurrence of this string can be done straightforwardly in $$$O(n)$$$.

• The implementation can differ for each participant, but the following method provides a clean implementation. Let the initial coordinate be $$$(1,1)$$$, and maintain a counter which is initially reset to $$$1$$$. Then repeat the following until we reach $$$(2,n)$$$:

1. If we are on row $$$2$$$, move to the right.
2. If we are on column $$$n$$$, move downwards.
3. From here, let the character on the right be $$$a$$$, and one below be $$$b$$$.
4. If $$$a>b$$$, move downwards.
5. If $$$a<b$$$, move to the right and reset the counter to $$$1$$$.
6. If $$$a=b$$$, move to the right and increment the counter.

• In the end, the string on the path we passed through will be lexicographically smallest, and the integer on the counter will be the number of occurrences.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n;
char a[3][N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	        scanf("%d",&n);
		for(int i=1;i<=2;i++)
		{
		    scanf("\n");
			for(int j=1;j<=n;j++)
				scanf("%c",&a[i][j]);
		}
		int max_down=n,min_down=1;
		for(int i=n;i>=2;i--)
			if(a[1][i]=='1'&&a[2][i-1]=='0') max_down=i-1;
		for(int i=1;i<max_down;i++)
			if(a[2][i]=='1'&&a[1][i+1]=='0') min_down=i+1;
		for(int i=1;i<=max_down;i++) printf("%c",a[1][i]);
		for(int i=max_down;i<=n;i++) printf("%c",a[2][i]);
		printf("\n");
		printf("%d\n",max_down-min_down+1);
	}
	
	return 0;
}

What's the maximum value of $$$p_i \oplus p_j$$$?

How to get $$$i$$$, such that $$$p_i = n-1$$$?

How to get $$$j$$$, such that $$$p_i \oplus p_j$$$ reaches the maximum value?

Step1:do queries $$$? \ x \ x \ y \ y$$$ like classic searching for the maximum value among $$$n$$$ numbers to get $$$p_i= n-1$$$;

Step2:do queries $$$? \ x \ i \ y \ i$$$ to find all index $$$k$$$ such that $$$p_i | p_{k}$$$ reaches the maximum value. We store all such indexes in a vector $$$id$$$ .

Step3:do queries $$$? \ id[x] \ id[x] \ id[y] \ id[y]$$$ to find $$$j$$$ in $$$id$$$ such that $$$p_j$$$ reaches the minimum value.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;

char query(int a,int b,int c,int d)
{
	char x;
	printf("? %d %d %d %d\n",a,b,c,d);
	fflush(stdout);
	cin>>x;
	fflush(stdout);
	return x;
}

int main()
{	
	scanf("%d",&T);
	while(T--)
	{
    	        scanf("%d",&n);
		int mx=0,ans1=0,ans2;
		vector<int> v;
		for(int i=1;i<n;i++)
		{
			int c=query(ans1,ans1,i,i);
			if(c=='<') ans1=i;
		}
		v.push_back(0);
		for(int i=1;i<n;i++)
		{
			int c=query(mx,ans1,i,ans1);
			if(c=='<')
			{
			    mx=i;
			    v.clear();
			    v.push_back(i);
			}
			else if(c=='=') v.push_back(i);
		}
		ans2=v[0];
		for(int i=1;i<v.size();i++)
		{
			int c=query(ans2,ans2,v[i],v[i]);
			if(c=='>') ans2=v[i];
		}
		printf("! %d %d\n",ans1,ans2);
		fflush(stdout);
	}
	
	return 0;
}

Observe: which cells actually change the direction of the pinball placed at position $$$p$$$ initially?

These cells are the $$$>$$$ to the left of $$$p$$$ and the $$$<$$$ to the right of $$$p$$$. Can you see the trace of the pinball?

How to quickly calculate the time when a pinball leaves the grid?

We observe that, in fact, only the $$$>$$$ to the left of $$$p$$$ and the $$$<$$$ to the right of $$$p$$$ change the direction of the pinball placed at position $$$p$$$ initially.

For convenience, let's assume $$$s_p$$$ is $$$>$$$, $$$k=min(countright(1,p),countleft(p+1,n))$$$, and the pinball leaves from the left boundary(for other situations, we can handle them in a similar way).

We can obtain $$$right[1,\ldots,k]$$$ and $$$left[1,\ldots,k]$$$ through prefix sum + binary search, where $$$right$$$ represents the indices of $$$>$$$ to the left of $$$p$$$ (in decreasing order), and $$$left$$$ represents the indices of $$$<$$$ to the right of $$$p$$$ (in increasing order).

We use $$$right$$$ and $$$left$$$ to describe the trace of the pinball:

The first segment: the pinball moves from $$$right_1$$$ to $$$left_1$$$;

The second segment: the pinball moves from $$$left_1$$$ to $$$right_2$$$;

The third segment: the pinball moves from $$$right_2$$$ to $$$left_3$$$;

$$$\ldots$$$

The $$$2k$$$-th segment: the pinball moves from $$$left_k$$$ to the left boundary.

It is not difficult to observe that we can use prefix sum to store the sum of indices, and then quickly calculate the time when the pinball moves.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n;
ll   Sl[N],Sr[N],IDl[N],IDr[N];
char s[N];

int findpre(int x)
{
	int L=0,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(Sr[M]<x) L=M;
		else R=M; 
	}
	return R;
}

int findsuf(int x)
{
	int L=0,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(Sl[n]-Sl[M-1]<x) R=M;
		else L=M; 
	}
	return L;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	        scanf("%d%s",&n,s);
		for(int i=1;i<=n;i++) 
		{
	  	  Sr[i]=Sr[i-1]+(s[i-1]=='>');
	  	  Sl[i]=Sl[i-1]+(s[i-1]=='<');
 		  IDr[i]=IDr[i-1]+i*(s[i-1]=='>'); 	
 		  IDl[i]=IDl[i-1]+i*(s[i-1]=='<'); 	
		}		
		for(int i=1;i<=n;i++)
		{
			if(s[i-1]=='>')
			{
				if(Sr[i]>Sl[n]-Sl[i])
				{
					int p=findpre(Sr[i]-(Sl[n]-Sl[i]));
					printf("%I64d ",2*((IDl[n]-IDl[i])-(IDr[i]-IDr[p-1]))+i+(n+1));
				}
				else
				{
					int p=findsuf((Sl[n]-Sl[i])-Sr[i]+1);
					printf("%I64d ",2*((IDl[p]-IDl[i])-(IDr[i]-IDr[0]))+i);
				}
			}
			else
			{
				if(Sr[i]>=Sl[n]-Sl[i-1])
				{
					int p=findpre(Sr[i]-(Sl[n]-Sl[i-1])+1);
					printf("%I64d ",2*((IDl[n]-IDl[i-1])-(IDr[i]-IDr[p-1]))-i+(n+1));
				}
				else
				{
					int p=findsuf((Sl[n]-Sl[i-1])-Sr[i]);
					printf("%I64d ",2*((IDl[p]-IDl[i-1])-(IDr[i]-IDr[0]))-i);
				}
			}
		}
		printf("\n");
	}
	
	return 0;
}

In fact, you don't need to hire the same Pokemon more than once.

Consider graph building.

How to reduce the number of edges in the graph?

Let's consider $$$n$$$ Pokémon as nodes, and defeating Pokémon $$$u$$$ by Pokémon $$$v$$$ as the edge $$$u \rightarrow v$$$. Then the problem is essentially finding the shortest path from $$$n$$$ to $$$1$$$.

If we brute force to construct the graph, the time complexity will be $$$O(n^2m)$$$, which is unacceptable. How can we find a better way to build the graph?

Recalling, we need to represent all processes like "Pokémon $$$u$$$ increased attribute $$$x$$$ by some value and defeated Pokémon $$$v$$$" using paths in the graph.

We will use the following graph building to achieve this. Overall, we consider each attribute separately. For the $$$x$$$-th attribute, we construct $$$2n$$$ virtual nodes $$$X_1,...,X_n$$$ and $$$Y_1,...,Y_n$$$, and connect each Pokémon based on the $$$x$$$-th attribute.

For example, $$$n=3$$$ and $$$a_{1,1}=9, a_{2,1}=6, a_{3,1}=1$$$, we have the following graph building for attribute $$$1$$$:

In this graph,for example,"Pokémon $$$3$$$ increased attribute $$$1$$$ by $$$8$$$ and defeated Pokémon $$$1$$$" can be represented as path $$$3 \rightarrow X1 \rightarrow X2 \rightarrow X3 \rightarrow Y3 \rightarrow 1$$$.

More generally, our graph building method is :

• Consider each attribute separately. Assuming we are processing the $$$i$$$-th attribute, insert all $$$a_{1,i} , \ldots ,a_{n,i}$$$ into $$$val$$$ and sort it (for convenience, we assume that they are pairwise different).

• Construct $$$2n$$$ virtual nodes $$$X_1,...,X_n$$$ and $$$Y_1,...,Y_n$$$;

• Add edge $$$X_i \rightarrow X_{i+1}$$$ with a value of $$$(val_{i+1}-val_i)$$$ for $$$1 \le i < n$$$;

• Add edge $$$Y_{i+1} \rightarrow Y_{i}$$$ with a value of $$$0$$$ for $$$1 \le i < n$$$;

• Add edge $$$X_i \rightarrow Y_{i}$$$ with a value of $$$0$$$ for $$$1 \le i \le n$$$;

• Add edge $$$i \rightarrow X_{rank_i}$$$ with a value of $$$c_i$$$ for $$$1 \le i \le n$$$;

• Add edge $$$Y_{rank_i} \rightarrow i$$$ with a value of $$$0$$$ for $$$1 \le i \le n$$$.

Then we just run Dijkstra algorithm in this graph. The time complexity is $$$O(nmlog(nm))$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n, m;
                cin >> n >> m;

                vector<int> c(n + 1);
                for (int i = 1; i <= n; i++) cin >> c[i];

                vector<vector<int>> a(n + 1, vector<int>(m + 1));
                vector<vector<pair<int, int>>> b(m + 1);
                for (int i = 1; i <= n; i++) {
                        for (int j = 1; j <= m; j++) {
                                cin >> a[i][j];

                                b[j].push_back({a[i][j], i});
                        }
                }

                vector<vector<int>> rank(n + 1, vector<int>(m + 1));
                vector<vector<int>> dec(n + 1, vector<int>(m + 1));
                for (int j = 1; j <= m; j++) {
                        sort(b[j].begin(), b[j].end());

                        for (int i = 0; i < n; i++) {
                                auto [x, id] = b[j][i];
                                rank[id][j] = i + 1;
                                dec[i + 1][j] = id;
                        }
                }

                int ans = INFF;
                vector<int> vis(n + 1, 0);
                vector<vector<int>> dist(n + 1, vector<int>(m + 1, INFF));
                priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
                vis[1] = 1;
                for (int j = 1; j <= m; j++) dist[1][j] = 0, pq.push({dist[1][j], 1, j});
                while (!pq.empty()) {
                        auto [w, x, t] = pq.top();
                        pq.pop();

                        if (dist[x][t] < w) continue;

                        if (x == n) ans = min(ans, w + c[n]);

                        if (rank[x][t] < n) {
                                int z = dec[rank[x][t] + 1][t];
                                if (w < dist[z][t]) {
                                        dist[z][t] = w;
                                        pq.push({dist[z][t], z, t});
                                }
                        }

                        if (rank[x][t] > 1) {
                                int z = dec[rank[x][t] - 1][t];
                                if (w + a[x][t] - a[z][t] < dist[z][t]) {
                                        dist[z][t] = w + a[x][t] - a[z][t];
                                        pq.push({dist[z][t], z, t});
                                }
                        }

                        if (!vis[x]) {
                                vis[x] = 1;
                                for (int j = 1; j <= m; j++) {
                                        if (w + c[x] < dist[x][j]) {
                                                dist[x][j] = w + c[x];
                                                pq.push({dist[x][j], x, j});
                                        }
                                }
                        }
                }

                cout << ans << '\n';
        }
        
        return 0;
}

First we use the line segment tree to maintain sequence $$$b$$$. For the nodes $$$[l,r]$$$ on each line segment tree, we maintain the first and last occurrence positions of each binary bit in the interval.

We need to merge the two intervals, whether it is modification or query. Suppose you want to use the information of $$$[l, mid], [mid +1, r]$$$ to merge the information of $$$[l, r]$$$. Consider the answer that spans two intervals. If we want to make the $$$i$$$-th position of the interval OR $$$1$$$, then there are two possibilities

1. Select the last occurrence position $$$P$$$ of the $$$i$$$-th bit in $$$[l,mid].$$$

2. Select the first occurrence position $$$Q$$$ of the $$$i$$$-th bit in $$$[mid+1,r].$$$

Let $$$x = max(a[P], a[P+1],\ldots, a[mid]), y = max(a[mid + 1], a[mid + 2], \ldots, a[Q]).$$$

If $$$x<=y,$$$ we can choose the position $$$P$$$ greedily, because his price is smaller. If you choose $$$Q,$$$ then you must also choose $$$P,$$$ because choosing $$$P$$$ does not increase max $$$a.$$$ Otherwise, select $$$Q$$$ on the contrary.

With the above greedy, then you can enumerate the first binary bit $$$i$$$ that is larger than $$$v$$$. The $$$i$$$-th bit of the interval OR must be $$$1$$$, and the $$$i$$$-th bit of $$$v$$$ is $$$0$$$. For the $$$j$$$-th $$$(j >i)$$$ bit, if the $$$j$$$-th bit of $$$v$$$ is $$$1$$$, then the $$$j$$$-th bit must also be $$$1$$$. The rest of the bits can be regarded as $$$0$$$ or $$$1$$$, you only need to deal with these bits that must be selected $$$1$$$ greedily, and expand the interval.

You can use the st table $$$O(1)$$$ to find the interval max of $$$a$$$, so you can merge the information of the two intervals in the time of $$$O(log V)$$$. With the line segment tree, $$$O(q log n log V + n log V)$$$ can be done.

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 10, V = 30, inf = INT_MAX, L = 18;
int n, q, S, a[N], b[N];
struct Rmq
{
   int st[L][N];
   void init()
   {
      for (int i = 1; i <= n; i++)
         st[0][i] = a[i];
      for (int i = 1; i < L; i++)
      {
         for (int j = 1; j <= n - (1 << i) + 1; j++)
         {
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
         }
      }
   }
   int qry(int l, int r)
   {
      int k = __lg(r - l + 1);
      return max(st[k][l], st[k][r - (1 << k) + 1]);
   }
} ds;
struct Info
{
   int pre[V], suf[V];
   int ans, l, r;
   Info()
   {
      memset(pre, 0, sizeof(pre));
      memset(suf, 0, sizeof(suf));
      ans = inf, l = r = 0;
   }
   Info(const Info &x, const Info &y)
   {
      for (int i = 0; i < V; i++)
      {
         pre[i] = x.pre[i] ? x.pre[i] : y.pre[i];
         suf[i] = y.suf[i] ? y.suf[i] : x.suf[i];
      }
      ans = inf, l = r = 0;
   }
   friend Info operator+(const Info &x, const Info &y)
   {
      Info z(x, y);
      z.ans = min(x.ans, y.ans), z.l = x.l, z.r = y.r;
      int pl = x.r, pr = y.l;
      if (!pl)
         return z;
      for (int i = V - 1; i >= 0; i--)
      {
         int u = x.suf[i], v = y.pre[i];
         if (u)
            u = min(u, pl);
         if (v)
            v = max(v, pr);
         int lans = u ? ds.qry(u, pr) : inf;
         int rans = v ? ds.qry(pl, v) : inf;
         if (lans < rans)
         {
            if (S >> i & 1)
            {
               if (lans < z.ans)
                  pl = u;
               else
                  break;
            }
            else
               z.ans = min(z.ans, lans);
         }
         else
         {
            if (S >> i & 1)
            {
               if (rans < z.ans)
                  pr = v;
               else
                  break;
            }
            else
               z.ans = min(z.ans, rans);
         }
      }
      return z;
   }
   void clear()
   {
      *this = Info();
   }
   void upd(int p)
   {
      l = r = p, ans = b[p] > S ? a[p] : inf;
      memset(pre, 0, sizeof(pre));
      memset(suf, 0, sizeof(suf));
      for (int j = 0; j < V; j++)
      {
         if (b[p] >> j & 1)
         {
            suf[j] = p;
            pre[j] = p;
         }
      }
   }
} ans;
void reply(const Info &cur)
{
   ans = ans + cur;
}
struct Node
{
   Node *ls, *rs;
   int l, r, mid;
   Info info;
   void up()
   {
      info = ls->info + rs->info;
   }
   void update(int p)
   {
      if (l == r)
         return info.upd(l);
      p <= mid ? ls->update(p) : rs->update(p);
      up();
   }
   void query(int ql, int qr)
   {
      if (l >= ql && r <= qr)
         return reply(info);
      if (ql <= mid)
         ls->query(ql, qr);
      if (qr > mid)
         rs->query(ql, qr);
   }
} mempool[N + 5 << 1], *cnt = mempool, *rt;
Node *build(int l, int r)
{
   Node *u = cnt++;
   int mid = l + r >> 1;
   u->l = l, u->r = r, u->mid = mid;
   if (l == r)
   {
      u->info.upd(l);
      return u;
   }
   u->ls = build(l, mid);
   u->rs = build(mid + 1, r);
   u->up();
   return u;
}
 
void solve()
{
   cin >> n >> S;
   S--;
   for (int i = 1; i <= n; i++)
      cin >> a[i];
   ds.init();
   for (int i = 1; i <= n; i++)
      cin >> b[i];
   rt = build(1, n);
   cin >> q;
   for (int i = 0; i < q; i++)
   {
      int opt;
      cin >> opt;
      if (opt == 1)
      {
         int p, x;
         cin >> p >> x;
         b[p] = x;
         rt->update(p);
      }
      else
      {
         int l, r;
         cin >> l >> r;
         ans.clear();
         rt->query(l, r);
         cout << (ans.ans == inf ? -1 : ans.ans) << ' ';
      }
   }
   cout << "\n";
}
int main()
{
#ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
#endif
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   ios::sync_with_stdio(false), cin.tie(0);
   int t = 0;
   cin >> t;
   while (t--)
   {
      solve();
   }
 
   // 	cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n';
   return 0;
}

We found it difficult to directly calculate all valid permutations. How about calculating all invalid permutations?

Can you come up with an $$$O(n^2)$$$ DP solution?

How to optimize the $$$O(n^2)$$$ DP solution?

We found it difficult to directly calculate all valid permutations. Consider calculating all invalid permutations and subtract it from $$$n!$$$.

Let's first make some notes. We note $$$P_i=max(p_1,...,p_i),Q_i=max(q_1,...,q_i)$$$,and $$$last_i=max(j)(P_j \neq P_i)$$$.And note the values of all extreme points is $$$val[1,...,m]$$$ and positions is $$$pos[1,...,m]$$$.

For example,$$$p=[3,1,4,2,6,5]$$$,we get $$$m=3$$$, $$$val=[3,4,6]$$$ and $$$pos=[1,3,5]$$$.

Let’s call a permutation $$$q$$$ “i-invalid” if there’s an index $$$j$$$ satisfying $$$Q_j=P_j=val_i$$$.

Note $$$S_i$$$ as the set of all “i-invalid” permutations.According to the Inclusion-Exclusion Principle,the answer is $$$n!-(|S_1|+|S_2|+...)+(|S_1∩S_2|+|S_1∩S_3|+...)-...$$$

Consider put $$$val_i$$$ in $$$q$$$ to make $$$q$$$ “i-invalid”.There’re $$$2$$$ kinds of ways:

• $$$q_j=val_i(1 \le j < pos_i)$$$ and $$$Q_{pos_i}=val_i$$$;

• $$$q_j=val_i(pos_i \le j< pos_{i+1})$$$ and $$$Q_{pos_i}=val_i$$$.

In both cases,we call the first $$$max(j,pos_i)$$$ numbers are “determined”. In other words,they’re some numbers in $$$[1,val_i]$$$.

Then we can find an $$$O(n^2)$$$ DP. Note $$$dp_{i,j}$$$ — $$$i$$$ stands for the first $$$i$$$ numbers is “determined”,and $$$j$$$ stands for $$$j$$$ extreme values are “invalid”. In fact we only care about the parity of $$$j$$$,so $$$j=0,1$$$. Note for the first $$$i$$$ numbers are “determined” automatically means $$$Q_i=P_i$$$. In addition,$$$q_i=P_i(P_i=P_{i-1})$$$ or $$$q_i<P_i(P_i \neq P_{i-1})$$$.

We get a DP formula $$$dp_{i,j}= \Sigma_{k=0}^{last_i} dp_{k,j \oplus 1} \cdot A^{P_i-k-1}_{i-k-1} \cdot (P_i==P_{i+1}?1:i-k)$$$

Here is a small trick to reduce the constant. If we note $$$f_i=dp_{i,0}-dp_{i,1}$$$, we get a more concise formula $$$f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} \cdot (P_i==P_{i+1}?1:i-j)$$$

We perform the following transformation on the formula.

① For $$$i$$$ satisfying $$$P_i=P_{i-1}$$$, we get

$$$f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} = -[(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} f_{j} \cdot (P_i-j-1)!$$$

② For $$$i$$$ satisfying $$$P_i \neq P_{i-1}$$$, we get

$$$f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} \cdot (i-j) = -i[(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} f_{j} \cdot (P_i-j-1)! + [(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} jf_{j} \cdot (P_i-j-1)!$$$

After that, we have transformed the formula into a classical form $$$f(i)= h(i) \Sigma_{j=0}^{i-1} f(j) \cdot g(i-j)$$$, which can be calculate in $$$O(n log^2 n)$$$ by D&C+FFT.

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

#define all(a) a.begin(),a.end()
#define pb push_back
#define sz(a) ((int)a.size())

using ll=long long;
using u32=unsigned int;
using u64=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using f128=__float128;

using pii=pair<int,int>;
using pll=pair<ll,ll>;

template<typename T> using vc=vector<T>;
template<typename T> using vvc=vc<vc<T>>;
template<typename T> using vvvc=vc<vvc<T>>;

using vi=vc<int>;
using vll=vc<ll>;
using vvi=vc<vi>;
using vvll=vc<vll>;

#define vv(type,name,n,...) \
    vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) \
    vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))

template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
template<typename T> using max_heap=priority_queue<T>;

// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))

template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);}
template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);}

template<typename T>
void sort_unique(vector<T> &vec){
    sort(vec.begin(),vec.end());
    vec.resize(unique(vec.begin(),vec.end())-vec.begin());
}

template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;}
template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;}

template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;}
template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;}

#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;}

vvi read_graph(int n, int m, int base=1){
    vvi adj(n);
    for(int i=0,u,v; i<m; ++i){
        cin >> u >> v,u-=base,v-=base;
        adj[u].pb(v),adj[v].pb(u);
    }
    return adj;
}

vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);}

template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};}

template<typename T> constexpr T inf=0;
template<> constexpr int inf<int> = 0x3f3f3f3f;
template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;

template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;}

template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;}

#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())



#include <utility>

namespace atcoder {

namespace internal {

// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
    unsigned int _m;
    unsigned long long im;

    // @param m `1 <= m < 2^31`
    barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}

    // @return m
    unsigned int umod() const { return _m; }

    // @param a `0 <= a < m`
    // @param b `0 <= b < m`
    // @return `a * b % m`
    unsigned int mul(unsigned int a, unsigned int b) const {
        // [1] m = 1
        // a = b = im = 0, so okay

        // [2] m >= 2
        // im = ceil(2^64 / m)
        // -> im * m = 2^64 + r (0 <= r < m)
        // let z = a*b = c*m + d (0 <= c, d < m)
        // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
        // ((ab * im) >> 64) == c or c + 1
        unsigned long long z = a;
        z *= b;
#ifdef _MSC_VER
        unsigned long long x;
        _umul128(z, im, &x);
#else
        unsigned long long x =
            (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
        unsigned int v = (unsigned int)(z - x * _m);
        if (_m <= v) v += _m;
        return v;
    }
};

// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};

    // Contracts:
    // [1] s - m0 * a = 0 (mod b)
    // [2] t - m1 * a = 0 (mod b)
    // [3] s * |m1| + t * |m0| <= b
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

        // [3]:
        // (s - t * u) * |m1| + t * |m0 - m1 * u|
        // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        // = s * |m1| + t * |m0| <= b

        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    // by [3]: |m0| <= b/g
    // by g != b: |m0| < b/g
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        divs[cnt++] = x;
    }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

}  // namespace internal

}  // namespace atcoder


#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <numeric>
#include <type_traits>

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

struct modint_base {};
struct static_modint_base : modint_base {};

template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;

}  // namespace internal

template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
    using mint = static_modint;

  public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    static_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }
    static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = internal::is_prime<m>;
};

template <int id> struct dynamic_modint : internal::modint_base {
    using mint = dynamic_modint;

  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = internal::barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        long long x = (long long)(v % (long long)(mod()));
        if (x < 0) x += mod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        _v = (unsigned int)(v % mod());
    }
    dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = internal::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static internal::barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

namespace internal {

template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;

template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;

template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};

template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

}  // namespace atcoder


#include <algorithm>
#include <array>

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <type_traits>
#include <vector>

namespace atcoder {

namespace internal {

template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
    static constexpr int g = internal::primitive_root<mint::mod()>;
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static bool first = true;
    static mint sum_e[30];  // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]
    if (first) {
        first = false;
        mint es[30], ies[30];  // es[i]^(2^(2+i)) == 1
        int cnt2 = bsf(mint::mod() - 1);
        mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
        for (int i = cnt2; i >= 2; i--) {
            // e^(2^i) == 1
            es[i - 2] = e;
            ies[i - 2] = ie;
            e *= e;
            ie *= ie;
        }
        mint now = 1;
        for (int i = 0; i <= cnt2 - 2; i++) {
            sum_e[i] = es[i] * now;
            now *= ies[i];
        }
    }
    for (int ph = 1; ph <= h; ph++) {
        int w = 1 << (ph - 1), p = 1 << (h - ph);
        mint now = 1;
        for (int s = 0; s < w; s++) {
            int offset = s << (h - ph + 1);
            for (int i = 0; i < p; i++) {
                auto l = a[i + offset];
                auto r = a[i + offset + p] * now;
                a[i + offset] = l + r;
                a[i + offset + p] = l - r;
            }
            now *= sum_e[bsf(~(unsigned int)(s))];
        }
    }
}

template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
    static constexpr int g = internal::primitive_root<mint::mod()>;
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static bool first = true;
    static mint sum_ie[30];  // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]
    if (first) {
        first = false;
        mint es[30], ies[30];  // es[i]^(2^(2+i)) == 1
        int cnt2 = bsf(mint::mod() - 1);
        mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
        for (int i = cnt2; i >= 2; i--) {
            // e^(2^i) == 1
            es[i - 2] = e;
            ies[i - 2] = ie;
            e *= e;
            ie *= ie;
        }
        mint now = 1;
        for (int i = 0; i <= cnt2 - 2; i++) {
            sum_ie[i] = ies[i] * now;
            now *= es[i];
        }
    }

    for (int ph = h; ph >= 1; ph--) {
        int w = 1 << (ph - 1), p = 1 << (h - ph);
        mint inow = 1;
        for (int s = 0; s < w; s++) {
            int offset = s << (h - ph + 1);
            for (int i = 0; i < p; i++) {
                auto l = a[i + offset];
                auto r = a[i + offset + p];
                a[i + offset] = l + r;
                a[i + offset + p] =
                    (unsigned long long)(mint::mod() + l.val() - r.val()) *
                    inow.val();
            }
            inow *= sum_ie[bsf(~(unsigned int)(s))];
        }
    }
}

}  // namespace internal

template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if (std::min(n, m) <= 60) {
        if (n < m) {
            std::swap(n, m);
            std::swap(a, b);
        }
        std::vector<mint> ans(n + m - 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i + j] += a[i] * b[j];
            }
        }
        return ans;
    }
    int z = 1 << internal::ceil_pow2(n + m - 1);
    a.resize(z);
    internal::butterfly(a);
    b.resize(z);
    internal::butterfly(b);
    for (int i = 0; i < z; i++) {
        a[i] *= b[i];
    }
    internal::butterfly_inv(a);
    a.resize(n + m - 1);
    mint iz = mint(z).inv();
    for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
    return a;
}

template <unsigned int mod = 998244353,
          class T,
          std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    using mint = static_modint<mod>;
    std::vector<mint> a2(n), b2(m);
    for (int i = 0; i < n; i++) {
        a2[i] = mint(a[i]);
    }
    for (int i = 0; i < m; i++) {
        b2[i] = mint(b[i]);
    }
    auto c2 = convolution(move(a2), move(b2));
    std::vector<T> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        c[i] = c2[i].val();
    }
    return c;
}

std::vector<long long> convolution_ll(const std::vector<long long>& a,
                                      const std::vector<long long>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    static constexpr unsigned long long MOD1 = 754974721;  // 2^24
    static constexpr unsigned long long MOD2 = 167772161;  // 2^25
    static constexpr unsigned long long MOD3 = 469762049;  // 2^26
    static constexpr unsigned long long M2M3 = MOD2 * MOD3;
    static constexpr unsigned long long M1M3 = MOD1 * MOD3;
    static constexpr unsigned long long M1M2 = MOD1 * MOD2;
    static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;

    static constexpr unsigned long long i1 =
        internal::inv_gcd(MOD2 * MOD3, MOD1).second;
    static constexpr unsigned long long i2 =
        internal::inv_gcd(MOD1 * MOD3, MOD2).second;
    static constexpr unsigned long long i3 =
        internal::inv_gcd(MOD1 * MOD2, MOD3).second;

    auto c1 = convolution<MOD1>(a, b);
    auto c2 = convolution<MOD2>(a, b);
    auto c3 = convolution<MOD3>(a, b);

    std::vector<long long> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        unsigned long long x = 0;
        x += (c1[i] * i1) % MOD1 * M2M3;
        x += (c2[i] * i2) % MOD2 * M1M3;
        x += (c3[i] * i3) % MOD3 * M1M2;
        // B = 2^63, -B <= x, r(real value) < B
        // (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
        // r = c1[i] (mod MOD1)
        // focus on MOD1
        // r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
        // r = x,
        //     x - M' + (0 or 2B),
        //     x - 2M' + (0, 2B or 4B),
        //     x - 3M' + (0, 2B, 4B or 6B) (without mod!)
        // (r - x) = 0, (0)
        //           - M' + (0 or 2B), (1)
        //           -2M' + (0 or 2B or 4B), (2)
        //           -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
        // we checked that
        //   ((1) mod MOD1) mod 5 = 2
        //   ((2) mod MOD1) mod 5 = 3
        //   ((3) mod MOD1) mod 5 = 4
        long long diff =
            c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
        if (diff < 0) diff += MOD1;
        static constexpr unsigned long long offset[5] = {
            0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
        x -= offset[diff % 5];
        c[i] = x;
    }

    return c;
}

}  // namespace atcoder

using namespace atcoder;

using mint=modint998244353;
//using mint=modint1000000007;

template<int mod>
struct nCr{
    vector<static_modint<mod>> fac,inv,ifac;
    void calc(int n){
        fac.resize(n+1),inv.resize(n+1),ifac.resize(n+1);
        fac[0]=inv[1]=ifac[0]=1;
        for(int i=1; i<=n; ++i) fac[i]=fac[i-1]*static_modint<mod>::raw(i);
        for(int i=2; i<=n; ++i) inv[i]=inv[mod%i]*static_modint<mod>::raw(mod-mod/i);
        for(int i=1; i<=n; ++i) ifac[i]=ifac[i-1]*inv[i];
    }
    static_modint<mod> C(int n, int m){
        if(m<0||m>n) return 0;
        return fac[n]*ifac[m]*ifac[n-m];
    }
};

nCr<998244353> de;

void ahcorz(){
    // (a_i - j)! / (a_i - i)! (a_i = a_j)
    // (a_i - j - 1)! / (a_i - i)! * (i - j) (a_i != a_j)
    int n; cin >> n;
    de.calc(n+1);
    vi a; a.pb(0);
    rep(n){
        int x; cin >> x;
        a.pb(max(a.back(),x));
    }
    vc<mint> dp(n+1),aux(n+1);
    auto solve=[&](auto &self, int l, int r) -> void{
        if(l+1==r){
            if(l==0) dp[l]=-1;
            else dp[l]+=aux[l]*l;
            dp[l]*=de.ifac[a[l]-l];
            return;
        }
        int mid=l+r>>1;
        self(self,l,mid);
        if(a[mid]==a[mid-1]){
            int x=mid-1,y=mid;
            while(x-1>=l&&a[x-1]==a[mid]) x--;
            while(y+1<r&&a[y+1]==a[mid]) y++;
            mint tot,tot1,tot2;
            rep(i,x,mid) tot+=dp[i]*de.fac[a[mid]-i],tot1+=dp[i]*de.fac[a[mid]-i-1],tot2+=dp[i]*de.fac[a[mid]-i-1]*i;
            rep(i,mid,y+1) dp[i]-=tot-(tot1*i-tot2);
        }
        vc<mint> vec;
        rep(i,a[mid]-mid,a[r-1]-(l+1)+1) vec.pb(de.fac[i]);
        vc<mint> vec1,vec2;
        rep(i,l,mid) vec1.pb(dp[i]),vec2.pb(dp[i]*i);
        auto res1=convolution(vec,vec1),res2=convolution(vec,vec2);
        int base=a[mid]-mid+l+1;
        rep(i,mid,r) if(a[i]-base>=0&&a[i]-base<sz(res1)) aux[i]-=res1[a[i]-base],dp[i]+=res2[a[i]-base];
        self(self,mid,r);
    };
    solve(solve,0,n+1);
    print(dp[n].val());
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cout << fixed << setprecision(20);
    int t=1;
    cin >> t;
    while(t--) ahcorz();
}

For a given center coordinate $$$(x,y)$$$, we can model the objective function $$$r=f(x,y)$$$ to maximize as follows.

Formally, this can be modeled as follows:

This is a second order cone program. Generally, this is not as simple to solve as linear or quadratic programs. There are multiple solvers out there, but all of them are either commercial or simply unfit for use on Codeforces. And even if we use general approaches to second order cone programming, their time complexity is at least $$$\mathcal{O}(n^{3.5})$$$, so they cannot work. Almost all general approaches to convex programming do not help very much for this task also, because of the following reasons.

• Gradient Descent cannot work in this task. The objective function is not smooth.

• Coordinate Descent also cannot work in this task for the same reason, and it is not hard to find a countercase.

• Subgradient methods can solve this task, but they take $$$\mathcal{O}(1/\epsilon^2)$$$ iterations to converge. This is a very big dependency on the precision, so they take too much time.

• We do not expect anyone to write Adaptive Coordinate Descent during contest time, but we still tested the PRAXIS algorithm and checked that it does not pass.

• Using nested ternary searches does not help very much. The time complexity will be $$$\mathcal{O}(n \log^2 (1/\epsilon))$$$, but the constants are large due to multiple function calls and floating point operations.

• Heuristics such as the Nelder-Mead method are not proven to converge. In many cases we found it not converging successfully.

In the editorial, we will explain a solution of expected $$$\mathcal{O}(n)$$$ time complexity, with constants depending on the number of dimensions (which is $$$2$$$ in our case).

First, we observe that any answer can be described as a "basis" of at most $$$3$$$ selected circles. For $$$k=0,1,2,3$$$, the basis is as follows.

• Case 1: $$$k=0$$$

This is the case of no circles, which can be regarded as an "identity element" of bases. Some very huge circle that will enclose any given circle, for example the circle with $$$10^{18}$$$ as radius and $$$(0,0)$$$ as center, can represent this case.

• Case 2: $$$k=1$$$

This is the case of a single circle. The circle that represents this case is the one selected circle.

• Case 3: $$$k=2$$$

This is the case of two circles, for which the basis is the largest circle in the intersection of two circles. We can find this by choosing the center as the midpoint of the two points $$$A$$$ and $$$B$$$, where $$$A$$$ and $$$B$$$ are the points where the line segment between circle centers and the circle itself intersect.

• Case 4: $$$k=3$$$

This is the case of three circles, and the most tricky of all four cases. It can be found as one solution to the following system of quadratic equations:

This can be solved algebraically. If you are used to solving geometry problems in Olympiads, you may know the ''Problem of Apollonius''. This is one special case of the problem, which is not very often mentioned because often the three circles do not intersect with each other (thus most of the time one solution for $$$r$$$ must be negative). Or if one does not know the problem, they can find that the locus of the circle center that meets with two circle edges (as in Case 3) is a conic section, precisely one side of a pair of hyperbola. By finding the intersections of two hyperbola, one can find the center of this circle. Thus, this circle can be found in $$$\mathcal{O}(1)$$$ time, with constants based on number of dimensions.

By the system of quadratic equations stated above, we see that there are at most $$$2$$$ solutions. It is sufficient to take the one that happens to be inside the intersection. (If there are two such solutions, take the larger one. For the current version of the data this check is not necessary, but it does not hurt to try.) Thus, for some $$$n>3$$$, the bases can be represented with some $$$k \le 3$$$ circles.

Do note that, already, we have an $$$\mathcal{O}(n^3)$$$ solution based on this. We enumerate all possible bases, and find the smallest one out of them (since that one will be the one that satisfies the conditions).

Now, for some basis circle $$$(x,y,r)$$$, we can check whether some given circle $$$(x_i,y_i,r_i)$$$ is "violated" by this basis (i.e. this basis is not inside this circle) in $$$\mathcal{O}(1)$$$ by comparing the distance. We take an incremental approach. We add circles to the basis one by one, up to $$$3$$$ circles. We choose to change the basis if only the next added circle is violated by the current basis. Of course, still this takes $$$\mathcal{O}(n^3)$$$ time, and sorting the circles based on any argument will not help anyways.

However, adding the circles in random order will make it only take expected $$$\mathcal{O}(n)$$$ time. This can be analyzed by the probability that a new basis will be added. The precise analysis for the time complexity is left as a practice for the reader.

If you have seen the minimum enclosing circle problem, the Welzl's algorithm to solve that precise problem will seem very similar to this. In fact, the suggested algorithm itself is not very different from Welzl's algorithm. If you want, though, you may take an iterative approach instead of modifying Welzl's algorithm. Using three nested loops will do.

There is only two issues left. The first is the issue of numerical instability. Sometimes, due to numerical instability, the algorithm will return a NaN value. It is not that hard to solve, we can simply shuffle again and rerun the algorithm. The given time limit will be sufficient for doing this unless the constant is too big. The second is more tricky, and it is about hacks.

If you use a fixed seed for randomization (or time-based seeds to some extent), someone may hack you by adding an adversarial test case which makes the time complexity explode back to $$$\mathcal{O}(n^3)$$$. This is very bad. How do we solve this? To intervent this, we will make the algorithm halt when the number of iterations exceed a certain limit. Formally, let us choose a constant $$$c$$$, and the algorithm will halt and rerun when the number of iterations exceeds $$$c \cdot n$$$. Then, if the probability of the algorithm successfully running in this number of iterations is $$$p$$$, the expected number of reruns needed is $$$\mathcal{O}(1/p)$$$, and hacking is much harder. The algorithm will successfully find the solution in $$$\mathcal{O}((c/p) \cdot n)$$$ time. Of course, the probability $$$p$$$ depends on $$$c$$$, and you must tune the value as needed. Empirically $$$c=30$$$ runs very well, almost always taking no longer than $$$0.4$$$ seconds under proper optimizations, and $$$1.5$$$ seconds without.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
using lf=long double;
using pt=pair<lf,lf>;
lf& real(pt& p){return p.first;}
lf& imag(pt& p){return p.second;}
pt midp(pt a,pt b){return pt{(real(a)+real(b))/2,(imag(a)+imag(b))/2};}
pt addi(pt a,pt b){return pt{(real(a)+real(b)),(imag(a)+imag(b))};}
pt subt(pt a,pt b){return pt{(real(a)-real(b)),(imag(a)-imag(b))};}
pt mult(pt a,lf b){return pt{real(a)*b,imag(a)*b};}
lf abs(pt a){return sqrtl(powl(real(a),2)+powl(imag(a),2));}
lf dist(pt a,pt b){return sqrtl(powl(real(a)-real(b),2)+powl(imag(a)-imag(b),2));}
 
struct circ{pt p;lf r;};
const lf inf=1e18;
 
circ basis0(){return {pt{0,0},inf};}
 
circ basis1(circ a){return a;}
 
circ basis2(circ a,circ b)
{
    pt aa=a.p,bb=b.p;
    pt ab=subt(bb,aa),ba=subt(aa,bb);
    lf aab=abs(ab),aba=abs(ba);
    real(ab)/=aab;
    imag(ab)/=aab;
    real(ba)/=aba;
    imag(ba)/=aba;
    pt ar=addi(aa,mult(ab,a.r)),br=addi(bb,mult(ba,b.r));
    
    return {midp(ar,br),dist(ar,br)/2.0L};
}
 
circ basis3(circ a,circ b,circ c)
{
    lf x1=real(a.p),y1=imag(a.p),r1=a.r;
    lf x2=real(b.p),y2=imag(b.p),r2=b.r;
    lf x3=real(c.p),y3=imag(c.p),r3=c.r;
    lf a2=x1-x2,a3=x1-x3,b2=y1-y2,b3=y1-y3,c2=r2-r1,c3=r3-r1;
    lf d1=x1*x1+y1*y1-r1*r1,d2=d1-x2*x2-y2*y2+r2*r2,d3=d1-x3*x3-y3*y3+r3*r3;
    lf ab=a3*b2-a2*b3;
    lf xa=(b2*d3-b3*d2)/(ab*2)-x1;
    lf xb=(b3*c2-b2*c3)/ab;
    lf ya=(a3*d2-a2*d3)/(ab*2)-y1;
    lf yb=(a2*c3-a3*c2)/ab;
    lf A=xb*xb+yb*yb-1;
    lf B=2*(r1+xa*xb+ya*yb);
    lf C=xa*xa+ya*ya-r1*r1;
    lf r=-(A?(B-sqrtl(B*B-4*A*C))/(2*A):C/B);
    return {pt{x1+xa+xb*r,y1+ya+yb*r},r};
}
 
bool viol(circ p,circ a)
{
    return a.r<p.r+dist(a.p,p.p);
}
 
circ solve(vector<circ>&v)
{
    lf _nan=nan("aaa");
    mt19937_64 mt(1999999);
    //shuffle(begin(v),end(v),mt);
    vector<circ>basis;
    auto trivial=[&]()
    {
        if(size(basis)==0)return basis0();
        if(size(basis)==1)return basis[0];
        if(size(basis)==2)return basis2(basis[0],basis[1]);
        return basis3(basis[0],basis[1],basis[2]);
    };
 
    int counter=0;
    
    auto rec=[&](auto rec,int n)->circ
    {
        if(n==0||size(basis)==3)return trivial();
        counter++;
        if(counter>30*size(v))return {pt{0,0},_nan};
        auto c=rec(rec,n-1);
        auto p=v[n-1];
        if(!viol(c,p)||isnan(c.r))return c;
        basis.push_back(p);
        c=rec(rec,n-1);
        basis.pop_back();
        return c;
    };
    auto c=rec(rec,size(v));
    while(isnan(c.r))
    {
        counter=0;
        shuffle(begin(v),end(v),mt);
        c=rec(rec,size(v));
    }
    return c;
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    vector<circ>v(n);
    for(auto&[p,r]:v)
    {
        ll x,y,rr;cin>>x>>y>>rr;
        p={x,y};r=rr;
    }
    auto ans=solve(v);
    cout<<setprecision(16)<<fixed<<real(ans.p)<<" "<<imag(ans.p)<<" "<<ans.r<<"\n";
}

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

void test_case() {
	int a, b, c, n; cin >> a >> b >> c >> n;
	c = min(c, n / 100); n -= c * 100;
	b = min(b, n / 10); n -= b * 10;
	a = min(a, n); n -= a;
	if (n == 0) cout << "YES\n";
	else cout << "NO\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

We only need to use $$$100$$$ coins as much as possible first, then $$$10$$$ coins as much as possible, and finally $$$1$$$ coins.

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif

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

#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif

int32_t main() {
    ios_base::sync_with_stdio(0);   cin.tie(0);

    int T;  cin >> T;
    while(T--) {
        int n;  cin >> n;
        vector<int> a(n), b(n);

        long long ans = LLONG_MIN, sum = 0, sa = 0, sb = 0;
        for(auto &i: a)     cin >> i;
        for(auto &i: b)     cin >> i, sum += i;


        ans = 2 * a.back() - sum;
        for(int i = n - 1 ; i >= 0 ; i--) {
            sa += a[i], sb += b[i];
            ans = max(ans, min((sa - a.back()) - (sb - b[i]), sa - (sum - b.back())));
        }

        cout << ans << '\n';

    }

    return 0;
}

Consider enumerate $$$i_a$$$ from $$$1$$$ to $$$n$$$.

For a fixed $$$i_a$$$,Bob has only two possible optimal options:choose $$$i_b=1$$$ or $$$i_b=i_a+1$$$ (if $$$i_a \neq n$$$).So Bob chooses $$$min(a_{i_a}+...+a_n-(b_1+...+b_{n-1}),a_{i_a}+...+a_{n-1}-(b_{i_a+1}+...+b_n))$$$.

Note $$$score_i$$$ as the answer for fixed $$$i_a=i$$$,the final answer is $$$max(score_i)$$$.

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

#define int long long

void test_case() {
	int n; cin >> n;
	string s; cin >> s;
	int same = 1, cnt = 0;
	for (int i = 1; i < n; i++) {
		if (s[i] != s[i - 1]) same = 0;
		same++;
		if (same >= 3) cnt += same - 2;
	}
	for (int i = 0; i < n; i += 2) s[i] = '1' + '0' - s[i];
	same = 1;
	for (int i = 1; i < n; i++) {
		if (s[i] != s[i - 1]) same = 0;
		same++;
		cnt += (same - 1) / 2;
	}
	cout << cnt << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

The key observation is that super palindromes are strings of length $$$\geq 3$$$ with all numbers equal, or a string with alternating $$$0-1$$$ (and with odd length).

After that, we only need to enumerate $$$i$$$ from $$$1$$$ to $$$n$$$ and count super palindromes that end in index $$$i$$$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 2e5 + 2;

int p[MAXN];
bitset<MAXN> used;

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, sum = 1, k = 1;
        cin >> n;
        for (int i = 1;i <= n;i++) {
            used.reset(i);
            p[i] = 0;
        }
        while (sum <= n * (n + 1) / 4) {
            used.set(k);
            p[k] = k;
            k++;
            sum += k;
        }
        k--;
        ll r = n * (n + 1) / 4 - k * (k + 1) / 2, rmax = n;
        while (r) {
            p[k] = min(p[k] + r, rmax);
            used.set(p[k]);
            used.reset(k);
            r -= min(r, rmax - k);
            k--; rmax--;
        }
        int point_p = 1, point_q = 1;
        while (point_p <= n && point_q <= n) {
            while (p[point_p]) point_p++;
            while (used.test(point_q)) point_q++;
            p[point_p] = point_q;
            used.set(point_q);
        }
        for (int i = 1;i <= n;i++) cout << p[i] << ' ';
        cout << endl;
    }
}

Let $$$p$$$ be the lexicographically smallest balanced permutation of length $$$n$$$ and $$$x$$$ be the integer such that $$$1 \leq x < n$$$ and $$$p_1+p_2+⋯+p_x=p_{x+1}+p_{x+2}+⋯+p_n$$$. Let's take a look to the lexicographically smallest (not necessary balanced) permutation of length $$$n$$$, which is $$${1,2,\dots,n}$$$.

Let $$$m$$$ be the largest value such that:

Notice that since $$$m$$$ is as large as possible, $$$1+2+\dots+m+(m+1) > (m+2)+(m+3)+\dots+n$$$. Which means, $$$x < m+1$$$ for any balanced permutation of length $$$n$$$ (since no matter how you rearrange the permutation, $$$p_1+p_2+⋯+p_{m+1} \geq 1+2+\dots+m+(m+1)$$$). It is also worth noting that $$$m < n$$$. This will be useful later.

Since $$$p$$$ is the lexicographically smallest balanced permutation of length $$$n$$$, we want to greedily shove as much small numbers as possible to the prefix of $$$p$$$, then sort the prefix from smallest to largest, thus making $$$x$$$ be as large as possible. Notice that since $$$x < m+1$$$, it is possible that $$$x = m$$$ in the optimal solution and we can prove that it actually is.

Assume $$$p = {1,2,\dots,n}$$$ (in other words, $$$p_i = i$$$ for all $$$1 \leq i \leq n$$$). Focus on the $$$m$$$ first numbers in the permutation. Let $$$r = \frac{1+2+\dots+n}{2} - (1+2+\dots+m)$$$ (which means $$$r \geq 0$$$). Since:

$$$r < m+1$$$ which means $$$r \leq m$$$. This means that in order to make sure $$$p_1 + p_2 + \dots + p_m = p_{m+1} + p_{m+2} + \dots + p_n$$$, we can just add $$$1$$$ to all $$$p_j$$$ where $$$m - r + 1 \leq j \leq m$$$ and $$$p_1,p_2,\dots,p_m$$$ will still be a possible prefix of the permutation, since $$$p_m \leq n$$$ and $$$p_1 < p_2 < \dots < p_m$$$ will still be satisfied after the changes (because $$$m < n$$$ and $$$p_1 < p_2 < \dots < p_{m-r} < p_{m-r+1} < \dots < p_m$$$ before the changes). Now that we know $$$x = m$$$, how can we make $$$p$$$ as small lexicographically as possible?

Let's focus on the first $$$m$$$ numbers inside $$$p$$$. Set $$$p_i := i$$$ for all $$$1 \leq i \leq m$$$. We will modify this later. Now, we need to add the value $$$r$$$ to the first $$$m$$$ numbers by spreading the addition. However, to make sure $$$p$$$ is as small as possible, we have to greedily add some value to some last numbers inside $$${p_1,p_2,\dots,p_m}$$$ such that the added value is $$$r$$$ and $$${p_1,p_2,\dots,p_m}$$$ is lexicographically smallest. In other words, we can do this procedure to construct the first $$$m$$$ numbers inside the permutation:

• Set $$$p_i := i$$$ for all $$$1 \leq i \leq m$$$.
• Let $$$j = m$$$. While $$$r > 0$$$, add $$$\min(r,k-j)$$$ to $$$p_j$$$, decrease $$$r$$$ by $$$\min(r,k-j)$$$, and decrease $$$j$$$ by $$$1$$$ where $$$k$$$ is the maximum integer such that $$$k \leq n$$$ and $$$k$$$ currently does not appear inside $$${p_1,p_2,\dots,p_m}$$$.

For the last $$$n-m$$$ numbers, notice that we can just fill these with all the numbers that are not used in the first $$$m$$$ numbers, since the sum of the numbers will automatically be equal to $$$p_1+p_2+\dots+p_m = \frac{1+2+\dots+n}{2}$$$. Do note that to make sure $$$p$$$ is as small as possible, $$$p_{m+1} < p_{m+2} < \dots < p_n$$$ need to be satisfied.

Time Complexity: $$$O(n)$$$

Turns out that there is an unexpected DFS solution to this problem that some of the participants has used, although I don't really know how the sol works :].

Bonus question: Can you guess which $$$n$$$ values results in no possible balanced permutation?

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

#define int long long
#define INF (int)(1e16)

#define N 510000
#define K 51

int a[N], cnt[N], pref[N], dp[K][N], n, k;

void calc(int i, int l, int r, int vl, int vr) {
	if (r < l) return;
	int mid = (l + r) / 2;
	int v, mn = INF;
	for (int j = vr; j >= vl; j--) {
		int sum = pref[mid] - pref[j - 1];
		int need = cnt[mid] - cnt[j - 1];
		if (i % 2 == 0) {
			need = (j + j + need - 1) * need / 2;
			sum = sum - need;
		} else {
			need = (mid + mid - need + 1) * need / 2;
			sum = need - sum;
		}
		if (dp[i - 1][j - 1] + sum < mn) {
			mn = dp[i - 1][j - 1] + sum;
			v = j;
		}
	}
	dp[i][mid] = mn;
	calc(i, l, mid - 1, vl, v);
	calc(i, mid + 1, r, v, vr);
}

void test_case() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 2; i <= n; i++)
		a[i] ^= a[i - 1];
	for (int i = 1; i <= n; i++)
		cnt[i] = cnt[i - 1] + a[i], pref[i] = pref[i - 1] + i * a[i];
	for (int i = 1; i < n; i++)
		dp[0][i] = INF;
	dp[0][0] = 0;
	int ans = INF;
	for (int i = 1; i <= k; i++) {
		calc(i, 1, n - 1, 1, n - 1);
		if (i + (a[n] ^ (i & 1)) <= k)
			ans = min(ans, dp[i][n - 1]);
	}
	cout << ans << '\n';
}

int32_t main() {
	int t; cin >> t;
	while (t--) test_case();
}

Considering the prefix xor array of $$$a$$$, we found that the original operation was equivalent to swapping $$$prexor_ {i-1}, prexor_ {i} (1<i<n) $$$.

In fact,it is a variation of this.

Afterwards, the constraint of 'at most 2' is equivalent to having at most one continuous $$$1... 1$$$in $$$prexor$$$.

Because $$$prexor_n$$$ cannot be changed,if $$$prexor_n=1$$$, we merge all $$$1$$$ into one suffix. Otherwise, we will merge all $$$1$$$s into the vicinity of the middle $$$1$$$.

Read the solution for the Easy Version first.

In this version,we need to divide all $$$1$$$ s into up to $$$\lfloor \frac{k}{2} \rfloor$$$ groups and merge the $$$1$$$ s of each group in the optimal way.

Note $$$pos$$$ as positions of all $$$1$$$s,we can calculate the cost of merging $$$pos_l,...,pos_r$$$ in $$$O(1)$$$.Note it as $$$cost(l,r)$$$.

Now,we have a slmple $$$DP$$$:$$$dp_{i,j}=min_{0 \leq t <i}(dp_{t,j-1}+cost(t+1,i))$$$.It's $$$O(n^2k)$$$.How to optimize it?

We notice $$$cost(l+1,r+1)+cost(l,r) \leq cost(l+1,r)+cost(l,r+1)$$$ holds here.Due to the quadrilateral inequality, decision monotonicity holds. We can optimize it to $$$O(nk log n)$$$ using classic techniques (decision stack or divide and conquer).

The code above divides every group into the left and right parts to make calculations easier.

To learn the classic techniques:

CF 868 F

CF 321 E

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define MOD (int)(1e9+7)
 
#define N 110000ll
#define K 20ll
#define B 850000006ll
 
struct segtree {
	vector<int> sum, lk, lb;
	segtree() {}
	segtree(int n) {
		sum = vector<int>(4 * n + 1, 0);
		lk = vector<int>(4 * n + 1, 1);
		lb = vector<int>(4 * n + 1, 0);
	}
	void push(int v, int l, int r) {
		if (lk[v] == 1 && lb[v] == 0) return;
		sum[v] = (lk[v] * sum[v] % MOD + (r - l + 1) * lb[v] % MOD) % MOD;
		if (l != r) {
			lk[v * 2 + 0] = lk[v] * lk[v * 2 + 0] % MOD;
			lb[v * 2 + 0] = (lk[v] * lb[v * 2 + 0] % MOD + lb[v]) % MOD;
			lk[v * 2 + 1] = lk[v] * lk[v * 2 + 1] % MOD;
			lb[v * 2 + 1] = (lk[v] * lb[v * 2 + 1] % MOD + lb[v]) % MOD;
		}
		lk[v] = 1, lb[v] = 0;
	}
	void upd(int v, int l, int r, int k, int x) {
		push(v, l, r);
		if (k < l || r < k) return;
		if (l == r) {
			sum[v] = x;
			return;
		}
		int mid = (l + r) / 2;
		upd(v * 2 + 0, l, mid, k, x);
		upd(v * 2 + 1, mid + 1, r, k, x);
		sum[v] = (sum[v * 2 + 0] + sum[v * 2 + 1]) % MOD;
	}
	void apply(int v, int l, int r, int ql, int qr, int k, int b) {
		push(v, l, r);
		if (qr < l || r < ql) return;
		if (ql <= l && r <= qr) {
			lk[v] = k;
			lb[v] = b;
			push(v, l, r);
			return;
		}
		int mid = (l + r) / 2;
		apply(v * 2 + 0, l, mid, ql, qr, k, b);
		apply(v * 2 + 1, mid + 1, r, ql, qr, k, b);
		sum[v] = (sum[v * 2 + 0] + sum[v * 2 + 1]) % MOD;
	}
	int get(int v, int l, int r, int ql, int qr) {
		push(v, l, r);
		if (qr < l || r < ql) return 0;
		if (ql <= l && r <= qr) return sum[v];
		int mid = (l + r) / 2;
		return (get(v * 2 + 0, l, mid, ql, qr) +
				get(v * 2 + 1, mid + 1, r, ql, qr)) % MOD;
	}
};
 
int a[N];
segtree p[K], pp;
 
int inv(int x) {
	return x == 1 ? 1 : MOD - MOD / x * inv(MOD % x) % MOD;
}
 
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for (int i = 0; i < K; i++)
		p[i] = segtree(n);
	pp = segtree(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		for (int j = 0; j < K; j++)
			if (a[i] & (1 << j)) p[j].upd(1, 0, n - 1, i, 1);
	}
	int pk = (1 - 2 * B % MOD + MOD) % MOD, pb = B;
	int ppk = pk * pk % MOD, ppb = (B - B * B % MOD + MOD) % MOD;
	while (q--) {
		int t; cin >> t;
		if (t == 1) {
			int i, x; cin >> i >> x; i--;
			for (int j = 0; j < K; j++)
				p[j].upd(1, 0, n - 1, i, (x >> j) & 1);
			pp.upd(1, 0, n - 1, i, 0);
		} else if (t == 2) {
			int l, r; cin >> l >> r; l--; r--;
			for (int j = 0; j < K; j++)
				p[j].apply(1, 0, n - 1, l, r, pk, pb);
			pp.apply(1, 0, n - 1, l, r, ppk, ppb);
		} else if (t == 3) {
			int l, r; cin >> l >> r; l--; r--;
			if (l == r) {cout << 0 << '\n'; continue;}
			int ev = 0;
			int sumpp = pp.get(1, 0, n - 1, l, r);
			for (int j = 0; j < K; j++) {
				int sump = p[j].get(1, 0, n - 1, l, r);
				int cur = (sump * (r - l + 1 - sump + MOD) % MOD - sumpp + MOD) % MOD;
				(ev += cur * (1 << j) % MOD) %= MOD;
			}
			(ev *= inv(r - l + 1) * inv(r - l) % MOD * 2 % MOD) %= MOD;
			cout << ev << '\n';
		}
	}
}

Firstly, because of linearity of expectation, we can calculate answer for each bit independently.

Formula for expected value on segment for one bit is $$$\frac{\sum_{l\leq i\neq j\leq r} p_i(1-p_j)}{(r - l + 1) \cdot (r - l) / 2}$$$, where $$$p_i$$$ is probability of $$$a_i$$$ being set to $$$1$$$.

To calculate this, we just need to maintain $$$\sum_{l\leq i\leq r} p_i$$$ and $$$\sum_{l\leq i\leq r} p_i(1-p_i)$$$ Let $$$po_i$$$ be $$$p_i$$$ before second operation and $$$b$$$ probability of bit changing ($$$\frac{1}{20}$$$).

Now to maintain $$$\sum_{l\leq i\leq r} p_i$$$ and $$$\sum_{l\leq i\leq r} p_i(1-p_i)$$$ we just need to apply linear function on segment, we can do it using segment tree. This is already fast enough for C++20 compiler. We can notice that $$$p_i(1-p_i)$$$ is same for all bits, so we can maintain only one segtree for it. With this optimization solution passes using other compilers.

The final complexity is $$$\mathcal{O}(n \log n \log A)$$$

$$$1 \le x < y \le 1000,3 \le n \le 1000$$$

DIV2A

One of the easiest.It contains the simplest 'reverse thinking'.

$$$0 \le x < 2^{30},3 \le n \le 10^5$$$

DIV2D

Contains a general idea for solving bit operation problems:consider bit by bit.

A little patience in observation is also needed.

Both of the above problems use the same model, which may be able to create more interesting problems.

$$$1 \le n \le 10^5$$$

DIV2B

Problems of snake paths on a grid is generally not easy to solve, so I chose to reduce the constraint and set the problem on a $$$2 \cdot n$$$ grid(and it works). I guess it helps beginners familiarize themselves with mex.

In addition,I think we can find more cool problems in $$$2 \cdot n$$$ grid like this one.

$$$2 \le x\le 10^9$$$

DIV2C

In the initial version, $$$x \leq 10^{18}$$$.

After discussion,we have decided to set $$$x \leq 10^9 $$$ to "mislead" people into decomposing $$$x$$$.

The interesting point is,loose constraints actually make the problem more difficult.For example,if I set $$$x \leq 10^{18}$$$ and the number of operations $$$\leq 64$$$,you will soon think of binary stuff.

Afterwards, we really discovered a solution based on factorization, which is also very beautiful!

$$$2 \le n\le 10^{18}$$$

DIV2B

A purely observational problem. I guess some people would like this kind of IQ test style problem.

I believe that some MO and IQ problems can be adapted into CP problems.

$$$1 \le n\le 10^5$$$

DIV2D-E (Codechef Rating 2961)

Including an experience (not accurate) that "most interaction problems involve binary search".

You still need some optimization, otherwise you won't be able to complete the task in $$$40$$$ operations.

$$$1 \le n\le 3000,0 \leq a_i <2^{30}$$$

DIV2D-E (Codechef Rating 3086)

The most interesting point is that when you modify a certain $$$a_x$$$, you can't even get immediate feedback from the judge(most of the time, the maximum value of the array does not change).

Consider bit by bit again :)

$$$1 \le n\le 10^5,1 \leq a_i <10^6$$$

DIV2D (Codechef Rating 2700)

I think it contains some general ideas. Considering the power of each prime factor, then you find $$$gcd(x_1,x_2,...)$$$ is to pick the maximum power of all numbers, and $$$lcm(x_1, x_2,...)$$$ is to pick the minimum power of all numbers.

• $$$1 \leq n,m \leq 3 \cdot 10^5$$$
• $$$1 \leq l \leq r \leq n$$$
• $$$-10^6 \leq k,b,x_i,y_i \leq 10^6$$$

DIV2E (Codechef Rating 3150)

If you are practicing segment trees, I strongly recommend this problem :)

An interesting thing is used here: if you write an equal difference sequence on the coordinate axis, then these points are collinear.

$$$1 \le n\le 4 \cdot 10^5,1 \leq a_i,x_i,k \leq 10^9$$$

DIV2E

This seems like a number theory problem, but it use string algorithms?

There are many educational points.This includes abstracting problems into the simplest mathematical models,techniques for transforming equations, and the use of some classic algorithms.

$$$1 \le n,k\le 10^9$$$

DIV2B-C

One way to create a problem is to start with an interesting definition(in this problem,it is $$$con(x,y)$$$).

No advanced algorithms, only testing your casework.

$$$2 \le n,k\le 10^5$$$

DIV2C

It's a variation of a classic problem.

an easier variation

an harder variation

$$$3 \le n \le m\le 10^6$$$

DIV2D

As we all know,the sum of the two sides of a triangle is greater than the third side.You need to similarly convert condition $$$3$$$.

It contains a general idea:if $$$P$$$ is hard to count,then think about count $$$ALL- \overline P$$$.

$$$C_i^j+C_{i−1}^j+...+C_j^j=C_{i+1}^{j+1}$$$

$$$2 \le n \le 2 \cdot 10^5$$$

DIV2D-E(Codechef Rating 3037)

Finding $$$a$$$ based on given $$$p$$$ is a classic problem(monotonic stack).

Here 'reverse thinking' is used, and fortunately, this problem has become more interesting :)

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

map<int, int> mp;

void test_case() {
	mp.clear();
	int n; cin >> n;
	int cnt1 = 0;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		mp[x]++;
		if (mp[x] == 1) cnt1++;
		if (mp[x] == 2) cnt1--;
	}
	if (cnt1 > 0) cout << "YES\n";
	else cout << "NO\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

If there is a unique number in a, output YES. Otherwise, output NO.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    
    while (tests--) {
        int64_t n, k;
        cin >> n >> k;
        if (k < 2 * n) {
            cout << (n - k % n) * (n - k % n) << '\n';
        } else if (n == 1 || k % 2 == 0 || k - 2 * (n - 1) != 3) {
            cout << 0 << '\n';
        } else {
            cout << 2 - (n == 2) << '\n';
        }
    }
}

If $$$k \leq 2n$$$,the optimal solution is to form array $$$a$$$ with $$$1$$$ and $$$2$$$. The answer is $$$c_1^ 2$$$.Any other construction will result in a num of $$$1$$$ greater than $$$c_1$$$, obviously not the optimal one.

For $$$k>2n+1$$$,the answer is always $$$0$$$.If $$$k$$$ is even,we can easily form array $$$a$$$ with $$$n$$$ even numbers.If $$$k$$$ is odd,we can set $$$a_1=5$$$ and form $$$a_2,...,a_n$$$ with $$$n-1$$$ even numbers.

For $$$k=2n+1$$$,if $$$n=2$$$,$$$a=[2,3]$$$ is optimal and the answer is $$$1$$$.Otherwise($$$n>2$$$),$$$a=[1,4,2,...,2]$$$ is optimal and the answer is $$$2$$$.

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

#define N 210000

string s;

void test_case() {
	int n; cin >> n >> s;
	sort(begin(s), end(s));
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum += s[i] - 'a';
	if (sum % 2 != 0) {cout << -1 << '\n'; return;}
	int ans = n * 100;
	if (s[n - 1] - 'a' <= sum - s[n - 1] + 'a')
		ans = sum;
	for (int i = 0; i < n; i++) {
		int sumcur = sum - s[i] + 'a';
		int valcur = s[i] - 'a' + 26;
		int num = (max(0, valcur - sumcur) + 25) / 26;
		if (num > i) continue;
		ans = min(ans, sum + 26 + num * 26);
	}
	if (ans == n * 100) {cout << -1 << '\n'; return;}
	cout << ans / 2 << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

For $$$n=2$$$,if $$$s_1 \neq s_2$$$ ,output $$$-1$$$.Otherwise,output $$$s_1-'a'$$$.

For $$$n>2$$$,let's consider a classic problem:for a given array $$$a$$$,you can make $$$a_i--,a_j--$$$,determine if you can make all numbers to $$$0$$$.

Let's go back to this problem.Let's see string $$$s$$$ as the array $$$a$$$ above.Note $$$opr_i$$$ as the number of times we operate on $$$s_i$$$.We can get $$$opr_i=(a_i-'a')+26k_i$$$ since we want all $$$a_i='a'$$$.Now our task is minimize $$$\Sigma k_i$$$.

First check if the original array satisfies $$$2max(a_i) \leq \Sigma a_i$$$.If not,then greedily increase the minimum value by $$$26$$$.It can be proven that we can get $$$2max(a_i) \leq \Sigma a_i$$$ after adding the array at most two times .

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=4010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int n,q;
int a[N*N];
int S[N][N];

int main()
{	
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n*n;i++) 
	{
		scanf("%d",&a[i]);
		S[i%(2*n)][(i+2*n)/(2*n)]=S[i%(2*n)][(i+2*n)/(2*n)-1]+a[i];
	}
	for(int i=1;i<=q;i++)
	{
		int t,x,p1,p2,ans=0;
		scanf("%d%d",&t,&x);
		p1=t-x+1;p2=t-2*n+x;
		if(p1>0) ans+=S[p1%(2*n)][(p1+2*n)/(2*n)];
		if(p2>0) ans+=S[p2%(2*n)][(p2+2*n)/(2*n)];
		printf("%d\n",ans);
	}
	
	return 0;
}

The key to solving the problem lies in observing:If we group all elements in $$$a$$$ according to the index mod $$$2n$$$, then at all times, the elements of the same group will always be in the same column.

We divide the elements in $$$a$$$ into $$$2n$$$ groups and build prefix sum arrays for each group. For each query, we calculate which two groups pass through this column, and then calculate the answer with the two prefix sum arrays.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
ll  sum;
int p[N],pos[N],sig[N],BIT[N];

void add(int p,int v)
{
	for(int i=p;i<=n;i+=(i&-i)) BIT[i]+=v;
}

int getsum(int p)
{
	int s=0;
	for(int i=p;i;i-=(i&-i)) s+=BIT[i];
	return s;
}

struct nod
{
	int l,r,sum,tag;
	nod *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree()
	{
		build(&root,1,n);
	}
	
	void newnod(nod **p,int L,int R)
	{
		*p=new nod;
		(*p)->l=L;(*p)->r=R;(*p)->sum=1;(*p)->tag=0;
	}
	
	void build(nod **p,int L,int R)
	{
		newnod(p,L,R);
		if(L==R) return ;
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M);
		build(&(*p)->rc,M+1,R);
		(*p)->sum=(*p)->lc->sum+(*p)->rc->sum;
	}
	
	void pushdown(nod *p)
	{
		if(p->tag) p->sum*=-1;
		if(p->l!=p->r)
		{
			p->lc->tag^=p->tag;
			p->rc->tag^=p->tag;
		}
		p->tag=0;
	}
	
	void flip(int L,int R)
	{
		_flip(root,L,R);
	}
	
	void _flip(nod *p,int L,int R)
	{
		pushdown(p);
		if(p->l==L&&p->r==R)
		{
			p->tag^=1;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(R<=M)     _flip(p->lc,L,R);
		else if(L>M) _flip(p->rc,L,R);
		else         _flip(p->lc,L,M),_flip(p->rc,M+1,R);
		pushdown(p->lc);pushdown(p->rc);
		p->sum=p->lc->sum+p->rc->sum;
	}
	
	int getsum(int L,int R)
	{
		return _getsum(root,L,R);
	}
	
	int _getsum(nod *p,int L,int R)
	{
		pushdown(p);
		if(p->l==L&&p->r==R) return p->sum;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _getsum(p->lc,L,R);
		else if(L>M) return _getsum(p->rc,L,R);
		else         return _getsum(p->lc,L,M)+_getsum(p->rc,M+1,R);
	}
};

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&p[i]),pos[p[i]]=i;
    	Segtree TR;
    	sum=0;
    	for(int i=1;i<=n;i++) BIT[i]=0;
    	for(int i=1;i<=n;i++)
    	{
	    	sig[i]=(getsum(p[i])&1)?-1:1;
	    	add(p[i],1);
	    }
    	for(int i=1;i<=n;i++)
		{
			sum+=((pos[i]&1)?1:-1)*(ll)(pos[i]-1)*i;
	    	sum+=(ll)(sig[pos[i]]*TR.getsum(pos[i],pos[i])*TR.getsum(pos[i],n))*i;
	    	TR.flip(pos[i],n);
	    }
	    printf("%I64d\n",sum);
	}
	
	return 0;
}

Consider calculating the contribution of each element separately.

For an element,we can observe that only elements with values less than it and indexes greater than it increase its index by $$$1$$$.

We represent these 'influence' as a sequence $$$s$$$ containing only $$$1$$$ and $$$-1$$$.At the beginning,$$$s_i=1$$$ for all $$$1\leq i \leq n$$$.We calculate the contribution of each element in ascending order of values.

Assuming we have already calculated the contribution of $$$x$$$,then we do filp $$$s_{pos_x},...,s_n$$$ (flip denotes making $$$1$$$ to $$$-1$$$ and make $$$-1$$$ to $$$1$$$) and calculate the contribution of $$$x+1$$$ using updated $$$s$$$.

#include <bits/stdc++.h>
// v.erase( unique(all(v)) , v.end() )    ----->   removes duplicates and resizes the vector as so
using namespace std;
#define IO_file freopen("output.txt","w",stdout), freopen("input.txt","r",stdin);
#define ll long long
#define lld long double
const lld pi = 3.14159265358979323846;
#define pb push_back
#define pf push_front
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
constexpr int mod = (int)(1e9 + 7);
#define log(x) (31^__builtin_clz(x)) // Easily calculate log2 on GNU G++ compilers
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}

struct AhoCorasick {
  //The trie
  struct tr_node {
    int adj[26];
    int link;
    int parent;
    int term;
    
    tr_node() {
      link = 0;
      parent = -1;
      term = 0;
      memset(adj, -1, sizeof(adj));
    }
  
  };
  
  vector<tr_node> tr;
  int tick = 0;//--> tick is the number of nodes in the trie
  
  AhoCorasick() {
    init();
  }
  
  void init() {
    tr.clear();
    tr.push_back(tr_node());
    tick = 0;
    tr[0].link = -1;
  }
  
  void insert(const string &s) {
    int p = 0;
    for(int i=0;i<s.size();i++){
      if(tr[p].adj[s[i]-'a'] == -1){
        tr.push_back(tr_node());
        tr[p].adj[s[i]-'a'] = (++tick);
      }
      p = tr[p].adj[s[i]-'a'];
    }
    tr[p].term++;
  }
  
  //build the suffix links and transitions for each node 
  //in Amortized O(sizeof the strings inserted in the trie + No.nodes*sizeofAlphabet).	
  //this implementation has less memory usage, so you choose which to run.
  //you can add an additional array "adj" to build a tree over the suffix links.
  vector<int> character;
  
  //we build the suffix links only and we calculate transitions on the run
  int trans(int p, int c) {
    //p is the node, c is the character
    while(p != -1 && tr[p].adj[c] == -1) p = tr[p].link;
    if(p == -1) return 0;//we return the root
    return tr[p].adj[c];
  }
  
  void build() {
    character.resize(tick+5); 
    queue<int> q; q.push(0);
    character[0] = -1;
    while(!q.empty()){
      int p = q.front(); q.pop();
      if(p){
        if(tr[tr[p].parent].link != -1){
          tr[p].link = trans(tr[tr[p].parent].link, character[p]);
        }
        if(tr[p].link != -1){
          tr[p].term += tr[tr[p].link].term;
        }
      }
      for(int i = 0 ; i < 26 ; i++){
        if(tr[p].adj[i] != -1){
          tr[tr[p].adj[i]].parent = p;
          character[tr[p].adj[i]] = i;
          q.push(tr[p].adj[i]);
          continue;
        }
      }
    }
  }
  
}Aho[20];
 
vector<string> info[20];
 
void add(const string &s) {
  for(int i = 0 ; i < 20 ; i++){
    if(info[i].size() == 0){
      for(int j = 0 ; j < i ; j++){
        for(string x : info[j]){
          info[i].pb(x);
        }
        vector<string> v;
        info[j].swap(v);
        Aho[j].init();
      }
      info[i].pb(s);
      for(string x : info[i]){
        Aho[i].insert(x);
      }
      Aho[i].build();
      break;
    }
  }
}
 
ll query(const string &s) {
  ll cnt = 0;
  for(int i = 0 ; i < 20 ; i++){
    if(info[i].empty()) continue;
    int p = 0;
    for(int j = 0 ; j < s.size() ; j++){
      p = Aho[i].trans(p, s[j] - 'a');
      cnt += Aho[i].tr[p].term;
    }
  }
  return cnt;
}

const int N = 2e5 + 7;
const int M = 4e5 + 7;

int n, par[M], fake_node;
vector<int> adj[M];
string str[N];
string qry_str[N];

void init() {
  for(int i = 0 ; i <= 2 * n ; i++){
    par[i] = i;
  }
  fake_node = n;
}

int find(int x) {
  if(x == par[x]) return x;
  return par[x] = find(par[x]);
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if(x == y) return;
  fake_node++;
  par[x] = fake_node;
  par[y] = fake_node;
  adj[fake_node].pb(x);
  adj[fake_node].pb(y);
}

int in[M], out[M], tick, node_at[M];

void dfs(int node) {
  in[node] = ++tick;
  node_at[tick] = node;
  for(int u : adj[node]){
    dfs(u);
  }
  out[node] = tick;
}

vector<pair<int, bool > > queries2[M]; // the query indx, 0 pos | 1 neg

int main()
{ios_base::sync_with_stdio(0),cin.tie(0);
cin>>n;
init();
for(int i = 1 ; i <= n ; i++){
  cin>>str[i];
}
int q; cin>>q;
vector<pair<int, int> > queries; // the node, the query indx
vector<int> quests;
for(int i = 0 ; i < q ; i++){
  int t; cin>>t;
  if(t == 1){
    int a, b; cin>>a>>b;
    merge(a, b);
    continue;
  }
  int v; cin>>v;
  cin>>qry_str[i];
  v = find(v);
  queries.pb({v, i});
  quests.pb(i);
}
for(int i = 1 ; i < n ; i++){
  merge(i, i + 1);
}
int root = find(1);
dfs(root);
for(pair<int, int> X : queries){
  int v = X.first; int indx = X.second;
  queries2[out[v]].pb({indx, 0});
  if(v != root){
    queries2[in[v] - 1].pb({indx, 1});
  }
}
ll ans[q] = {};
for(int i = 1 ; i <= tick ; i++){
  int u = node_at[i];
  if(u <= n){
    add(str[u]);
  }
  for(pair<int, int> X : queries2[i]){
    int indx = X.first;
    bool o = X.second;
    if(o){
      ans[indx] -= query(qry_str[indx]);
    }
    else {
      ans[indx] += query(qry_str[indx]);
    }
  }
}
for(int i = 0 ; i < quests.size() ; i++){
  cout<<ans[quests[i]]<<'\n';
}



    return 0;
}

We will answer the queries offline.

We will use DSU to process queries of the first type.

For each query of the first type, we will create a new node $$$H$$$ and connect both $$$u$$$ and $$$v$$$ to it.

For each query of the second type, we will add the query to the query-list of the root of the component $$$u$$$ is in.

Now we merge all the components together and we notice that now we have a tree and each query of the second type turns out to be a subtree query in our tree.

We run euler tour on the tree and now each subtree query is a range query in the euler tour array, for example it's a query on $$$[L, R]$$$, the answer to it is the answer on $$$[1, R]$$$ minus the answer on $$$[1, L - 1]$$$.

to answer these prefix queries we will use dynamic Aho-Corasick to add the strings and answer the queries.

The amortized time complexity of this solution is $$$O(N * log(N) * AlphabetSize)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
int a[N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    	sort(a+1,a+n+1);
    	for(int i=1;i<=n;i++) printf("%d%c",a[i]*(i&1?1:-1),i==n?'\n':' ');
	}
	
	//fclose(stdin);
	return 0;
}

We just sort the array and set $$$a_i:=-a_i$$$ for all even $$$i$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                string s;
                int k;
                cin >> s >> k;

                int n = (int)s.length();
                int mn = n - k;
                for (int i = n - k - 1; i >= 0; i--) {
                        if (s[i] > s[i + k]) {
                                mn = i;
                        }       
                }

                string ans = s.substr(0, mn) + s.substr(mn + k);

                cout << ans << '\n';
        }
        
        return 0;
}

We will solve this problem by using the sliding window trick. Let's assume $$$s_{i,j}$$$ as the substring inside $$$s$$$ from the $$$i$$$-th character to the $$$j$$$-th character from the left of the string $$$s$$$. First, create a window from the segment $$$[1,k]$$$ denoting the deletion window, which means $$$x=s_{k+1,|s|}$$$ for now. Now, we will slide this window by one index to the right each time and check if the new string formed by concatenating characters not covered by the window after sliding is weaker than current weakest string before sliding.

Notice that when we slide the window from the segment $$$[i,i+k-1]$$$ to $$$[i+1,i+k]$$$, the only difference between the resulting string from both deletion window result is the $$$i$$$-th character. Or more specifically, we override the $$$i$$$-th character in the result from $$$s_{i+k,i+k}$$$ to $$$s_{i,i}$$$. Furthermore, if $$$s_{i+k,i+k}$$$ is lexicographically smaller (or weaker) than $$$s_{i,i}$$$, that means the resulting string from all the deletion window placement after sliding it to the right from the segment $$$[i,i+k-1]$$$ will never be weaker than when the window is at the segment $$$[i,i+k-1]$$$, which means it is enough to keep sliding the deletion window to the right up until the point where $$$s_{i+k,i+k} < s_{i,i}$$$. Then, delete the segment $$$[i,i+k-1]$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,k,ans;
int  p[N],d[N],pre[N];
int  dp[N][2];

int main()
{
	//freopen("test.in","r",stdin);
	
	T=1;
	//scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    	ans=0;
    	pre[0]=k; 
	    for(int i=1;i<=n;i++)
	    {
    		if((d[i]&&pre[i-1]>=1900)||((!d[i])&&pre[i-1]<=2100)) pre[i]=(p[i]-pre[i-1])/4+pre[i-1];
			else pre[i]=pre[i-1];
    	}
    	ans=max(pre[n-1],pre[n]);
    	for(int i=0;i<=4000;i++) dp[i][(n+1)&1]=i;
    	for(int i=n;i>=2;i--)
    	{
			for(int j=0;j<=4000;j++) 
			{
				if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[j][i&1]=dp[(p[i]-j)/4+j][(i+1)&1];
				else dp[j][i&1]=dp[j][(i+1)&1];
			}
			ans=max(ans,dp[pre[i-2]][i&1]);
	    }
    	/*for(int i=0;i<=4000;i++) dp[n+1][i]=i;
    	for(int i=n;i;i--)
    	{
	    	for(int j=0;j<=4000;j++)
	    	{
	    		if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[i][j]=dp[i+1][(p[i]-j)/4+j];
	    		else dp[i][j]=dp[i+1][j];
	    	}
	    }
	    ans=dp[1][k];kk=k;
	    for(int i=1;i<=n;i++)
	    {
    		ans=max(ans,(int)dp[i+1][k]);
    		if((d[i]&&k>=1900)||((!d[i])&&k<=2100)) k=(p[i]-k)/4+k;
    	}*/
    	printf("%d\n",k-ans);
	}
	
	//fclose(stdin);
	return 0;
}

The key to solving the problem is to notice that $$$k$$$ is small ($$$k \leq 4000$$$).The intended solution is $$$O(nk)$$$.

We note $$$dp_{i,j}$$$ as the final rating when current score is $$$j$$$, participating in the $$$i, i+1,...,n_{th}$$$ contest.

We can enumerate the skipped contest and update the answer with the $$$dp$$$ array.

To avoid exceeding the memory limit, you need to use a scrolling array.

/**
 *  @the_hyp0cr1t3
 *  30.07.2023 20:42
**/
#include <bits/stdc++.h>

template <int P> struct modint {
    static int mod_;
    int v;

    constexpr modint() : v{} {}
    constexpr modint(long long u) {
        if (u < 0) u = u % get_mod() + get_mod();
        if (u >= get_mod()) u %= get_mod();
        v = u;
    }

    constexpr int val() const { return v; }
    constexpr static int get_mod() {
        if constexpr (P > 0)
            return P;
        else
            return mod_;
    }
    constexpr static void set_mod(int m) {
        mod_ = m;
    }
    explicit constexpr operator int() const { return v; }
    friend constexpr std::istream& operator>>(std::istream& in, modint& m) {
        long long u; in >> u;
        m = modint(u);
        return in;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const modint& m) {
        return os << m.v;
    }

    static int inv(int a, int m) {
        int g = m, x = 0, y = 1;
        while (a != 0) {
            int q = g / a;
            g %= a;
            std::swap(g, a);
            x -= q * y;
            std::swap(x, y);
        }
        return x < 0 ? x + m : x;
    }

    constexpr static unsigned fast_mod(uint64_t x, unsigned m = get_mod()) {
#if !defined(_WIN32) || defined(_WIN64)
        return unsigned(x % m);
#endif  // x must be less than 2^32 * m
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x), quot, rem;
        asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
        return rem;
    }

    constexpr modint inv() const { return modint(inv(v, get_mod())); }
    constexpr modint operator-() const { return modint(v ? get_mod() - v : 0); }
    constexpr modint& operator+=(const modint& o) {
        v += o.v;
        if (v >= get_mod()) v -= get_mod();
        return *this;
    }
    constexpr modint& operator-=(const modint& o) {
        v -= o.v;
        if (v < 0) v += get_mod();
        return *this;
    }
    constexpr modint& operator*=(const modint& o) {
        v = fast_mod(uint64_t(v) * o.v);
        return *this;
    }
    constexpr modint& operator/=(const modint& o) { return *this *= o.inv(); }
    friend constexpr modint operator+(const modint& a, const modint& b) {
        modint res = a; res += b;
        return res;
    }
    friend constexpr modint operator-(const modint& a, const modint& b) {
        modint res = a;
        res -= b;
        return res;
    }
    friend constexpr modint operator*(const modint& a, const modint& b) {
        modint res = a;
        res *= b;
        return res;
    }
    friend constexpr modint operator/(const modint& a, const modint& b) {
        modint res = a;
        res /= b;
        return res;
    }
    friend constexpr bool operator==(const modint& a, const modint& b) {
        return a.val() == b.val();
    }
};

template <typename T>
constexpr T expo(T A, long long B) {
    T res{1};
    while (B) {
        if (B & 1) res *= A;
        B >>= 1;
        A *= A;
    }
    return res;
}

template <>
int modint<0>::mod_ = 1;

constexpr int mod = 1'000'000'007;
using Z = modint<mod>;
// using Z = double;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    std::cin >> tests;
    while (tests--) {
        int n;
        std::array<Z, 3> p;
        std::cin >> n;
        int pmx = -1;
        for (int k : {2, 1, 0}) {
            std::cin >> p[k];
            pmx = std::max(pmx, p[k].val());
            p[k] /= 100;
        }

        if (pmx == 100) {
            std::cout << (n == 1 ? 0 : -1) << '\n';
            continue;
        }

        --n;

        auto P = p;
        std::array<Z, 2> ans{};
        std::array<std::vector<std::array<Z, 2>>, 3> dp;
        for (int k : {0, 1, 2}) {
            dp[k].reserve(n + 1);
            dp[k].push_back({0, p[k]});
        }

        for (int i = 1; i <= n; i++) {
            ans = {};
            for (int k : {0, 1, 2}) {
                for (int j = 0; j < i; j++) {
                    Z mul = p[(k + 1) % 3] * (i + 1) / (i - j);
                    for (int t : {0, 1}) {
                        dp[k][j][t] *= mul;
                        ans[t] += dp[k][j][t];
                    }
                }
            }
            ans = {(1 + ans[0]) / ans[1], 1};
            for (int k : {0, 1, 2}) {
                P[k] *= p[k];
                dp[k].push_back({});
                for (int t : {0, 1})
                    dp[k][i][t] = ans[t] * P[k];
            }
        }

        std::cout << ans[0] << '\n';
    }

}

For convenience, let $$$A=\frac{a}{100}$$$, $$$B=\frac{b}{100}$$$, $$$C=\frac{c}{100}$$$.

First, let's deal with some corner cases. When $$$n=1$$$, the answer is $$$0$$$. When $$$[A=0] + [B=0] + [C=0] = 2$$$, the answer is $$$-1$$$, because no one can leave if only one move is possible. Make sure to deal with these two cases in this particular order, because the answer when $$$n=1$$$ and $$$[A=0] + [B=0] + [C=0] = 2$$$ are both satisfied is $$$0$$$.

Then, let's solve the problem with DP. Let $$$f_i$$$ be the expected number of rounds it takes to result in $$$1$$$ person, starting from $$$i$$$ people. In the base case, we have $$$f_1 = 0$$$. Then, the transition would be:

where $$$P(i, j)$$$ is the probability of transitioning from $$$i$$$ people to $$$j$$$ people in one round. Rearranging, that is,

$$$P(i, i)$$$ basically translates to the probability of having one type or three types of moves in the room in one round. Thus,

To calculate $$$P(i, j)$$$ where $$$i > j$$$, we can also count cases in which $$$j$$$ winning moves and $$$i - j$$$ losing moves are made. That is,

Then, our answer would just be $$$f_n$$$.

Overall, the complexity is $$$O(n^2\log n)$$$ if techniques like fast-power are used to calculate the powers and combination values. However, the constant can be very big. By precomputing these values, the complexity would be $$$O(n^2)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=63;
const ll  TMD=0;
const ll  INF=2147483647;
int T;
ll  n,k,ans;
int dif[N];
ll  f[LOGN][LOGN][2];
vector<int> v;

void init()
{
	f[0][0][0]=f[1][0][0]=f[1][0][1]=1;
	for(int i=2;i<LOGN;i++)
	{
	    for(int j=0;j<i;j++)
	    {
	        for(int k=0;k<=1;k++) 
	        {
				f[i][j][k]=f[i-1][j][k];
				if(j) f[i][j][k]+=f[i-1][j-1][k^1];
	        }
	    }
	}
		
}

void DP(int bt)
{
	if(bt<0) 
	{
		ans+=(dif[0]==k);
		return ;
	}
	if(v[bt])
	{
		if(bt==(int)v.size()-1) 
		{
			for(int i=bt;i;i--) ans+=f[i][k][1];
		}
		else 
		{
			int diff=dif[bt+1]+v[bt+1];
			if(k-diff>=0)   ans+=f[bt][k-diff][0];
			if(k-diff-1>=0) ans+=f[bt][k-diff-1][1];
		}
	}
	DP(bt-1);
}

int main()
{
	//freopen("test.in","r",stdin);
	
	init();
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%I64d%I64d",&n,&k);
    	v.clear();
    	while(n) v.push_back(n&1),n>>=1;
    	dif[(int)v.size()-1]=0;
    	for(int i=(int)v.size()-2;i>=0;i--) dif[i]=dif[i+1]+(v[i]^v[i+1]);
    	ans=0;
    	DP((int)v.size()-1);
		printf("%I64d\n",ans%1000000007); 
	}
	
	//fclose(stdin);
	return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,tt,ans;
int t[N],s[N],dt[N],ds[N];
int dp[N][N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d",&n,&tt);
    	for(int i=1;i<=n;i++) scanf("%d%d%d%d",&t[i],&s[i],&dt[i],&ds[i]);
    	ans=0;
    	for(int i=1;i<=tt;i++)
    	{
    		vector<pair<int,int> > v;
	    	for(int j=1;j<=n;j++) 
			{
				if(i+dt[j]>tt) v.push_back(make_pair(s[j],j));
				else           v.push_back(make_pair(ds[j],j));
			}
			sort(v.begin(),v.end());
			for(int j=1;j<=n;j++)
				for(int k=0;k<=i;k++)
					dp[i][j]=-INF;
			dp[0][0]=0;
			for(int j=1;j<=n;j++)
			{
				int num=v[j-1].second;
				if(i-t[num]>=0) ans=max(ans,dp[j-1][i-t[num]]+s[num]-v[j-1].first);
				for(int k=0;k<=i;k++)
				{
					dp[j][k]=dp[j-1][k];
					if(k-t[num]>=0) dp[j][k]=max(dp[j][k],dp[j-1][k-t[num]]+s[num]);
				}
			}
	    }
    	printf("%d\n",ans);
	}
	
	//fclose(stdin);
	return 0;
}

Consider:for a fixed problem set you choose,which problem will the hacker hack?

For problem $$$i$$$,$$$f_i \leq T-Σt$$$,hack it will decrease you score by $$$p_i$$$.

However,for problem $$$i$$$,$$$f_i >T-Σt$$$,hack it will decrease you score by $$$a_i$$$,since you don't have enough time to fix the bug.

Note $$$decrease_i$$$ as the score that actually decreased for the i-th hacked problem.Hacker'll hack the problem with the max $$$decrease$$$ value.

We find $$$decrease$$$ is depend on the value of $$$Σt$$$.

Enumeration $$$Σt$$$ from $$$0$$$ to $$$T$$$,calculate the corresponding $$$decrease$$$,then do classic knapsack DP.It's $$$O(n^2T)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,k,ls,lt;
ll  ans;
int x[N],a[N],S[N],s[N],t[N],nxt[N];
vector<int> p;

//

void build_nxt(int s[],int l)
{
	for(int i=1;i<l;i++)
	{
		int j=i;
		while(s[nxt[j-1]]!=s[i]&&j!=0) j=nxt[j-1];
		nxt[i]=(s[i]==s[nxt[j-1]])?nxt[j-1]+1:0;
	}
	//for(int i=0;i<l;i++) printf("%d ",nxt[i]);
	//printf("\n");
}

void KMP(int s[],int t[],int ls,int lt,vector<int> &v)
{
	build_nxt(t,lt);
	int ps=0,pt=0;
	while(1)
	{
		if(pt>=lt) 
		{
			v.push_back(ps-lt);
			pt=nxt[pt-1];
		}
		if(ps==ls) break;
		while(s[ps]!=t[pt])
		{
			if(!pt) break;
			else pt=nxt[pt-1];
		}
		if(s[ps]==t[pt]) ps++,pt++;
		else ps++,pt=0;
	}
}

//

//

ll md(ll a,ll b)	//a mod b
{
	if(a>0) return a%b;
	return (-(-a)%b+b)%b;	
}
		
void exgcd(ll &x,ll &y,ll a,ll b){
    if(!b){
        x=1;y=0;
        return ;
    }
    exgcd(x,y,b,a%b);
    ll xx=x,yy=y;
    x=yy;y=xx-(a/b)*yy;
}

ll solve_equation(ll a,ll b,ll k)	//solve ax=b(mod k),x>=0 and x is minimal
{
	ll x,y,g;
	md(a,k);md(b,k);
	exgcd(x,y,a,k); 	//ax+ky=gcd(a,k)
	g=a*x+k*y;
	if(b%g) return -1;
	return md(x*(b/g),k/g);
}

int check()
{
	for(int i=1;i<=n;i++) if(x[i]%k) return 0;
	return 1;
}

//


int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++)  scanf("%d",&x[i]);
    	for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    	if(check())
		{
			printf("0\n");
			continue;
		} 
    	for(int i=1;i<=n;i++)  S[i]=(S[i-1]+a[i])%k;
 		ls=2*n-2;lt=n-1;
 		for(int i=1;i<n;i++)   s[i-1]=a[i+1]%k;
 		for(int i=n;i<2*n;i++) s[i-1]=a[i-n+1]%k;
 		for(int i=1;i<n;i++)   t[i-1]=md(a[i]+x[i]-x[i+1],k);
 		p.clear();
    	KMP(s,t,ls,lt,p);
    	ans=INF*INF;
    	for(int i=0;i<p.size();i++)
    	{
	    	ll y=x[1]+S[1+p[i]],sol=solve_equation(S[n],-y,k);
	    	if(sol==-1) continue;
	    	ans=min(ans,sol*n+p[i]+1);
	    }
	    if(ans==INF*INF) printf("-1\n");
	    else printf("%I64d\n",ans);
	}
	
	//fclose(stdin);
	return 0;
}

Let's say $$$t = nm+p (0 \leq p<n)$$$ and $$$S$$$ is sum of all $$$a_i$$$.

We get $$$x_i + a_i + ... + a_{i + p} = x_{i + 1} + a_{i + 1} + ... + a_{i + p + 1}=-Sm (mod k)$$$

Thus $$$x_i + a_i = x_{i + 1} + a_{i + p + 1} (mod k)$$$ for $$$1\leq i \leq n-1$$$.

So we need to find $$$a_i + x_i - x_{i + 1}$$$ shifted in $$$a$$$, this is KMP.

Assume we have known $$$p$$$.Note $$$v=x_i + a_i + ... + a_{i + p}$$$,we also need $$$v+Sm=0(mod k)$$$.Use exgcd to get $$$m$$$.

Complexity:$$$O(n log n)$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> a(n);
                vector<int> b(n);

                for (int i = 0; i < n; i++) cin >> a[i];
                for (int i = 0; i < n; i++) cin >> b[i];

                vector<int> ord(n);
                iota(ord.begin(), ord.end(), 0);
                sort(ord.begin(), ord.end(), [&](int x, int y) {
                        if (b[x] == b[y]) return a[x] > a[y];
                        return b[x] == 1;
                });

                int ans = a[0] * b[0];
                int suma = 0, sumb = 0;

                for (int i = 0; i < n; i++) {
                        suma += a[ord[i]];
                        sumb += b[ord[i]];

                        ans = max(ans, suma * sumb);
                        ans = max(ans, a[i] * b[i]);
                }

                cout << ans << '\n';
        }

        return 0;
}

Consider greedy algorithm.

When all $$$b_i(1 \leq i \leq n)=-1$$$,obviously,the answer is $$$-min(a_i)$$$.

Otherwise,we choose all tuples which's $$$b_i=1$$$ firstly.Then choose tuples in descending order of $$$a_i$$$ value which's $$$b_i=-1$$$.The answer is the maximum in this process.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> ca(2 * n);
                vector<int> cb(2 * n);

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        ca[x] += 1;
                }

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        cb[x] += 1;
                }

                bool ok = 1;

                for (int i = 0; i < 2 * n; i++) {
                        if (ca[i] + cb[i] > n) {
                                ok = 0;
                        }
                }

                cout << (ok ? "YES" : "NO") << '\n';
        }
        
        return 0;
}

Note $$$k$$$ is the number with the highest sum of occurrences in $$$s$$$ and $$$t$$$.The answer is "YES" iff $$$occurrences(k) \leq n$$$.

If $$$occurrences(k) > n$$$,it means the total of numbers that are not $$$k$$$ is less than $$$n$$$.Obviously the answer is "NO".

Otherwise,we can use Mathematical induction to prove that there is a solution:

• 1.For two empty sets $$$s$$$,$$$t$$$,$$$occurrences(k) \leq n$$$ holds;

• 2.Assume for two empty sets $$$s$$$,$$$t$$$ if size $$$n$$$,$$$occurrences(k) \leq n$$$ holds.We do remove a $$$k$$$ from one set and remove a number which is not $$$k$$$ from another set.After that,the size becomes $$$n-1$$$,and $$$occurrences(k) \leq n-1$$$ holds.

#include<bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
using namespace std;
#define fastio  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define pb push_back
#define PI acos(-1)
#define pii pair<int,int>
#define endl "\n"
#define all(a) a.begin(),a.end()
#define len(s) (int)s.size()
#define F first
#define S second
const int mod=1e9+7;
int dp[20001][101][101];
int a[101];
const int add=10000;
const int L=-10000;
const int R=10000;
int f(int sum,int l,int r)
{
	//count number of non-empty subsequence of subarray [l,r] 
	//with adding=sum
	if( !(sum>=L and sum<=R))
		return 0;
	
	if(l==r)
	{

		if(sum==a[l])
			return 1;
		return 0;
	}
	if(dp[sum+add][l][r]!=-1)
		return dp[sum+add][l][r];
	int ans1=f(sum,l,r-1);
	int ans2=f(sum,l+1,r);
	int rem=0;
	if(l+1<=r-1)
		rem=f(sum,l+1,r-1);
	int ans3=0;
	if(l+1<=r-1)
		ans3=f(sum-a[l]-a[r],l+1,r-1)+(sum==(a[l]+a[r]));
	else
		ans3=(sum==(a[l]+a[r]));
	
	return dp[sum+add][l][r]=(((ans1+ans2)%mod-rem+mod)%mod+ans3)%mod;
}
void solve()
{
	int n,x;
	cin>>n>>x;
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++)
		cin>>a[i];
	if(n<3)
	{
		cout<<0;
		return ;
	}
	else
	{
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)
			a[i]-=x;
		int ans=0;
	
		for(int i=1;i<=n;i++)
		{
			for(int j=i+2;j<=n;j++)
			{
				ans+=f(0,i+1,j-1);
				ans%=mod;
			}
		}
		cout<<ans;
	}
}
signed main()
{
fastio
int TestCases=1;
//cin>>TestCases;
while(TestCases--)
{
solve();
cout<<endl;
}
}

Firstly,we substract all $$$a_i$$$ by $$$x$$$.Then the problem is equivent to count the number of subsequences which's sum is $$$0$$$.

Consider sort the array and do DP.Note $$$dp_{l,r,s}$$$ as the number of subsequences with $$$a_l$$$ as the head, $$$a_r$$$ as the tail, and $$$s$$$ as the sum.

For $$$dp_{l,r,0}(2\leq l \leq r \leq n-1)$$$,it's contribution is $$$dp_{l,r,0}*(l-1)*(n-r)$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        vector<int> fac(2222222);

        fac[0] = 1;
        for (int i = 1; i <= 2000000; i++) {
                fac[i] = (fac[i - 1] * i) % MOD;
        }

        auto binpow = [&](int x, int y) {
                int res = 1;

                while (y > 0) {
                        if (y & 1) (res *= x) %= MOD;

                        (x *= x) %= MOD;
                        y >>= 1;
                }

                return res;
        };

        vector<int> inv(2222222);

        inv[2000000] = binpow(fac[2000000], MOD - 2);
        for (int i = 1999999; i >= 0; i--) {
                inv[i] = (inv[i + 1] * (i + 1)) % MOD;
        }

        auto comb = [&](int n, int r) {
                if (n < r) {
                        cout << "hi\n";
                        exit(0);
                }
                return fac[n] * inv[r] % MOD * inv[n - r] % MOD;
        };

        int t;
        cin >> t;

        while (t --> 0) {
                int n, m;
                cin >> n >> m;
                // general case: a1 + a2 + a3 + .. + an = m -> C(m - 1, n - 1)
                int ans = comb(m - 1, n - 1);

                if (n - 1 <= m - (m + 1) / 2) {
                        ans -= n * comb(m - (m + 1) / 2 - 1 + 1, n - 1 - 1 + 1);
                }

                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        
        return 0;
}

As we all know,the sum of the two sides of a triangle is greater than the third side.Similarly,we can infer condition $$$3$$$ is equviant to $$$max(a_i)< \lceil m/2 \rceil$$$.

What's the number of arrays satisfying the following condition?

• 1.All $$$a_i$$$ are positive integers;

• 2.$$$\Sigma a_i=m$$$.

The answer is $$$C^{m-1}_{n-1}$$$.It's a classic problem.

$$$C^i_j+C^{i-1}_j+...+C^j_j=C^{i+1}_{j+1}$$$.

We find it's easier to calculate bad arrays.When $$$max(a_i)=\lceil m/2 \rceil,\lceil m/2 \rceil+1,...$$$,$$$a$$$ is a bad array.

The total of bad array is $$$n*(C^{m-\lceil m/2 \rceil}_{n-2}+C^{m- \lceil m/2 \rceil-1}_{n-2}+...)=n*C^{\lfloor m/2 \rfloor}_{n-1}$$$.

The final answer is $$$C^{m-1}_{n-1}-n*C^{\lfloor m/2 \rfloor}_{n-1}$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n, m, s;
                cin >> n >> m >> s;

                set<pair<int, int>> st;
                st.insert({s, 0});

                for (int i = 0; i < m; i++) {
                        int l, r;
                        cin >> l >> r;

                        vector<pair<int, int>> del;
                        int mnl = INFF, mnr = INFF;
                        for (auto it = st.lower_bound({l, 0}); it != st.end(); it++) {
                                if (it->fi > r) break;

                                if (l - 1 >= 1) {
                                        mnl = min(mnl, it->se + it->fi - l + 1);
                                }

                                if (r + 1 <= n) {
                                        mnr = min(mnr, it->se + r + 1 - it->fi);
                                }

                                del.push_back(*it);
                        }
                        
                        for (auto p : del) st.erase(p);

                        auto it = st.lower_bound({l - 1, 0});
                        if (it != st.end() && it->fi == l - 1) {
                                mnl = min(mnl, it->se);
                                st.erase(it);
                        }

                        auto it2 = st.lower_bound({r + 1, 0});
                        if (it2 != st.end() && it2->fi == r + 1) {
                                mnr = min(mnr, it2->se);
                                st.erase(it2);
                        }

                        if (l - 1 >= 1) {
                                st.insert({l - 1, mnl});
                        }

                        if (r + 1 <= n) {
                                st.insert({r + 1, mnr});
                        }
                }

                int ans = INFF;

                for (auto [pos, cost] : st) {
                        ans = min(ans, cost);
                }

                cout << ans << '\n';
        }
        
        return 0;
}

The original idea of this problem is using segment tree, hence the $$$n \leq 2\cdot 10^5$$$ constraint. However, this problem can be solved easier by using std::set.

For this problem, we can do DP to solve the problem.

Define $$$dp_i$$$ after the $$$j$$$-th attack as minimum energy needed to avoid the first $$$j$$$ attacks and we ended up at tile $$$i$$$. If we try updating all $$$n$$$ indices for each attack (by doing $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ for all $$$1 \leq j \leq n$$$), that will cost $$$O(n)$$$ transition, which means the complexity will be $$$O(n^2m)$$$ per test case. Since it's too slow, we need some observation.

Observation. For the $$$k$$$-th attack, we only need to update two DP indices each attack and it's optimal to do $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ where $$$i=l_k-1$$$ or $$$i=r_k+1$$$ (if those two indices actually exist inside the range $$$[1,n]$$$) and $$$l_k \leq j \leq r_k$$$

Proof. Assume that everytime the boss attacks, it is sometimes optimal for us to move if we didn't stand inside the incoming lazer previously. So, assume at some point, we went to the right $$$y$$$ tiles as the "optimal" route. Then, there are three cases for the next attack:

• The current optimal route involves going to the left by $$$x$$$ tiles $$$(x > y)$$$. In this case, the current optimal is not the same as the previous optimal, since we could've just not move in previous turn and then move to the left by $$$x-y$$$ tiles.

• The current optimal route involves going to the left by $$$x$$$ tiles $$$(0 < x \leq y)$$$. In this case, the current optimal is also not the same as the previous optimal, since we could've just not move in previous turn and then move to the right by $$$y-x$$$ tiles.

• The current optimal route involves going to the right by $$$x$$$ tiles $$$(x \geq 0)$$$. In this case, there is an alternative solution, where we could've just not move in previous turn and then move to the right by $$$x+y$$$ tiles. It'll result with the same energy spent.

So, it is optimal to do nothing if we don't stand inside the lazer.

If we do stand inside the lazer (assume it's the $$$j$$$-th lazer), it is optimal to go to either $$$l_j-1$$$ or $$$r_j+1$$$, since with the same idea as above, one of these tiles are either the most optimal solution, or one of the most optimal solution (think of it like a waterfall :]).

Now, with this in mind, we can implement this in $$$O(n\sum_{i=1}^n (r_i-li))$$$ per test case. Since it's still too slow, we can optimize it again. Notice that for each attack, we're only interested from the updates that actually give paths, not the one getting blocked by the lazer. So, we will try to implement this using C++ std::set. First, create the set $$$route$$$ which stores all previously updated $$$dp$$$ indices that give paths (since we update the tiles that will get hit by the lazer for each attack to $$$INF$$$ again after updating $$$dp{li-1}$$$ and $$$dp{r_i+1}$$$). Set $$$dp_i=INF$$$ for all $$$1 \leq i \leq n,i \neq s$$$, $$$dp_s=0$$$, and . Then, do the following for the j-th attack:

• Find all the element $$$k$$$ in $$$route$$$ such that $$$l_j \leq k \leq rj$$$.

• For each of the element satisfying the constraint above, update $$$dp{lj-1}$$$ to $$$\min(dp{l_j-1},dp_k+k-lj+1)$$$ and $$$dp{rj+1}$$$ to $$$\min(dp{r_j+1},dp_k+r_j+1-k)$$$

• Set all $$$dp_k$$$ to $$$INF$$$, remove all elements satisfying the constraint above, and then add $$$l_j-1$$$ and $$$r_j+1$$$ to $$$route$$$

The time complexity of this would be $$$O(m\log m)$$$ with $$$O(n)$$$ initializer and $$$O(n)$$$ finding optimal of each $$$dp$$$ index for each test case.

To optimize this even further, notice that after all the $$$m$$$ attacks, every index outside the $$$route$$$ would have the value of $$$INF$$$, so we only need to check the minimum from all $$$dp$$$ with indices inside $$$route$$$ (which is $$$O(m)$$$) and only to reset those indices as well for the next test case (which is also $$$O(m)$$$).

Once again, beware of the fact that $$$l_i-1$$$ or $$$r_i+1$$$ might be out of the arena range.

Time complexity: $$$O(m\log m)$$$

Bonus: Solve the problem if $$$n \leq 10^9$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        vector<bool> ok(22222, 0);

        auto conv = [&](int x) {
                int res = 0;

                while (x > 0) {
                        int y = x % 10;

                        res += y * y;
                        x /= 10;
                }

                return res;
        };

        for (int i = 1; i <= 16200; i++) {
                int x = i;

                set<int> vis;
                
                while (!vis.count(x)) {
                        vis.insert(x);

                        int y = conv(x);
                        if (x == y) {
                                ok[i] = 1;
                        }
                        x = y;
                }
        }
        
        vector<vector<int>> dp(222, vector<int>(22222)); // digit - sum
        dp[0][0] = 1;

        for (int i = 1; i <= 200; i++) {
                for (int j = 0; j < 20000; j++) {
                        for (int k = 0; k <= 9; k++) {
                                dp[i][j + k * k] += dp[i - 1][j];
                                dp[i][j + k * k] %= MOD;
                        }
                }
        }

        int t;
        cin >> t;

        while (t --> 0) {
                string l, r;
                cin >> l >> r;

                auto calc = [&](string s, bool on) {
                        int res = 0;
                        int n = (int)s.length();
                        int cur = 0;

                        for (int i = 0; i < n; i++) {
                                for (int j = 0; j < s[i] - '0'; j++) {
                                        for (int k = cur + j * j; k <= 16200; k++) {
                                                res += ok[k] * dp[n - i - 1][k - (cur + j * j)];
                                                res %= MOD;
                                        }
                                }
                                cur += (s[i] - '0') * (s[i] - '0');
                        }

                        if (ok[cur] && on) res += 1;

                        return res;
                };
                
                int ans = calc(r, 1) - calc(l, 0);
                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        return 0;
}

Notice that the biggest number we can obtain after exactly one operation is $$$81 \cdot 200 = 16200$$$.

We can solve the problem with digit DP (or DFS with memorization). Let $$$AN$$$ be the number of happy numbers less than or equal to $$$N$$$. Our answer would then be $$$A{ri} - A{l_i - 1}$$$.

Now we are interested in calculating $$$AN$$$ for some integer $$$N$$$. We do a DFS from the leftmost digit to the rightmost digit. Let $$$f{i, j}$$$ denote the number of happy numbers, less than or equal to $$$N$$$, with the sum of the first $$$i$$$ digits squared equal to $$$j$$$. We can do a DFS from left to right, taking note of whether the current digit sequence is exactly the same as $$$N$$$'s first digits; if not so, we can memorize the answer with $$$f_{i, j}$$$ (to avoid repeated calculations).

It is not hard to see that we are expected to reach every state once, and we can re-use $$$f$$$ over all test cases. Thus, the time complexity is $$$O(DS)$$$, where $$$D \leq 201$$$ is the number of digits and $$$S \leq 16200$$$ is the digit-squared sum.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#define int long long
const int bk=500;
namespace sumadd {
   int tag[bk],pb[bk],pre[bk][bk];
   void addib(int l,int r,int id,int v) {
      for(int i=0,x=0;i<=bk-1;++i){if(l<=i&&i<=r)x+=v;x+=tag[id];pre[id][i]+=x;}
      tag[id]=0;
   }
   void add(int l,int r,int v) {
      if(l/bk==r/bk) {
         addib(l%bk,r%bk,l/bk,v);
         for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
         return;
      }
      if(l%bk!=0) {addib(l%bk,bk-1,l/bk,v);l+=bk-l%bk;}
      if(r%bk!=bk-1) {addib(0,r%bk,r/bk,v);r-=r%bk+1;}
      while(l<=r) {tag[l/bk]+=v;l+=bk;}
      for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
   }
   int sum(int l,int r) {
      if(l/bk==r/bk) {
         return (r-l+1)*tag[l/bk]+pre[l/bk][r%bk]-(l%bk==0?0:pre[l/bk][l%bk-1]);
      }
      int sum=0;
      if(l%bk!=0) {sum+=tag[l/bk]*(bk-l%bk)+pre[l/bk][bk-1]-(l%bk==0?0:pre[l/bk][l%bk-1]);l+=bk-l%bk;}
      if(r%bk!=bk-1) {sum+=tag[r/bk]*(r%bk+1)+pre[r/bk][r%bk];r-=r%bk+1;}
      sum+=pb[r/bk]-(l==0?0:pb[l/bk-1]);
      return sum;
   }
   void cln() {
      for(int i=0;i<bk;++i) {
         tag[i]=pb[i]=0;
         for(int j=0;j<bk;++j)
            pre[i][j]=0;
      }
   }
}
pair<int,int> ivl[bk][bk];
array<int,4> qry[bk*bk];
int cnt[bk*bk],ans[bk*bk],flag[bk*bk];
vector<int> lp={0};
void Delta() {
   int n,m,q;
   cin >> n >> m >> q;
   for(int i=1,l,r;i<=m;++i) {
      cin >> l >> r;
      ivl[i/bk][i%bk]={l,r};
      lp.push_back(lp.end()[-1]+r-l+1);
   }
   cerr << endl;
   lp.push_back(2147483647);
   for(int i=1,o,l,r,v;i<=q;++i) {
      cin >> o >> l >> r;
      if(o==1) {cin >> v;qry[i]={1,l,r,v};sumadd::add(l,r,v);}
      else {
         auto il=lower_bound(lp.begin(),lp.end(),l-1),ir=prev(lower_bound(lp.begin(),lp.end(),r+1));
         qry[i]={2,il-lp.begin()+1,ir-lp.begin(),0};
         if(qry[i][1]==qry[i][2]+2) {
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            l-=*prev(il);r-=*prev(il);
            ans[i]=sumadd::sum(t.first+l-1,t.first+r-1);
            flag[i]=true;
            continue;
         }
         if(qry[i][1]==qry[i][2]+1) {
            ans[i]=sumadd::sum(ivl[qry[i][2]/bk][qry[i][2]%bk].first+l-*prev(il)-1,ivl[qry[i][2]/bk][qry[i][2]%bk].second);
            ans[i]+=sumadd::sum(ivl[qry[i][1]/bk][qry[i][1]%bk].first,ivl[qry[i][1]/bk][qry[i][1]%bk].first+r-*ir-1);
            flag[i]=true;
            continue;
         }
         if(il!=lp.begin()) {
            int p=qry[i][1]-1;l=*il-l+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.second+1-l,t.second);
         }
         if(next(ir)!=lp.end()) {
            r-=*ir;
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.first,t.first+r-1);
         }
         if(flag[i]) ans[i]=-ans[i];
      }
   }
   sumadd::cln();
   for(int k=0;k<bk;++k) {
      int sum=0;
      for(int i=0;i<bk;++i) {
         auto t=ivl[k][i];
         if(t==pair<int,int>{0,0}) continue;
         cnt[t.first]++;
         cnt[t.second+1]--;
      }
      for(int j=1;j<=2;++j)
         for(int i=1;i<=n;++i)
            cnt[i]+=cnt[i-1];
      for(int i=1;i<=q;++i)
         if(qry[i][0]==1) {
            sum+=qry[i][3]*(cnt[qry[i][2]]-(qry[i][1]==0?0:cnt[qry[i][1]-1]));
         }
         else
            if(!flag[i]&&qry[i][1]<=k*bk&&k*bk+bk-1<=qry[i][2]) ans[i]+=sum;
      for(int i=1;i<=n;++i) cnt[i]=0;
   }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==1)
         sumadd::add(qry[i][1],qry[i][2],qry[i][3]);
      else {
         if(flag[i]) continue;
         int l=qry[i][1],r=qry[i][2];
         if(l>r) continue;
         if(l/bk==r/bk&&l%bk!=0&&r%bk!=bk-1) {
            for(int j=l;j<=r;++j) {
               auto t=ivl[j/bk][j%bk];
               ans[i]+=sumadd::sum(t.first,t.second);
            }
            continue;
         }
         while(l%bk!=0)    {auto t=ivl[l/bk][l%bk];ans[i]+=sumadd::sum(t.first,t.second);l++;}
         while(r%bk!=bk-1) {auto t=ivl[r/bk][r%bk];ans[i]+=sumadd::sum(t.first,t.second);r--;}
      }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==2)
         cout << ans[i] << ' ';
   cout << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

Consider SQRT decomp for $$$[l_i,r_i]$$$, putting each $$$sqrt(n)$$$ of $$$[l_i,r_i]$$$ into a block, and maintaining the sum of the group, and the number of occurrences in the block in each original array $$$a_i$$$.

Enumerate all blocks, and if a query completely contains an sqrt, then +=sum is added to the result of the query.

If we add, then sum+= the number of times the number * added value. (This can be done with two times perfix sums)

For queries that are not complete blocks, consider direct brute force maintenance of the A-array and query, it has $$$n^{1.5}$$$ query operations and n modification operations, so we can use a partitioned data structure to do $$$O(1)$$$ queries, $$$O(n^{0.5})$$$ modifications.

So, the total complexity is $$$O(n^{1.5})$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#define int long long

const int MOD=998244353;
void Delta() {
   int a,b,c,d;
   cin >> a >> b >> c >> d;
   cout << (a+b>c+d?"YES":"NO") << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

The probability of Alice's winning is strictly higher than Bob's iff $$$l_1+r_1>l_2+r_2$$$.

Submitting this code directly will get ILE, please delete cerr and submit.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
namespace Fact {
   vector<char> isPrime;
   vector<int> Prime,OneFac;
   void GetPrime(int n){for(int i=0;i<n;++i)isPrime[i]=1;isPrime[1]=1;for(int i=2;i<=n;i++){if(isPrime[i])Prime.push_back(i);for(int j:Prime){if(i*j>n) break;isPrime[i*j]=0;OneFac[i*j]=j;if(i%j==0)break;}}}
   void Fac_dfs(int x,int y,vector<int>& ans,vector<pair<int,int>>& FacList){if(x==(long long)(FacList.size())){ans.push_back(y);return;}int k=1;for(int i=0;i<=FacList[x].second;++i){Fac_dfs(x+1,y*k,ans,FacList);k*=FacList[x].first;}}
   vector<pair<int,int>>GetPrimeFac(int a){vector<pair<int,int>>answer;if(isPrime[a])return(vector<pair<int,int>>{pair<int,int>{a,1}});answer.push_back({OneFac[a],1});a/=OneFac[a];while(!isPrime[a]){if(OneFac[a]==answer.back().first)answer.back().second++;else answer.push_back({OneFac[a],1});a/=OneFac[a];}if(a==answer.back().first)answer.back().second++;else answer.push_back({a,1});return(answer);}
   vector<int>GetFacList(int a){vector<int> ans;vector<pair<int,int>>FacList=GetPrimeFac(a);Fac_dfs(0,1,ans,FacList);return(ans);}
   void init(int n){isPrime.resize(n+2);OneFac.resize(n+2);GetPrime(n);}
   void init(){init(10000005);}
};
#define int long long

const int MOD=998244353;
void Delta() {
   int a,b;
   cin >> a >> b;
   if(Fact::isPrime[a]||(a/Fact::OneFac[a]<b)) cout << "NO" << endl;
   // in code "OneFac" is The smallest non-1 factor.
   else {
      cout << "YES" << endl;
      for(int i=1;i<b;++i) cerr << Fact::OneFac[a] << ' ';
      cerr << a-(b-1)*Fact::OneFac[a] << endl;
   }
}
signed main() {
   Fact::init(100001);
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

Let's say we finally get the gcd $$$x$$$, so all $$$a_i$$$ are multiples of $$$x$$$.

We want all $$$a_i$$$to be positive, so every $$$a_i$$$ is at least $$$x$$$, and all sums are at least $$$kx$$$ and sum is divisible by $$$x$$$ (You have some $$$a_i$$$ that is divisible by $$$x$$$, add it up, and it's still divisible by $$$x$$$).

Since we already know sum (is $$$n$$$), $$$x$$$ can only be a factor of $$$n$$$, Since $$$x>1$$$, just to take the smallest non-1 factor of $$$n$$$ and check. If $$$kx$$$ is less than $$$n$$$, then just put all the rest on $$$a_k$$$, which still guarantees that gcd=x.

(The constructional output is given in cerr of code for help understand)

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
int n,m,sum;
map<int,int> a,b,c;
vector<pair<int,int>> Q;
void dfs(int idx,int A,int B,int C) {
   if(idx==(int)Q.size()) {
      sum+=a[A]*b[B]*c[C];
      return;
   }
   for(int i=0,t1=1;i<=Q[idx].second;++i,t1*=Q[idx].first)
      for(int j=i,t2=1;j<=Q[idx].second;++j,t2*=Q[idx].first)
         for(int k=j,t3=1;k<=Q[idx].second;++k,t3*=Q[idx].first)
            if(k==Q[idx].second)
               dfs(idx+1,A*t1,B*t2,C*t3);
}
void Delta() {
   cin >> n >> m;
   for(auto i:{&a,&b,&c})
      for(int j=1,x;j<=n;++j) {
         cin >> x;
         ++(*i)[x];
      }
   for(int i=2;i*i<=m;++i)
      while(m%i==0) {
         if(Q.empty()||Q.end()[-1].first!=i) Q.push_back({i,1});
         else Q.end()[-1].second++;
         m/=i;
      }
   if(m!=1)
      if(Q.empty()||Q.end()[-1].first!=m) Q.push_back({m,1});
      else Q.end()[-1].second++;
   else;
   dfs(0,1,1,1);
   cout << sum << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

If a number is less than $$$10^9$$$, it has a maximum possible factor of $$$1344$$$, enumerate two factors of $$$m$$$, then divide the third factor, and then use map to do count to pass.

In this table you can find all the values of $$$\text{d}(n)$$$ and $$$ω(n)$$$ for your future use :)

upd:

$$$\text{d}(n)$$$ = the number of different factors, and $$$ω(n)$$$ = the number of different prime factors

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
 
#define int long long
 
const int MOD=998244353;
int a[500001];
void Delta() {
   int n,x; cin >> n >> x;
   if(x<n-1||x>(n/2)*(n-n/2)) {
      cout << -1 << endl;
      return;
   }
   for(int i=2;i<=n/2+1;++i) cout << i-1 << ' ' << i << endl;
   x-=n-1;
   for(int i=n/2+2;i<=n;++i) {
      cout << min(x,n/2-1)+1 << ' ' << i << endl;
      x-=min(x,n/2-1);
   }
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

The key to solving the problem is — consider constructing a tree with the highest score first.

It's obvious all leaf have the same LCA (othwise,link leaves with smaller depths next to leaves with larger depths, and the score will not decrease) .Note $$$x$$$ as the number of leaf nodes,then the score is $$$x(n-x)$$$,when $$$x=\lfloor\frac{n}{2}\rfloor$$$,it reaches the maximum.

From the tree with the highest score, we can easily construct a tree with any score (by moving each leaf node up).

For convenience,note $$$A={a_1,a_2,...,a_n}$$$ and $$$B={a_{n+1},a_{n+2},...,a_{2n}}$$$($$$A,B$$$ are circular).

Calculate $$$preA$$$ and $$$sufB$$$:

• $$$\text{preA}_i:\max(a_j+...+a{i-1}+a_{i})$$$;

• $$$\text{sufB}_i:\max(b_i+b_{i+1}+...+b_{j})$$$;

This can be solved using monotonic stacks in $$$\Theta(n)$$$.

Then reverse $$$A,B$$$ and do it again.

The answer is the maximum of the following values:

• $$$\max(\text{preA}_i);$$$

• $$$\max(\text{sufB}_i);$$$

• $$$\max(\text{preA}_i+\text{sufB}_{i+1}).$$$

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=3000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
ll  ans;
int a[N],b[N],Q[N];
ll  Sa[N],Sb[N],prea[N],sufb[N];

void solve()
{
	for(int i=1;i<=n;i++)   a[i+n]=a[i],b[i+n]=b[i];
	for(int i=1;i<=n*2;i++) Sa[i]=Sa[i-1]+a[i],Sb[i]=Sb[i-1]+b[i];
	int head=1,tail=0;
	for(int i=1;i<=n*2;i++)
	{
		if(i>n)
		{
			while(i-Q[head]>n) head++;
			prea[i-n]=Sa[i]-Sa[Q[head]];
		}	
		while(head<=tail&&Sa[Q[tail]]>Sa[i]) tail--;
		Q[++tail]=i;
	}
	head=1;tail=0;
	for(int i=n*2;i;i--)
	{	
		while(head<=tail&&Sb[Q[tail]]<Sb[i]) tail--;
		Q[++tail]=i;
		if(i<=n)
		{
			while(Q[head]-i+1>n) head++;
			sufb[i]=Sb[Q[head]]-Sb[i-1];
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,prea[i]);
	for(int i=1;i<=n;i++) ans=max(ans,sufb[i]);
	for(int i=1;i<n;i++)  ans=max(ans,prea[i]+sufb[i+1]);
	ans=max(ans,prea[n]+sufb[1]);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&b[i]);
		ans=-INF;
		solve();
		for(int i=1,j=n;i<j;i++,j--) swap(a[i],a[j]),swap(b[i],b[j]);
		solve();
		cout<<ans<<'\n';
	}
	
	return 0;
}

We can see how to merge the largest subsegment of two intervals and by GSS1 in $$$\Theta(1)$$$ time, so using a seg tree and just enumerates all possible k and computs it in $$$O(\log n)$$$ time. This is $$$O(n\log n)$$$.

As you can see, each query is a prefix or suffix of a single array, so we can use the prefix sum and the suffix sum, this is $$$\Theta(n)$$$.

I mentioned a minimum-memory solution in the announcement comment, so now explain how to do $$$\text{12,000 KB}$$$.

For this $$$\Theta(n)$$$ level's memory we can only save int32 a[].

For the prefix sum, just save the value of the previous one, and then add it up, you can do $$$\Theta(1)$$$ memory.

For suffix sum, do the normal suffix sum first, and save the suffix sum values on all $$$k·\sqrt{n}$$$ locations. Then compute each sqrt block separately, $$$\Theta(\sqrt{n})$$$ saves its suffix, computes its perfix recursively, and releases the memory after the calculation is complete.

This allows us to achieve memory complexity $$$\Theta(\text{sqrt})$$$ and time complexity $$$\Theta(n)$$$ in addition to "int32 a[]".

It's $$$\text{12,000 KB}$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
int a[3000010];
#define int long long
#define B 1000
class node{public:int sum,lm,rm,ans;}temp;
inline void merge1(node&a,node&l,node&r){a={l.sum+r.sum,max(l.lm,l.sum+r.lm),max(r.rm,r.sum+l.rm),max({l.ans,r.ans,l.rm+r.lm})};}
inline void merge2(node&a,node&l,node&r){a={l.sum+r.sum,min(l.lm,l.sum+r.lm),min(r.rm,r.sum+l.rm),min({l.ans,r.ans,l.rm+r.lm})};}
inline node i2node(int x){return {x,x,x,x};}
node sufb[1500010/B+10],sufnb[1500010/B+10],tsuff[B+10],tsufnf[B+10];
void Delta() {
   int n,s=-2147483648,sum=0,flag=true,mx=-2147483648;cin >> n;
   for(int i=1;i<=n*2;++i) {
      cin >> a[i];sum+=(int)a[i];
      flag&=a[i]<0;mx=max(mx,(int)a[i]);
   } 
   node pre=i2node(0),pren=i2node(0),suf=i2node(0),sufn=i2node(0);
   for(int i=n;i>=1;--i) {
      temp=i2node(a[i]);
      merge1(suf,temp,suf);
      temp=i2node(a[i+n]);
      merge1(sufn,temp,sufn);
      if(i%B==0) {
         sufb[i/B]=suf;
         sufnb[i/B]=sufn;
      }
   }
   for(int i=1;i<=n;++i) {
      temp=i2node(a[i]);
      merge1(pre,pre,temp);
      temp=i2node(a[i+n]);
      merge1(pren,pren,temp);
      if(i%B==0||i==1) {
         tsuff[B]=sufb[i/B+1];
         tsufnf[B]=sufnb[i/B+1];
         for(int j=(B-1);j>=1;--j) {
            temp=i2node(i-(i==1)+j>n?0:a[i-(i==1)+j]);
            merge1(tsuff[j],temp,tsuff[j+1]);
            temp=i2node(i-(i==1)+j+n>2*n?0:a[i-(i==1)+j+n]);
            merge1(tsufnf[j],temp,tsufnf[j+1]);
         }
      }
      merge1(temp,pren,tsuff[i%B+1]);
      merge1(temp,temp,pre);
      merge1(temp,temp,tsufnf[i%B+1]);
      s=max(s,temp.ans);
   }
   pre=pren=suf=sufn=i2node(0);
   for(int i=n;i>=1;--i) {
      temp=i2node(a[i]);
      merge2(suf,temp,suf);
      temp=i2node(a[i+n]);
      merge2(sufn,temp,sufn);
      if(i%B==0) {
         sufb[i/B]=suf;
         sufnb[i/B]=sufn;
      }
   }
   for(int i=1;i<=n;++i) {
      temp=i2node(a[i]);
      merge2(pre,pre,temp);
      temp=i2node(a[i+n]);
      merge2(pren,pren,temp);
      if(i%B==0||i==1) {
         tsuff[B]=sufb[i/B+1];
         tsufnf[B]=sufnb[i/B+1];
         for(int j=(B-1);j>=1;--j) {
            temp=i2node(i-(i==1)+j>n?0:a[i-(i==1)+j]);
            merge2(tsuff[j],temp,tsuff[j+1]);
            temp=i2node(i-(i==1)+j+n>2*n?0:a[i-(i==1)+j+n]);
            merge2(tsufnf[j],temp,tsufnf[j+1]);
         }
      }
      merge2(temp,pren,tsuff[i%B+1]);
      merge2(temp,temp,pre);
      merge2(temp,temp,tsufnf[i%B+1]);
      s=max(s,sum-temp.ans);
   }
   cout << (flag?mx:s) << '\n';
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
 
#define int long long
 
const int MOD=998244353;
int a[200001],b[200001],vis[200001];
vector<int> Q[200001];
void dfs(int x) {
   if(vis[x]) return;
   vis[x]=true;
   for(int i:Q[x]) dfs(i);
}
void Delta() {
   int cnt=0,blk=0,n; // count,block number
   cin >> n;
   for(int i=1;i<=n;++i) {
      cin >> a[i];
      b[i]=a[i];
      Q[i].clear();
      vis[i]=0;
   }
   sort(b+1,b+1+n);
   for(int i=1;i<=n;++i) 
      if(a[i]!=b[i]) {
         Q[a[i]].push_back(b[i]);
         Q[b[i]].push_back(a[i]);
      } else cnt++;
   for(int i=1;i<=n;++i)
      if(!vis[a[i]]&&a[i]!=b[i]) {
         blk++;
         dfs(a[i]);
      }
   if(n==2) {
      if(cnt==2) cout << 0 << endl;
      else cout << -1 << endl;
      return;
   }
   if(cnt!=0) cout << blk+(n-cnt) << endl;
   else if(blk==1) cout << n+2 << endl;
   else cout << n+blk << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

Compare the original array (say $$$a$$$) to the sorted one (say $$$b$$$). Since we can move only one token at once, in one move we can place at max one token to its correct place. So let's try to minimise the number of moves that don't do this.

To make optimal moves, model a directed multi-edged graph. Start with only vertices ($$$1$$$ to $$$n$$$), no edges, and add a directed edge from $$$a[i]$$$ to $$$b[i]$$$ when $$$a[i]!=b[i]$$$, for each $$$i$$$ (meaning that $$$b[i]$$$ should be placed in place of $$$a[i]$$$).

We can follow an optimal scheme like this: For now let us assume there is at least one position where correct token is placed (let it be $$$p$$$). Choose an incorrectly placed token, place it on top of $$$p$$$. This creates a gap. Place the correct token for this place. This moves the gap somewhere else. Again choose a corect token for the gap and so on. In the end, place the token stacked on top of $$$p$$$ into the gap, close the gap, and all the tokens we touched are placed correctly.

In the graph, placing a token from $$$b[i]$$$ to gap at $$$a[i]$$$ would mean moving from $$$a[i]$$$ to $$$b[i]$$$ in the graph along an edge and removing the edge. Thus the problem reduces to removing all edges of the graph in minimum number of moves.

The graph is split into disjoint connected componnts. We can thus independently resolve each component optimally for minimum number of moves.

Next, we prove that a connected component is always an euler circuit.

Claim $$$1$$$: The component would have a cycle. If it doesn't, then following some path $$$a \rightarrow b \rightarrow ...$$$, we will reach a dead end, which means that the last element has no place to go, which is not true since it belongs to the array and must have a correct position to be placed at. By induction, we can keep removing cycles (by moving along them and removing edges), and so the component is basically a set of directed cycles intersecting at vertices.

Claim $$$2$$$: It will hence form an euler circuit. Let us go along a cycle. It starts at $$$v$$$, ends at $$$v$$$. Now if there is a cyce intersecting at some vertex $$$v'$$$ in the cycle, on reaching $$$v'$$$ resolve that cycle, return at $$$v'$$$, continue on the older cycle. By this inductive argument, we can cover all edges exactly once and return to $$$v$$$, making an euler circuit.

To find the precise number of moves to resolve a component involving $$$s$$$ tokens, we need to create a gap in $$$1$$$ move, place $$$s-1$$$ tokens correctly, and place the last token we moved initially. Total $$$s+1$$$ moves. To create a gap, we need to place a token from our position to some position not in the component.

Now, proper casework:

Let the number of tokens not placed correctly be $$$co$$$. Let the number of disjoint connected components be $$$x$$$.

If $$$co<n$$$: There is always a correctly placed position to stack our token on and create a gap. So, each component of size s will be resolved in $$$s+1$$$. So total $$$co+x$$$ moves.

If $$$x>1$$$: Since there are $$$>1$$$ components, we can use a position from the other component to create gap for one component. Again $$$co+x$$$.

$$$co==n$$$ and $$$x==1$$$: It may be a single cycle, or $$$>1$$$ joint cycles. If there are $$$>1$$$ joint cycles, resolve one of the cycles, then it reduces to the cases above. Totals to $$$n+2$$$ moves. For exactly one cycle, graph is $$$1 \rightarrow 2 \rightarrow ...n \rightarrow 1$$$. So stack $$$1$$$ on $$$2$$$, resolve rest $$$n-2$$$, total $$$n-1$$$. Then resolve $$$1$$$ and $$$2$$$ which takes $$$3$$$ moves. So total again is $$$n+2$$$. Since $$$n+1$$$ is not possible in this case, and we construct a solution in $$$n+2$$$, it is optimal.

Final solution:

1. $$$(co < n)$$$ or $$$(x>1)$$$ : $$$co+x$$$

2. $$$(co==n)$$$ and $$$(x==1)$$$ : $$$n+2$$$

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

#define int long long

void test_case() {
	int n; cin >> n;
	int a = floor(sqrt(n));
	int b = (n + a - 1) / a;
	cout << a * 2 + b * 2 << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

If $$$n$$$ is a perfect square number, we find that the square dyeing scheme is always optimal.The answer is $$$4\sqrt{n}$$$.

Otherwise,if $$$n-\lfloor \sqrt{n} \rfloor ^2 \leq \lfloor \sqrt{n} \rfloor$$$,the answer is $$$4\lfloor \sqrt{n} \rfloor+2$$$.Otherwise the answer is $$$4\lfloor \sqrt{n} \rfloor+4$$$.

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; cin >> t;
	while(t--) {
		int n; cin >> n;
		std::vector<vector<int>> v(2);
		std::vector<int> cnt(2*n + 10);
		for(int i = 0; i < 2; i++) {
			v[i].resize(n);
			for(int &u:v[i]) {
				cin >> u;
				cnt[u]++;
			}	
		}
		int mex = 0;
		while(cnt[mex]) mex++;
		int ans = mex * (n&1);
		for(int i = 0; i < n; i++) {
			int val = v[1 ^ (i%2)][i];
			if(!(n&1)) {
				int cur_mex;
				if(val > mex || cnt[val] > 1) cur_mex = mex;
				else cur_mex = val;
				ans = max(ans, cur_mex); 
			}
		}
		cout << ans << "\n";
	}
}

If $$$n$$$ is odd,we can traverse all cells, which is a simple situation.

If $$$n$$$ is even,we can skip one of $$$(1,2) (1,4) (1,6)...(1,n),(2,1),(2,3),(2,5)...(2,n-1)$$$.If there is a duplicate number, skip it. Otherwise, skip the maximum number.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,k;
int  a[N],pre1[N],tot1[N];
char s[N];

void init()
{
	pre1[n+1]=tot1[n+1]=0;
	for(int i=n;i;i--)
	{
		if(a[i])
		{
			pre1[i]=pre1[i+1]+1;
			tot1[i]=tot1[i+1]+1;
		}
		else
		{
			pre1[i]=0;
			tot1[i]=tot1[i+1];
		}
	}
}

int check(int idx,int c1)
{
	return (pre1[idx]<c1)||(pre1[idx]==c1&&tot1[idx]==c1);
}

void solve1()
{
	int c0=(n+k)/2,c1=c0-k;
	for(int i=1;i<=n;i++)
	{
		if(a[i])
		{
			c1--;
			printf("1");	
		}
		else
		{
			if(c0&&check(i+1,c1))
			{
				c0--;
				printf("0");	
			}
			else
			{
				c1--;
				printf("1");
				for(int i=1;i<=c0;i++) printf("0");
				for(int i=1;i<=c1;i++) printf("1");
				break;
			}
		}
	}
	printf("\n");
}

void solve2()
{
	int c0=0,c1=0;
	if(k>0)
	{
		c0=k;
		c0++,c1++;	
		while(c0+c1<=n) c0++,c1++;	
	}
	else
	{
		c1=-k;
		while(c0+c1<=n) c0++,c1++;	
	}
	printf("1");
	c1--;
	for(int i=1;i<=c0;i++) printf("0");
	for(int i=1;i<=c1;i++) printf("1");
	printf("\n");
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d%s",&n,&k,s);
    	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
    	init();
    	if(n==1&&a[1]==0&&k==1)
    	{
	    	printf("0\n");
	    	continue;
	    }
    	if((n+k)&1) solve2();
    	else
		{
	    	int c0=(n+k)/2,c1=c0-k;
			if(c0<0||c1<0) solve2();
			else
			{
				if(check(1,c1)) solve1();
				else solve2();
			}
	    }
	}
	
	return 0;
}

First,be careful when $$$y=0$$$ and $$$k=1$$$ :)

Consider the answer with a length greater than $$$n$$$, which is always $$$10...01...1$$$.The construction is not hard.

What about the answer with length $$$n$$$?

Consider setting numbers from the highest bit to the lowest bit and current bit is $$$i$$$.If $$$y_i=1$$$,we must set $$$x_i=1$$$.Otherwise($$$y_i=0$$$),we either do set $$$x_i=0$$$ and go to the lower bit,or do set $$$x_i=1$$$, $$$x_{i+1}x_{i+2}...x_n=0...01...1$$$ and break.

For $$$y_i=0$$$,when can we do set $$$x_i=0$$$ and go to the lower bit?The condition is $$$re1>pre1_{i+1}$$$ or $$$re1==pre1_{i+1}$$$ and $$$pre1_{i+1}==tot1_{i+1}$$$.$$$re1$$$ is the current remaining number of $$$1's$$$,$$$pre1_{i+1}$$$ is the length of the continuous $$$1$$$ prefix of $$$y_{i+1}y_{i+2}...y_n$$$,and $$$tot1_{i+1}$$$ is the total of $$$1$$$ of $$$y_{i+1}y_{i+2}...y_n$$$.

include<bits/stdc++.h>

define ll long long int

using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { int n, x; cin >> n >> x; int fst = -1; int val = 0; for(int i = 29; i >= 0; i--) { int a = (x >> i)&1; if(!a) { fst = i; break; } val ^= (1 << i); } if(fst + 2 >= n) { cout << x; for(int i = 2; i <= n; i++) { val ^= (1 << (fst — i + 2)); cout << " " << val; } cout << "\n"; } else cout << "-1\n"; } }

Note $$$maxdif(x,y)=max(k)(bit(x,k)!=bit(y,k))$$$.

It can be proved that $$$maxdif(a[i],a[i+1])$$$ is strictly decreasing.

Based on the above conclusion, we can make the optimal construction.

Note $$$x=(1...10???)_2$$$,construct $$$a=[(1...10???)_2,(1...110...0)_2,(1...111...0)_2,...,(1...111...1)_2]$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
ll  T,n,m,c;
ll  a[N][N];
ll  dp[N][N];

void init()
{
	scanf("%I64d%I64d%I64d",&n,&m,&c);
	for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    		scanf("%I64d",&a[i][j]);
}

void DP()
{
	for(int i=1;i<=n;i++)
	{
		ll maxl[N]={0},maxr[N]={0},left[N]={0},right[N]={0};
		for(int j=1;j<=m;j++) maxl[j]=max(0LL,a[i][j]-2*c+maxl[j-1]);
		for(int j=m;j>=1;j--) maxr[j]=max(0LL,a[i][j]-2*c+maxr[j+1]);
		for(int j=1;j<=m;j++) left[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxl[j-1],left[j-1]+a[i][j]-c);
		for(int j=m;j>=1;j--) right[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxr[j+1],right[j+1]+a[i][j]-c);
		for(int j=1;j<=m;j++) dp[i][j]=max(left[j]+maxr[j+1],right[j]+maxl[j-1]);
	}
	ll ans=-INF;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=max(ans,dp[i][j]);
	printf("%I64d\n",ans);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	init();
    	DP();
	}
	
	return 0;
}

Consider DP.

Note $$$dp_{i,j}$$$ as the maximum score we can get at the end of $$$(i,j)$$$.

Note $$$lmax_{i,j}=max(0,max_(1 \leq k \leq j)((a_{i,k}-2c)+...+(a_{i,j}-2c)))$$$ and $$$rmax$$$ similarly.

Now consider which cell we go from to $$$(i,j)$$$.There are four situations.

$$$1.$$$ We just start at $$$(i,j)$$$.The answer is $$$a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$2.(i-1,j) \rightarrow (i,j)$$$.The answer is $$$dp_{i-1,j}-c+a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$3.(i,j-1) \rightarrow (i,j)$$$.The answer is $$$left_{i-1,j}-c+a_{i,j}+rmax_{i,j+1}$$$;

$$$4.(i,j+1) \rightarrow (i,j)$$$.The answer is $$$right_{i+1,j}-c+a_{i,j}+lmax_{i,j-1}$$$.

$$$left_{i,j}=max(max(0,dp_{i-1,j}-c)+a_{i,j}+lmax_{i,j-1},left_{i,j-1}-c+a_{i,j})$$$,and $$$right_{i,j}$$$ similarly.

$$$dp_{i,j}$$$ is the maximum value of the answers for the four situations mentioned above.And the final answer is $$$max(dp_{i,j})$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(n%6==1)
		{
			for(int i=1;i<n/6;i++) printf("0");
			printf("8\n");
			continue;
		}
		for(int i=1;i<=n/6;i++) printf("0");
		if(n%6==2) printf("1\n");
		else if(n%6==3) printf("7\n");
		else if(n%6==4) printf("4\n");
		else if(n%6==5) printf("2\n");
		else printf("\n");
	}
	
	return 0;
}

If $$$n=6k$$$,print $$$0...0$$$;

If $$$n=6k+1$$$,print $$$0...08$$$;

If $$$n=6k+2$$$,print $$$0...01$$$;

If $$$n=6k+3$$$,print $$$0...07$$$;

If $$$n=6k+4$$$,print $$$0...04$$$;

If $$$n=6k+5$$$,print $$$0...05$$$;

If $$$n=6k+6$$$,print $$$0...09$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,k;
int a[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=k;i++) a[i]=0;
		for(int i=1;i<=k;i++)
		{
			if(n<2) break;
			a[i]=1;
			n-=2; 
		} 
		for(int i=k;i;i--)
		{
			if(a[i])
			{
				if(n>=4) a[i]=9,n-=4;
				else if(n>=1) a[i]=7,n--;
				else break;
			}
		}
		for(int i=k;i;i--) if(a[i]) printf("%d",a[i]);
		printf("\n");
	}
	
	return 0;
}

First,maximize number of digits — fill each digit with $$$'1'$$$.

Then starting from the highest bit,consider maximizing the current digit — consider changing the current bit to $$$'9'$$$. If no enough matchsticks, consider $$$'7'$$$.

Luckily,you find $$$[1,2n,2,2n-1,...,n,n+1]$$$ works :)

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,x;

int check(vector<int> v)
{
	sort(v.begin(),v.end());
	for(int i=1;i<=n*2;i++) if(v[i]!=i) return 0;
	return 1;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&x);
		ll S=(ll)n*(2*n+1),a=2*n+1,b,flg=0;
		for(int i=x;i<=x;i++)
		{
			for(int j=1;j<=2*n;j++)
			{
				if((S-i-j)%(n-1)) continue;
				b=(S-i-j)/(n-1); 
				vector<int> v;
				v.push_back(0);
				v.push_back(i);
				for(int i=2;i<n*2;i++)
				{
					if(i&1) v.push_back(b-v.back());
					else    v.push_back(a-v.back());
				} 
				v.push_back(j);
				if(check(v))
				{
					for(int k=1;k<=n*2;k++) printf("%d%c",v[k],k==n*2?'\n':' ');
					flg=1;
					break;
				}
			} 
		} 
		if(!flg) printf("-1\n");
	}
	
	return 0;
}

Note $$$s_1=p_1+p_2=p_3+p_4=...=p_{2n-1}+p_{2n},s_2=p_2+p_3=p_4+p_5=...=p_{2n-2}+p_{2n-1}$$$.

We can easily get $$$s_1=2n+1$$$.

Consider fix $$$s_2$$$,we can get:$$$p_{2n}=n*s_1-p_1-(n-1)s_2$$$.Since $$$1\leq p_{2n} \leq 2n$$$, we found that there are no more than $$$3$$$ suitable $$$s_2$$$.

For each suitable $$$s_2$$$,we can calculate the whole array,and check if it’s a permutation in $$$O(n)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,m;
int t[N];
int a[N][N],b[N][N],c[N][N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&b[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				c[i][j]=(a[i][j]^b[i][j]);		
		t[0]=t[1]=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				t[(i+j)&1]^=c[i][j];
		if(n==3&&m==3&&(c[1][2]||c[2][1]||c[2][3]||c[3][2])) printf("NO\n");
		else if(n==3&&m==4&&(c[2][1]||c[2][4])) printf("NO\n");
		else if(n==4&&m==3&&(c[1][2]||c[4][2])) printf("NO\n");
		else printf("%s\n",(t[0]||t[1])?"NO":"YES");		
	}
	
	return 0;
}

Consider a $$$3*3$$$ matrix,we can do something like:

$$$000$$$

$$$000$$$

$$$000$$$

$$$->$$$

$$$100$$$

$$$010$$$

$$$101$$$

$$$->$$$

$$$101$$$

$$$000$$$

$$$000$$$

Consider we can only flip $$$a_{x,y},a_{x,y+2}$$$ and $$$a_{x,y},a_{x+2,y}$$$,what about the answer?

Note $$$x_0=a_{1,1}⊕a_{1,3}⊕...,x_1=a_{1,2}⊕a_{1,4}⊕...$$$,the answer is $$$YES$$$ if and only if the $$$x_0=x_1=0$$$.

Let's go back to the original problem.The only difference is there are some unaccessable elements.Just do special judgment.

If $$$n=3,m=3$$$,unaccessable elements are $$$a_{1,2},a_{2,1},a_{2,3},a_{3,2}$$$;

If $$$n=3,m=4$$$,unaccessable elements are $$$a_{2,1},a_{2,4}$$$;

If $$$n=4,m=3$$$,unaccessable elements are $$$a_{1,2},a_{4,2}$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,flg;
int a[N],fre[N];
vector<int> G[N],ch[N];

void DFS(int x,int pr)
{
    for(int i=0;i<G[x].size();i++)
    {
	    int y=G[x][i];
            if(y==pr) continue;
	    ch[x].push_back(y);
            DFS(y,x);
    }
    if(x==1) return ;
    if(ch[x].size()==0) fre[x]=0;
    else if(ch[x].size()==1)
    {
    	fre[x]=0;
    	if(a[ch[x][0]]&&fre[ch[x][0]]) a[x]^=1;
    	else if(a[ch[x][0]]&&(!fre[ch[x][0]])) flg=0;
    }
    else if(ch[x].size()==2)
    {
    	if(fre[ch[x][0]]||fre[ch[x][1]])
    	{
    		a[x]^=(a[ch[x][0]]^a[ch[x][1]]);
	    	if(fre[ch[x][0]]&&fre[ch[x][1]]) fre[x]=1;
	    	else
	    	{
	    		fre[x]=0;
	    		if(a[ch[x][0]]&&a[ch[x][1]]) a[x]^=1,a[pr]^=1;
	    		else if(a[ch[x][0]]&&(!fre[ch[x][0]])) a[x]^=1,a[pr]^=1;
	    		else if(a[ch[x][1]]&&(!fre[ch[x][1]])) a[x]^=1,a[pr]^=1;
	    	}
	    }
	    else
	    {
	    	fre[x]=0;
    		if(a[ch[x][0]]^a[ch[x][1]]) flg=0;
	    	else a[x]^=a[ch[x][0]],a[pr]^=a[ch[x][0]];
    	}
    }
    else
    {
    	int tagf=0,taga=0;
    	for(int i=0;i<ch[x].size();i++) tagf|=fre[ch[x][i]],taga^=a[ch[x][i]];
    	if((!tagf)&&taga) flg=0;
    	else fre[x]=1,a[x]^=taga;
    }
}

void check1()
{
	int taga=0;
	for(int i=0;i<ch[1].size();i++) if((!fre[ch[1][i]])&&a[ch[1][i]]) flg=0;
	for(int i=0;i<ch[1].size();i++) taga^=a[ch[1][i]];
	if(taga^a[1]) flg=0;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
	    scanf("%d",&n);
	    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	    for(int i=1;i<=n;i++) G[i].clear(),ch[i].clear(); 
	    for(int i=1;i<n;i++)
	    {
    		int u,v;
    		scanf("%d%d",&u,&v);
    		G[u].push_back(v);
    		G[v].push_back(u);
    	   }
    	   flg=1;
    	   DFS(1,0);
           check1();
	   printf("%s\n",flg?"YES":"NO");
	}
	
	return 0;
}

Define free nodes $$$x$$$ — $$$free[x]=1$$$ means we can freely flip $$$x,fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0;

Define $$$col[x]$$$ — the value when node $$$x$$$ does not affect $$$fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0.Later on, we can see that this value is unique.

We update the values of $$$free[x],col[x]$$$ from bottom to top.

Case $$$1$$$:$$$x$$$ has $$$0$$$ son nodes.It's easy to get $$$free[x]=0,col[x]=a[x]$$$.

Case $$$2$$$:$$$x$$$ has $$$1$$$ son nodes.

We get $$$free[x]=0$$$.

If $$$col[son[x][0]]=0$$$,we don't need to flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]$$$;

If $$$col[son[x][0]]=1$$$ and $$$free[son[x][0]]=0$$$,no solution.Otherwise we must flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]⊕1$$$;

Case $$$3$$$:$$$x$$$ has $$$>2$$$ son nodes.

Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$x$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[x][i]$$$,no solution.

If we can change all the descendant nodes(exclude itself) of $$$x$$$ to 0,$$$x$$$ is always a free node.

Let's calculate $$$col[x]$$$.If $$$tagc=1$$$,we must flip $$$x$$$ and a free node,so $$$col[x]=a[x]⊕1$$$.If $$$tagc=0$$$,$$$col[x]=a[x]⊕0$$$.

Case $$$4$$$:$$$x$$$ has $$$2$$$ son nodes.

If $$$son[x][1],son[x][2]$$$ are both not free nod:

• if $$$col[son[x][1]]⊕col[son[x][2]]=1$$$,no solution;

• if $$$col[son[x][1]]=col[son[x][2]]=0$$$,$$$free[x]=0,col[x]=a[x]$$$;

• if $$$col[son[x][1]]=col[son[x][2]]=1$$$,$$$free[x]=0,col[x]=a[x]⊕1$$$,and flip $$$a[fa[x]]$$$;

If $$$son[x][1],son[x][2]$$$ are both free node,$$$free[x]=1,col[x]=a[x]⊕col[son[x][1]]⊕col[son[x][2]]$$$.

Otherwise,do similar casework :)

Finally(I promise),let's check the answer,for all son nodes of node $$$1$$$:

Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$1$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[1][i]$$$,no solution.

Otherwise,we should check $$$a[1]⊕tagc$$$.The answer is $$$YES$$$ if and only if $$$a[1]⊕tagc=0$$$.

Obviously,the length of a continuous segment with a negative contribution is $$$1$$$.

We can write a $$$O(n^2)$$$ DP:

$$$dp[i]=max(dp[j]-a[j+1]+a[j+2]|...|a[i])$$$

Then we notice there're at most $$$O(log maxa)$$$ different values in $$$a[j]|...|a[i]$$$ $$$(j<i)$$$.It's a classic conclution.

For a fix $$$a[j]|...|a[i]$$$ $$$=t$$$,we get $$$dp[i]=max(dp[j]-a[j+1])+t$$$.Since the value range of $$$j$$$ is continuous,we can use a segment tree to maintain it.It's $$$O(n log^2 n)$$$.

In fact,use prefix maximum value is enough.Note $$$premax[i]=max(dp[1]-a[2],...,dp[i]-a[i+1])$$$,$$$dp[i]=premax[j]+t$$$.It's $$$O(n log n)$$$.

This has prepared us for solving F2(solution2).

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=110;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
int a[N],pre[N];
ll  dp[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=0;i<N;i++) dp[i]=pre[i]=0;
		for(int i=1;i<=n;i++)
		{
			int cur=0;
			scanf("%d",&a[i%N]);
			pre[i%N]=(pre[(i-1+N)%N]|a[i%N]);
			dp[i%N]=pre[i%N];
			for(int j=i;j>=max(3,i-60);j--) 
			{
				cur|=a[j%N];
				dp[i%N]=max(dp[i%N],dp[(j-2+N)%N]-a[(j-1+N)%N]+cur);
			}
		}
		printf("%I64d\n",dp[n%N]);
	}

	return 0;
}

You need to observation that the length of consecutive segments will not exceed $$$60$$$.

Then we can use a scrolling array for DP.

Note $$$maxp$$$ as the maximum index of the maximum value in $$$a$$$.

For $$$1 \leq k \leq maxp-1$$$,they do not meet the condition.

For $$$maxp+1 \leq k \leq n$$$,they all meet the condition.

You need to be careful of $$$k==maxp$$$,it meet the condition if and only if there is only one maximum value in $$$a$$$.

Note $$$a_1$$$ as the first $$$\lceil{n/2}\rceil$$$ numbers of $$$a$$$,and $$$a_2$$$ as the last $$$n-\lceil{n/2}\rceil$$$ numbers of $$$a$$$.

Through observation,we found that the following processes will be repeated cyclically:

• erase the leftmost number of $$$a_1$$$

• erase the leftmost number of $$$a_2$$$

• erase the rightmost number of $$$a_1$$$

• erase the rightmost number of $$$a_2$$$

In conclusion:

• If $$$|a_1|>|a_2|$$$(i.e. $$$n$$$ is odd),the answer is the number in the middle of $$$a_1$$$

• If $$$|a_1|=|a_2|$$$(i.e. $$$n$$$ is even),the answer is the number in the middle of $$$a_2$$$

We notice we can convert condition $$$3$$$ to $$$c0(a,l_1,r_1)-c1(a,l_1,r_1)=c1(b,l_2,r_2)-c0(b,l_2,r_2)$$$.

This provides us with convenience: we can independently calculate the left and right value ranges.

If two ranges intersect, the answer is $$$YES$$$,otherwise the answer is $$$NO$$$.

Let's calculate the left value ranges.Make all $$$a_i=0$$$ to $$$1$$$ and $$$a_i=1$$$ to $$$-1$$$,it is the value range of all subarrays of appropriate length.

In fact,we only need to find max subsegment sum and min subsegment sum.It's a classic problem.

You may have already guessed:if $$$x_1<y_1$$$,and you get $$$minsum,maxsum$$$,the range of values is continuous — $$$[minsum,maxsum]$$$.Why?

You also need to be careful of the edge cases that $$$x_i=y_i(1 \leq i \leq 2)$$$.

We notice we can calculate each bit independently.

In other words,note $$$f(a_i,j)$$$ as the $$$j^{th}$$$ bit under the binary representation of $$$a_i$$$,the answer is $$$\Sigma_{i=0}^{i=30} 2^{i}*(\Sigma f(a_l,i)⊕...⊕f(a_r,i))$$$.

Let's calculate the sum of the $$$0^{th}$$$ bit.

$$$a_{i,0}=0,1,0,1,...$$$

Note $$$pre_{i,0}=a_{1,0}⊕...⊕a_{i,0}$$$,then

$$$pre_{i,0}=0,1,1,0,0,1,1,0,...$$$

We noticed that the loop section of this sequence is $$$4$$$ and can calculate the total number of $$$'1'$$$(note it as $$$c_1$$$).The total number of subarrays with xor-value $$$1$$$ is $$$c_1*(n+1-c_1)$$$.

For the $$$1,2,...30^{th}$$$ bit,use the similar method to calculate it.

Consider an easier problem:for a fixed score $$$x_1*x_2*...*x_k$$$($$$x_i$$$ is one of the prefix minimum value and note the set of them as $$$X$$$),how to calculate the number of schemes?

Consider such a sequence construction process: put all $$$0$$$'s, all $$$1$$$'s, and all $$$2$$$'s,...

If you want the prefix minimum value of $$$i$$$ to appear in $$$a$$$, what should you do?We can get:at least one $$$i$$$ must be placed at the head of the current sequence.

This is actually equivalent to the classical problem: $$$m_i$$$ balls are put into $$$(m_1+...+m_{i-1}+1)$$$ boxes, the first box must have at least one ball,count the number of schemes.

The answer is:

$$$U_i=C(m_i-1+(m_1+...+m_{i-1}),(m_1+...+m_{i-1}))$$$.

If you want the prefix minimum value of i not to appear in $$$a$$$, what should you do?We can get:no $$$i$$$ must be placed at the head of the sequence.Solve it in a similar way as above.

The answer is:

$$$V_i=C(m_i+(m_1+...+m_{i-1})-1,(m_1+...+m_{i-1})-1)$$$.

Let's go back to the easier problem.The number of schemes is $$$\Pi_{i∈X}U_i * \Pi_{i∉X}V_i$$$.

Finally, how to calculate the total score?We can convert the formula into:$$$(1*U_1+V_1)(2*U_2+V_2)...(n*U_n+V_n)$$$.

There's another dp solution:$$$dp_i=(i-1)*U_{i-1}*dp_{i-1}+V_{i-1}*dp_{i-1}$$$.It's actually do the same thing.

Note $$$c_{i,j}=a_{i,j}⊕b_{i,j}$$$.The problem is equivalent to turning $$$c$$$ into a zero matrix.

Consider $$$l=2$$$.What about the solution?

We can easily get:the answer is $$$YES$$$ if and only if the xor-sum of all numbers is $$$0$$$.

Now let’s consider $$$l=3$$$.The method can be extended to $$$l=k$$$.

We notice we can do:

$$$0000->1110->1001$$$

If we can only filp $$${a_{x,y},a_{x,y+3}}$$$ and $$${a_{x,y},a_{x+3,y}}$$$,what about the answer?

We group the elements in the matrix $$$c$$$ like:

$$$1231231... $$$

$$$4564564... $$$

$$$7897897... $$$

$$$1231231... $$$

$$$... $$$

Note $$$XOR(i)$$$ as xor-sum of all numbers in group $$$i$$$.We can get:if all $$$XOR(i)$$$ are $$$0$$$,the answer is $$$YES$$$.

Now let’s consider the origin flip. In essence,there are only $$$6$$$ different operations:

• Flip $$$XOR(1),XOR(2),XOR(3)$$$;

• Flip $$$XOR(4),XOR(5),XOR(6)$$$;

• Flip $$$XOR(7),XOR(8),XOR(9)$$$;

• Flip $$$XOR(1),XOR(4),XOR(7)$$$;

• Flip $$$XOR(2),XOR(5),XOR(8)$$$;

• Flip $$$XOR(3),XOR(6),XOR(9)$$$.

Construct a $$$l*l$$$ matrix $$$d$$$,$$$d_{i,j}=XOR((i-1)*l+j)$$$.We find that we can turn it into a classical problem:

https://codeforces.me/problemset/problem/1475/F.

What about $$$x*y$$$ span?