【BZOJ4553】[Tjoi2016&Heoi2016]序列 cdq分治+树状数组
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【BZOJ4553】[Tjoi2016&Heoi2016]序列 cdq分治+树状数组,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2324字,纯文字阅读大概需要4分钟。
内容图文
![【BZOJ4553】[Tjoi2016&Heoi2016]序列 cdq分治+树状数组](/upload/InfoBanner/zyjiaocheng/1097/8f737e72bf8c42efab721974c68e9bed.jpg)
【BZOJ4553】[Tjoi2016&Heoi2016]序列
Description
佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。注意:每种变化最多只有一个值发生变化。在样例输入1中,所有的变化是:
Input
输入的第一行有两个正整数n, m,分别表示序列的长度和变化的个数。接下来一行有n个数,表示这个数列原始的状态。接下来m行,每行有2个数x, y,表示数列的第x项可以变化成y这个值。1 <= x <= n。所有数字均为正整数,且小于等于100,000
Output
输出一个整数,表示对应的答案
Sample Input
1 2 3
1 2
2 3
2 1
3 4
Sample Output
题解:我们设每个数可能的最大值为R,最小值为L,初始值为V,那么我们选出的序列的相邻两项一定满足:Ra<=Vb且Va<=Lb。显然是个类似三维偏序的东西,cdq分治+树状数组维护即可。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,m,N,now,ans; const int maxn=100010; int s[maxn],tim[maxn]; struct node { int l,r,v,org,f; }p[maxn]; bool cmpr(const node &a,const node &b) { return a.r<b.r; } bool cmpv(const node &a,const node &b) { return a.v<b.v; } bool cmpo(const node &a,const node &b) { return a.org<b.org; } inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘) f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+(gc^‘0‘),gc=getchar(); return ret*f; } inline void updata(int x,int val) { for(int i=x;i<=N;i+=i&-i) { if(tim[i]<now) tim[i]=now,s[i]=0; s[i]=max(s[i],val); } } inline int query(int x) { int i,ret=0; for(i=x;i;i-=i&-i) { if(tim[i]<now) tim[i]=now,s[i]=0; ret=max(ret,s[i]); } return ret; } void solve(int l,int r) { if(l==r) return ; int mid=(l+r)>>1,i,h1=l,h2=mid+1; sort(p+l,p+r+1,cmpo); solve(l,mid); sort(p+l,p+mid+1,cmpr),sort(p+mid+1,p+r+1,cmpv); now++; for(i=l;i<=r;i++) { if(h1<=mid&&(h2>r||p[h1].r<=p[h2].v)) updata(p[h1].v,p[h1].f),h1++; else p[h2].f=max(p[h2].f,query(p[h2].l)+1),h2++; } solve(mid+1,r); } int main() { n=rd(),m=rd(); int i,a,b; for(i=1;i<=n;i++) p[i].v=p[i].l=p[i].r=rd(),N=max(N,p[i].v),p[i].org=i,p[i].f=1; for(i=1;i<=m;i++) a=rd(),b=rd(),p[a].l=min(p[a].l,b),p[a].r=max(p[a].r,b),N=max(N,b); solve(1,n); for(i=1;i<=n;i++) ans=max(ans,p[i].f); printf("%d",ans); return 0; }
原文:http://www.cnblogs.com/CQzhangyu/p/7859558.html
内容总结
以上是互联网集市为您收集整理的【BZOJ4553】[Tjoi2016&Heoi2016]序列 cdq分治+树状数组全部内容,希望文章能够帮你解决【BZOJ4553】[Tjoi2016&Heoi2016]序列 cdq分治+树状数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。