Competition Links
A. Playing with water (water)
Check-in. It was found that if two paths are to be found, a sufficient condition for being able to find them is the existence of a point with the same letter above and to the left of it. (This is met even for two paths that go through very different points, when the end point will be that point.)
That is, there exists a location\((i,j)\) feasible\(s_{i-1,j}=s_{i,j-1}\)We call the position\((i,j)\) begood location。
Expanding to a three-way discovery, the presence of the two good locations above is fine, but there are requirements for these two locations:
- Two points are adjacent to each other, i.e., the following scenario:
or Neighbors in the same column
- Two good spots.\((i_1,j_1),(i_2,j_2)\) fulfillment\(i_2>i_1,j_2>j_1\)
B. AVL tree
greed, the idea is really simple, just not well implemented.
It was found that it was preferable to leave as small a node as possible, so the middle-order traversal was performed, and for each node, the minimum number of points that would have to be left if it was left was found (let's say this number is\(x\)), comparing\(x\) together with\(k\)if\(x<k\) Then the point can stay, marked on.
Consider exactly howQuery the number of points to leave at least one point left behind。
-
For inquiries:
It is found that if the height of an AVL tree is deterministic, the minimum number of nodes it contains can be found:
It can be preprocessed.\(f[i]\)expressedAVL tree of depth i with at least how many nodes. There are recursive\(f[i]=f[i−1]+f[i−2]+1\), which can be viewed as having a depth of i-1 on one side and i-2 on the other, with the root node attached to it.
Then the query seeks out a point to stay, all the way back to its ancestor nodes until the root, for the case that the node is a left son to calculate to retain this node at least how many nodes are needed in the right subtree, can be converted to find the minimum height of the right subtree.
We maintain each point of(of a speech etc) profundity\(dep\), maximum depth within subtree\(dmax\)The dfs pre-processes both of these messages.
Also maintain each point as the root of theMaximum depth of selected points in the subtree\(had\), and the minimum depth required if the point is to remain\(ned\)。
So that the number of points needed to ask is good, in the process of asking the point to keep jumping father back, when the point jumped to is the left son, find the minimum height of the right son of the node that retains this point, its parent node.
Look at the code specifically, so now we also need to update this information in real time.
-
Consider updating:
-
Each point is selected to keep backtracking from the ancestor node to the root node toUpdate the maximum depth of the selected subtree of all its ancestor nodes；
-
And the process of backtrackingMaximum depth required to update the right son of the parent node to stay when the point is a left son, (to ensure that the AVL tree requirement is met, i.e., that the difference in height between the two sons' subtrees does not exceed 1)
And when the point is a right son it doesn't care about the left son of the parent node, because the left son must have been prioritized by us as to whether it can be left or not, and the right son is traversed to after the left son and doesn't have an effect on the left son.
-
Due to the nature of AVL trees, the height is approximately\(\log n\), so the overall complexity is\(O(n\log n)\)。
Specifically there are also very detailed code comments:
code
#include<bits/stdc++.h>
#define mp make_pair
#define Type int
#define qr(x) x=read()
typedef __int128 INT.
typedef long long ll; #define mp make_pair #define Type int #define qr(x)
using namespace std.
inline Type read(){
char c=getchar(); Type x=0, f=1.
while(!isdigit(c)) (c=='-'?f=-1:f=1), c=getchar(); while(isdigit(c)) x=(isdigit(c))
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48), c=getchar();
return x*f.
}
const int N = 5e5 + 5;
int n, k, root, whi[N]; int son[N][2], fa[N], f[N]; const
int son[N][2], fa[N], f[N];
int dep[N], dmax[N];
inline void dfs(int x, int p){ dfs preprocessing
dmax[x] = dep[x] = dep[p] + 1;
for(int i=0; i<2; i++){
int y = son[x][i].
if(!y) continue;
dfs(y, x);
dmax[x] = max(dmax[x], dmax[y]);
}
}
int ned[N], had[N], vis[N];
inline int query(int u){
int y = u, x = fa[u], res = 0; while(x !
while(x ! = -1){
if(!whi[y]) res += f[max({had[x]-1, dep[u]-1, ned[son[x][1]]})-dep[x]]; // jump to the point when the point is the left son, plus the contribution of the right son
y = x, x = fa[x];
}
return res.
}
inline void update(int u){ //pick a point and update its influence on the ancestor nodes
had[u] = max(had[u], dep[u]);
int y = u, x = fa[u].
while(x ! = -1){
had[x] = max(had[x], dep[u]);//update the maximum depth of the selected points within the subtree
if(!whi[y] and son[x][1]) ned[son[x][1]] = max(ned[son[x][1]], had[x] - 1); //The point is the left son, update the maximum depth needed if the right son is selected
y = x, x = fa[x];
}
}
inline void DFS(int x){
if(query(x) < k){
vis[x] = true.
k--; update(x);
}
if(son[x][0] and dmax[son[x][0]] >= ned[x]){ //select the left subtree up to the maximum depth needed to get the parent node
ned[son[x][0]] = max(ned[son[x][0]], ned[x]);
if(son[x][1]) ned[son[x][1]] = max(ned[son[x][1]], ned[x] - 1);
}
else if(son[x][1]){ //otherwise select the right subtree
ned[son[x][1]] = max(ned[son[x][1]], ned[x]);
if(son[x][0]) ned[son[x][0]] = max(ned[son[x][0]], ned[x] - 1);
}
for(int i=0; i<2; i++){
int y = son[x][i];
if(!y) continue;
DFS(y);
}
}
signed main(){ //avl
freopen("", "r", stdin), freopen("", "w", stdout); }
qr(n), qr(k);
for(int i=1; i<=n; i++){
qr(fa[i]);
if(fa[i] == -1){root = i;continue;}
whi[i] = (i < fa[i] ? 0 : 1); // determine whether the point is a left or right child of its parent node
son[fa[i]][whi[i]] = i;
}
if(k == 1){
for(int i=1; i<=n; i++)
cout<<(i == root ? 1 : 0);
cout<<(i == root ? 1 : 0); return 0;
}
dfs(root, 0);
f[1] = 1;
for(int i=2; i<=30; i++) f[i] = f[i-1] + f[i-2] + 1; // recursively find the minimum number of nodes in the AVL tree with depth i
DFS(root).
for(int i=1; i<=n; i++)
cout<<vis[i].
cout<<'\n'.
return 0;
}