#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:
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)$$$.
