Codeforces Round 987 (Div. 2)

ABC 略

D

预处理出每个位置的前缀最大和后缀最小。从后向前枚举，如果一个数无法后移，那么答案就是最大前缀，否则答案要不是前缀最大，要不就是这个数先移到前缀最大位置再移到能移到的最大的位置此处的答案。用线段树维护

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=5e5+10;
int T,n,a[N],pre[N],suf[N],ans[N];
struct tree{int l,r,maxx;
}t[N*4];
void init()
{
}
void build(int p,int l,int r)
{t[p].l=l,t[p].r=r;t[p].maxx=0;if(l==r) return ;int mid=(l+r)/2;build(p*2,l,mid);build(p*2+1,mid+1,r);
}
void add(int p,int x,int k)
{if(t[p].l==t[p].r) {t[p].maxx=max(t[p].maxx,k); return ;}int mid=(t[p].l+t[p].r)/2;if(x<=mid) add(p*2,x,k);if(x>mid) add(p*2+1,x,k);t[p].maxx=max(t[p*2].maxx,t[p*2+1].maxx);
}
int ask(int p,int l,int r)
{if(t[p].l>=l&&t[p].r<=r) return t[p].maxx;int mid=(t[p].l+t[p].r)/2;int val=0;if(l<=mid) val=ask(p*2,l,r);if(r>mid) val=max(val,ask(p*2+1,l,r));return val;
}
void solve()
{cin>>n;init();for(int i=1;i<=n;i++)cin>>a[i];build(1,1,n);for(int i=1;i<=n;i++)pre[i]=max(pre[i-1],a[i]);suf[n]=a[n];for(int i=n-1;i>=1;i--)suf[i]=min(suf[i+1],a[i]);ans[n]=pre[n];add(1,a[n],n);for(int i=n-1;i>=1;i--){if(pre[i]<suf[i+1]){add(1,a[i],i);ans[i]=pre[i];continue;}ans[i]=max(ans[ask(1,1,pre[i]-1)],pre[i]);add(1,a[i],i);}for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie();cin>>T;while(T--) solve();
}

E

设f[x]表示x的子树的最小层数。首先明确删点操作只能增加一个层中点的个数，不能增加层数。一个点如果他的孩子数量<=2，那么f[x]就是它的儿子中最大f+1。当它的孩子>2时，在原二叉树中，父亲和所有儿子不再是全父子关系，存在儿子在原图中是父亲孙子的情况。下面我们将执行一个还原操作，将这个节点的子树还原为二叉树，此时它的孩子全部还原完成且知道还原完的层数。我们每次还原删去的父亲节点的f值就是它的两个孩子的f值中大的那个+1。相当于我们每次取两个孩子合成一个新的孩子，这个孩子的值为之前两个孩子的最大值+1，然后循环操作，直到就剩两个孩子为止，此时这两个孩子合成的就是原父亲节点。贪心每次选最小的两个合成即可，用优先队列维护。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=1e6+10;
int T,n,f[N];
vector<int> e[N];
void init()
{for(int i=1;i<=n;i++)e[i].clear();
}
void dfs(int x)
{priority_queue<int> q;for(int y : e[x]){dfs(y);q.emplace(-f[y]);}if(q.empty()) {f[x]=1; return ;}if(q.size()==1) {f[x]=-q.top()+1; return ;}while(q.size()>2){q.pop();int u=-q.top();q.pop();q.emplace(-(u+1));}q.pop();int u=-q.top();q.pop();f[x]=u+1;
}
void solve()
{cin>>n;init();for(int i=2;i<=n;i++){int x;cin>>x;e[x].emplace_back(i);}dfs(1);cout<<f[1]-1<<endl;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie();cin>>T;while(T--) solve();
}