坐等
by ST4LkRY @ 2019-11-07 20:24:27
坐等
by XyzL @ 2019-11-07 20:27:56
Orz，不会树状数组求法，不过你可以试试~~更为广大人民群众接受的~~单调队列！
by E17bits @ 2019-11-07 20:41:26
@[XyzL](/user/130812)
头像是鸣人吗
by Virtualtan @ 2019-11-07 21:45:16
女装是不可能的，这辈子不可能女装....
哎呀嘛，真香！
by Virtualtan @ 2019-11-07 21:45:59
@[UKEautomaton](/user/179833) 蛤，鸣仔他爸
by XyzL @ 2019-11-08 07:55:07
@[XyzL](/user/130812) 噢， 没点放大， 看不清....
by Virtualtan @ 2019-11-08 09:22:54
@[Virtualtan](/user/179833)
来自四年后的回复
是这样的，有两个问题，第一个是这个数据不合法，树不一定联通，所以最后用tot-ans会错，改成n-tot就对了，还有数据需要离散化，只是单纯的-最小值会导致很大的值出现，导致RE
以下是你的代码改的AC代码
可以把女装照片发给我吗（）
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 100000+9;
#define lowbit(x) (x&-x)
int n;
int a[N], b[N], tot=0, c[N];
int ls[N];
int lch[N], rch[N];
int mn = 2147483647, mx = -1;
void dfs(int x) {
// if(!x) return ;
if(lch[x])dfs(lch[x]);
b[++tot] = x;
if(rch[x])dfs(rch[x]);
}
int ft[N], ans;
void add(int x, int k) {while(x < N) {ft[x] = max(ft[x], k); x += lowbit(x);} }
int query(int x) {//最长不下降
int mxx = -1;
while(x) {
mxx = max(ft[x], mxx);
x -= lowbit(x);
}
return mxx;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int fa, ch;
for(int i = 2; i <= n; i++) {
scanf("%d%d",&fa, &ch);
if(ch == 0) lch[fa] = i;
else rch[fa] = i;
}
dfs(1);
// if(tot!=n)cout<<"Y\n";
for(int i = 1; i <= tot; i++) c[i] = a[b[i]], c[i] -= i,ls[i]=c[i];
sort(ls+1,ls+tot+1);
int sz=unique(ls+1,ls+tot+1)-ls-1;
for(int i=1;i<=tot;i++)c[i]=lower_bound(ls+1,ls+sz+1,c[i])-ls;
ans = -1;
// if(tot==n)cout<<"Y";
for(int i = 1; i <= tot; i++) {
ft[c[i]] = query(c[i]) + 1;
ans = max(ft[c[i]], ans);
add(c[i], ft[c[i]]);
}
// if(n==tot){
// cout<<'Y';
// }else cout<<tot;
printf("%d", n - ans);
}
```
by yywlp @ 2023-11-11 08:29:16