题解 P3365 【改造二叉树】

``` 20191013修改：个人博客网址变更 ``` 同样欢迎来到[我的个人博客查看](https://officerbonin.home.blog/2019/08/19/%e3%80%90%e4%bf%a1%e7%ab%9e%e3%80%91luogup3365-%e6%94%b9%e9%80%a0%e4%ba%8c%e5%8f%89%e6%a0%91/) 本题被教练选作了模拟赛的第一题，~~结果我去死磕树形DP,噗....~~ 考后[一位大佬](https://www.luogu.org/space/show?uid=88268)给我讲了本题的解法。 思想等同于本题[张亦弛给出的题解](https://www.luogu.org/blog/1557114139--com/solution-p3365)。 我发这篇题解，因为我使用的线段树优化的方式，但瞧见其他题解都是二分优化的，没有题解用这个方式。 修改后交题解没过，那就加点解释吧，见代码. ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<climits> #include<cmath> #include<algorithm> #include<map> #include<vector> #define maxn 100005 using namespace std; int n; struct node { int lc,rc,fa; } pot[maxn]; int a[maxn],b[maxn]; map<int,int>yst; int qa[maxn],f[maxn]; struct segmenttree { int l,r; int data; } tr[100005*4]; void zsbl(int now)//中序遍历 { // cout<<now<<endl; if(pot[now].lc) { zsbl(pot[now].lc); } // cout<<now; qa[++qa[0]]=a[now]; if(pot[now].rc) { zsbl(pot[now].rc); } return; } void build(int l,int r,int k) { tr[k].l=l; tr[k].r=r; if(l==r) { tr[k].data=0; return; } int mid=(l+r)/2; build(l,mid,k*2); build(mid+1,r,k*2+1); } int ask(int l,int r,int k) { if(!r)return 0; if(l<=tr[k].l&&tr[k].r<=r)return tr[k].data; if(r<tr[k].l||tr[k].r<l)return 0; return max(ask(l,r,k*2),ask(l,r,k*2+1)); } void update(int x,int k,int id) { if(tr[k].l==tr[k].r) { tr[k].data=max(tr[k].data,id); return; } int mid=(tr[k].l+tr[k].r)/2; if(x<=mid)update(x,k*2,id); else update(x,k*2+1,id); tr[k].data=max(tr[k*2].data,tr[k*2+1].data); } int main() { int n; cin>>n; for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); } int x,y; for(int i = 2; i <= n; i++) { scanf("%d%d",&x,&y); pot[i].fa=x; if(!y) pot[x].lc=i; else pot[x].rc=i; } zsbl(1);//中序遍历 for(int i = 1; i <= n; i++) { qa[i]-=i; b[i]=qa[i]; } sort(b+1,b+n+1); int cntb=unique(b+1,b+n+1)-b-1; for(int i = 1; i <= cntb; i++) yst[b[i]]=i; for(int i = 1; i <= n; i++) qa[i]=yst[qa[i]]; //上头都在读入和离散化 int maxx=0; build(1,n,1); /* 数组qa是二叉搜索树中序遍历展开并离散化后得到的序列，下简称q. f的含义稍有不同，f[i]为以第q[i]个数结尾，前头都塞小于等于q[i]的数（保证序列单调递增）时最多能保留多少个数（就是能有多少个数不变。 所以,f[i]的最佳值当然是1~q[i]中最大的+1.实现查找区间内最大的并进行单点修改，当然线段树十分好用 */ for(int it = 1; it <= n; it++) { f[it]=ask(1,qa[it],1)+1; update(qa[it],1,f[it]); maxx=max(maxx,f[it]); } cout<<n-maxx; } ```