首页 > 代码库 > BZOJ4553: [Tjoi2016&Heoi2016]序列 树套树优化DP
BZOJ4553: [Tjoi2016&Heoi2016]序列 树套树优化DP
把pos[i]上出现的平常值定义为nor[i]最大值定义为max[i]最小值定义为min[i]，那么我们发现在两个值,i（前）,j（后）,当且仅当max[i]<=nor[j],nor[i]<=min[j]时才会组成序列的前后两个值，并且当序列里所有连续的两个值都满足这个条件是时就可以，因此我们以f[i]表示以i为起点的序列最长值，那么我们就可以转移了f[i]=maxf[j](max[i]<=nor[j],nor[i]<=min[j],pos[i]<pos[j])+1,这就是一个三维逆序对，至于pos[i]我们用默认时间来维护（按倒序插入），用一颗值域线段树来维护nor[i]值域并在每个节点中建一颗替罪羊树表示在nor在此值域里的数，并用min值排序，并且在每个替罪羊节点上维护最大值标记（表示是子树里表示的点里f最大值）
用树套树解决三维偏序的一般思路：一维用时间维护，一维用线段树来维护，另一位用线段树里的平衡排序维护
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cstring> #define MAXN 100000 using namespace std; inline int read() { int sum=0; char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) { sum=(sum<<1)+(sum<<3)+ch-‘0‘; ch=getchar(); } return sum; } inline int MAX(int x,int y) { return x>y?x:y; } inline int MIN(int x,int y) { return x<y?x:y; } const double alpha=0.75; struct ScapeGoat_Tree { ScapeGoat_Tree *ch[2]; int key,size,f,Max; void pushup() { size=ch[0]->size+1+ch[1]->size; Max=ch[0]->Max>ch[1]->Max?ch[0]->Max:ch[1]->Max; Max=Max>f?Max:f; } bool isbad() { return alpha*size+5<ch[0]->size||alpha*size+5<ch[1]->size; } }*null,Node[MAXN<<5],*list[MAXN<<4]; int top,len; inline void ScapeGoat_Tree_Init() { null=Node; null->ch[1]=null->ch[0]=null; } inline ScapeGoat_Tree *NEW(int key,int F) { ScapeGoat_Tree *p=&Node[++top]; p->ch[0]=p->ch[1]=null; p->size=1; p->key=key; p->f=p->Max=F; return p; } void travel(ScapeGoat_Tree *p) { if(p==null)return; travel(p->ch[0]); list[++len]=p; travel(p->ch[1]); } ScapeGoat_Tree *divide(int l,int r) { if(l>r)return null; int mid=(l+r)>>1; list[mid]->ch[0]=divide(l,mid-1); list[mid]->ch[1]=divide(mid+1,r); list[mid]->pushup(); return list[mid]; } inline void rebuild(ScapeGoat_Tree *&p) { len=0; travel(p); p=divide(1,len); } ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,int key,int F) { if(p==null) { p=NEW(key,F); return &null; } ScapeGoat_Tree **ret=insert(p->ch[p->key<key],key,F); p->pushup(); if(p->isbad())ret=&p; return ret; } inline void Insert(ScapeGoat_Tree *&Root,int key,int F) { ScapeGoat_Tree **p=insert(Root,key,F); if(*p!=null)rebuild(*p); } inline int get_Rank(ScapeGoat_Tree *Root,int key) { ScapeGoat_Tree *p=Root; int ret=0; while(p!=null) if(p->key>=key) p=p->ch[0]; else ret+=p->ch[0]->size+1,p=p->ch[1]; return ret; } int get_Max(ScapeGoat_Tree *p,int l) { if(l>p->size)return 0; if(l<=1) return p->Max; int ans=0; if(l<=p->ch[0]->size)ans=get_Max(p->ch[0],l); if(l<=p->ch[0]->size+1)ans=MAX(ans,p->f); ans=MAX(ans,get_Max(p->ch[1],l-p->ch[0]->size-1)); return ans; } inline int query(ScapeGoat_Tree *Root,int key) { return get_Max(Root,get_Rank(Root,key)+1); } struct Seg_Tree { ScapeGoat_Tree *root; int l,r,mid; Seg_Tree *ch[2]; }node[MAXN<<2],*root; int sz; inline Seg_Tree *New(int l,int r) { Seg_Tree *p=&node[sz++]; p->l=l; p->r=r; p->mid=(l+r)>>1; p->root=null; return p; } void build(Seg_Tree *p) { if(p->l==p->r)return; p->ch[0]=New(p->l,p->mid); p->ch[1]=New(p->mid+1,p->r); build(p->ch[0]); build(p->ch[1]); } inline void Seg_Tree_Init() { root=New(1,MAXN); build(root); } void Ins(Seg_Tree *p,int pos,int key,int F) { Insert(p->root,key,F); if(p->l==p->r)return; Ins(p->ch[p->mid<pos],pos,key,F); } int Query(Seg_Tree *p,int l,int key) { if(l<=p->l) return query(p->root,key); int ans=0; if(l<=p->mid) ans=Query(p->ch[0],l,key); ans=MAX(ans,Query(p->ch[1],l,key)); return ans; } int n,m; int Max[MAXN+10],Min[MAXN+10],nor[MAXN+10],f[MAXN+10]; inline void Init() { ScapeGoat_Tree_Init(); Seg_Tree_Init(); n=read(),m=read(); for(int i=1;i<=n;i++)Max[i]=Min[i]=nor[i]=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(); Max[x]=MAX(y,Max[x]); Min[x]=MIN(y,Min[x]); } } inline void WORK() { f[n]=1; Ins(root,nor[n],Min[n],1); int ans=1; for(int i=n-1;i>0;i--) { f[i]=Query(root,Max[i],nor[i])+1; Ins(root,nor[i],Min[i],f[i]); ans=MAX(f[i],ans); } printf("%d",ans); } int main() { Init(); WORK(); }
BZOJ4553: [Tjoi2016&Heoi2016]序列 树套树优化DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。