TJOI2016 序列
题目大意:
有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。
能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?求这个子序列的最长长度。
注意:每种变化最多只有一个值发生变化。
题解:
首先,因为是对任意的变化都满足子序列不降,因而每一个位置上的数字我们只用存它原来的大小,变化后的最大值,以及变化后的最小值。(如果最大、最小都可以满足,其他的值也一定可以满足)
于是,我们发现,题目变成了比较明显的dp。
定义$dp_i$ 表示以i为结尾的最长的合法子序列有多长。
那么转移方程就是$dp_i = max \{ dp_j \} +1 $
看起来与LIS十分相似,不过转移条件变得更加苛刻了:
$num_j \le mi_i $ 并且 $ mx_j \le num_i $ .
不难发现,除去下标这一维,我们还剩下两个维度需要维护。
比较显然的想法是利用树套树来维护这两个维度。
由于本题维护的是前缀最大值,因而可以用二维BIT来实现。
但不能用一般的二维BIT,那样子空间开不下。
我们发现,总共的状态数为n个,我们开$n^2$显然是冗余了。
因为每一个状态的位置已经固定,我们可以在一维BIT基础上,开一个动态数组来维护第二维。
那么每一次修改或查询前,先二分一下对应位置即可。(相当于把它离散了)
总的时间复杂度为$O(nlog^2n)$ 。
具体实现可以看代码。
Code(二维BIT):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include<vector> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; inline void Rd(int&res){ res=0;char c; while(c=getchar(),c<48); do res=res*10+(c&15); while(c=getchar(),c>47); } const int N=100002; int n,m,num[N],mx[N],mi[N],dp[N]; inline void Min(int&a,int b){ if(a>b)a=b; } inline void Max(int&a,int b){ if(a<b)a=b; } #define lowbit(x) (x&(-x)) struct Binary_Indexed_Tree{ int sz; vector<int>data,bit; void insert(int x){ data.push_back(x); } void prepare(){ sort(data.begin(),data.end()); data.erase(unique(data.begin(),data.end()),data.end()); sz=data.size(); bit.resize(sz+1,0); } void add(int x,int v){ x=upper_bound(data.begin(),data.end(),x)-data.begin(); if(!x)return; for(;x<=sz;x+=lowbit(x)) Max(bit[x],v); } int sum(int x){ x=upper_bound(data.begin(),data.end(),x)-data.begin(); if(!x)return 0; int res=0; for(;x>0;x-=lowbit(x)) Max(res,bit[x]); return res; } }; struct Fenwick_Tree{ Binary_Indexed_Tree bit[N]; void insert(int x,int y){ for(;x<N;x+=lowbit(x)) bit[x].insert(y); } void prepare(){ for(int i=1;i<N;i++) bit[i].prepare(); } void add(int x,int y,int v){ for(;x<N;x+=lowbit(x)) bit[x].add(y,v); } int sum(int x,int y){ int res=0; for(;x>0;x-=lowbit(x)) Max(res,bit[x].sum(y)); return res; } }T; int main(){ Rd(n),Rd(m); for(int i=1;i<=n;i++){ Rd(num[i]); mi[i]=mx[i]=num[i]; } for(int i=1,a,b;i<=m;i++){ Rd(a),Rd(b); Min(mi[a],b); Max(mx[a],b); } for(int i=1;i<=n;i++) T.insert(num[i],mx[i]); T.prepare(); for(int i=1;i<=n;i++){ dp[i]=T.sum(mi[i],num[i])+1; T.add(num[i],mx[i],dp[i]); } int ans=0; for(int i=1;i<=n;i++) Max(ans,dp[i]); printf("%d\n",ans); return 0; }
|
另外还有一种实际跑起来更加优秀的算法:
这是一种分治的算法。
对于当前想要求解的区间$[L,R]$ 的dp值,我们先递归求解$[L,mid]$ 的dp值,再用$[L,mid]$ 区间的dp值去更新$[mid+1,R]$ 区间的dp值。最后递归求解$[mid+1,R]$ 的dp值。
(考虑一下树的中序遍历)
这样可以保证下标的一维已经满足。(保证了所有下标比我小的点都有机会更新我)
那么,重点来看更新操作。
我们用左半边区间,去更新右半边。
由于已经保证所有下标比我小的点都有机会更新我,我们可以在此离线操作。
可以把左半边的值都看作是update,而把右半边的值都看作query。
我们把update和query放到一起,以第一维为关键词排序,这样可以保证一维一定满足。
(若相同,update要放到query前面,因为此update也可更新到后面的query)
那么,最后就只剩下一维了,我们用一个BIT来维护前缀最大值即可。
总的时间复杂度为$O(nlog^2n)$ 。
但实际效果比二维BIT要优秀许多。
Code(分治):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
| #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; inline void Rd(int&res){ res=0;char c; while(c=getchar(),c<48); do res=res*10+(c&15); while(c=getchar(),c>47); } inline void Min(int&a,int b){ if(a>b)a=b; } inline void Max(int&a,int b){ if(a<b)a=b; } const int N=100005; int n,m,num[N],mi[N],mx[N],dp[N]; struct Bit{ #define lowbit(x) (x&(-x)) int bit[N]; void add(int x,int v){ for(;x<N;x+=lowbit(x))Max(bit[x],v); } void del(int x){ for(;x<N;x+=lowbit(x))bit[x]=0; } int sum(int x){ int res=0; for(;x>0;x-=lowbit(x))Max(res,bit[x]); return res; } }T; struct Action{ int op,id,num1,num2; bool operator <(const Action&tmp)const{ if(num1!=tmp.num1)return num1<tmp.num1; return op<tmp.op; } }act[N]; void update(int L,int R){ int tot=0,mid=L+R>>1; for(int i=L;i<=mid;i++)act[++tot]=(Action){0,i,mx[i],num[i]}; for(int i=mid+1;i<=R;i++)act[++tot]=(Action){1,i,num[i],mi[i]}; sort(act+1,act+1+tot); for(int i=1;i<=tot;i++){ if(act[i].op==0)T.add(act[i].num2,dp[act[i].id]); else Max(dp[act[i].id],T.sum(act[i].num2)+1); } for(int i=1;i<=tot;i++) if(act[i].op==0)T.del(act[i].num2); } void solve(int L,int R){ if(L==R){ Max(dp[L],1); return; } int mid=L+R>>1; solve(L,mid); update(L,R); solve(mid+1,R); } int main(){ Rd(n),Rd(m); for(int i=1;i<=n;i++){ Rd(num[i]); mi[i]=mx[i]=num[i]; } for(int i=1,a,b;i<=m;i++){ Rd(a),Rd(b); Min(mi[a],b); Max(mx[a],b); } solve(1,n); int ans=0; for(int i=1;i<=n;i++) Max(ans,dp[i]); printf("%d\n",ans); return 0; }
|