#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;
}
#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:
Single Point modification;
Range minimum value query;
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.
Since the BST here is not guaranteed to be balanced, a bruteforce approach would lead to TLE. However, we can construct this BST using the classic Segment Tree + recursion.
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)$$$.
