首页 技术 正文
技术 2022年11月23日
0 收藏 862 点赞 3,987 浏览 1891 个字

【BZOJ4553】[Tjoi2016&Heoi2016]序列

Description

佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。注意:每种变化最多只有一个值发生变化。在样例输入1中,所有的变化是:

1 2 32 2 31 3 31 1 31 2 4选择子序列为原序列,即在任意一种变化中均为不降子序列在样例输入2中,所有的变化是:3 3 33 2 3选择子序列为第一个元素和第三个元素,或者第二个元素和第三个元素,均可满足要求

Input

输入的第一行有两个正整数n, m,分别表示序列的长度和变化的个数。接下来一行有n个数,表示这个数列原始的状态。接下来m行,每行有2个数x, y,表示数列的第x项可以变化成y这个值。1 <= x <= n。所有数字均为正整数,且小于等于100,000

Output

输出一个整数,表示对应的答案

Sample Input

3 4
1 2 3
1 2
2 3
2 1
3 4

Sample Output

3

题解:我们设每个数可能的最大值为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++;
elsep[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;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141856.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,508
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,314
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站