UESTC 360(1425) another LCIS

2024-06-05 11:18
文章标签 360 another uestc 1425 lcis

本文主要是介绍UESTC 360(1425) another LCIS,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题是CD老OJ上面的一道题,现在在新OJ上的题号是360,开始在VJ上做的提交一直RE(囧)。后来才知道OJ移位了。

这道题是一个简单的成段更新+区间合并的线段树的题,1A还让我小激动了一下

这道题的大概意思是有两种操作,一种是成段地增加一个值,另外一种是询问从l到r这段区间内的最长递增子序列

首先先分析一下,如果某一段的值成段地增加一个量,那么该区间内的数的相对大小是不变的,因此递增子序列的长度是不会改变的

是要分析对于结果有影响的信息与值:一是每个子区间中的最值,二是有可能在两个区间合并之后的两个区间的中间的两段成为新的最值,因此我们需要判断中间的两个值是否可以合并,从何得知:我们需要在运算过程中分别记录下左端点的值和右端点的值,来判断是否可以合并。因此在每个节点增设两个值lv,rv。

还有一个问题就是在查询过程中,可能会存在查询的范围R-mid比lsum[rt<<1|1]小(mid-L+1比rsum[rt<<1]小),因此用比较取较小值相加就OK;额

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int SIZEN=100005;
 6 int sum[SIZEN<<2],lsum[SIZEN<<2],rsum[SIZEN<<2];
 7 int lv[SIZEN<<2],rv[SIZEN<<2],add[SIZEN<<2];
 8 int a[SIZEN];
 9 void pushup(int len,int rt){
10     int tmp;
11     lsum[rt]=lsum[rt<<1];
12     rsum[rt]=rsum[rt<<1|1];
13     lv[rt]=lv[rt<<1];rv[rt]=rv[rt<<1|1];
14     if(lsum[rt]==(len-(len>>1))&&rv[rt<<1]<lv[rt<<1|1]) lsum[rt]+=lsum[rt<<1|1];
15     if(rsum[rt]==(len>>1)&&rv[rt<<1]<lv[rt<<1|1]) rsum[rt]+=rsum[rt<<1];
16     tmp=rsum[rt<<1]+lsum[rt<<1|1];
17     if(rv[rt<<1]<lv[rt<<1|1])
18         sum[rt]=max(tmp,max(sum[rt<<1],sum[rt<<1|1]));
19     else sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
20 }
21 void pushdown(int rt){
22     if(add[rt]!=0){
23         add[rt<<1]+=add[rt];
24         add[rt<<1|1]+=add[rt];
25         lv[rt<<1]+=add[rt];rv[rt<<1]+=add[rt];
26         lv[rt<<1|1]+=add[rt];rv[rt<<1|1]+=add[rt];
27         add[rt]=0;
28     }
29 }
30 void update(int L,int R,int o,int l,int r,int rt){
31     if(L<=l&&r<=R){
32         add[rt]+=o;
33         lv[rt]+=o;rv[rt]+=o;
34         return;
35     }
36     pushdown(rt);
37     int mid=(l+r)>>1;
38     if(L<=mid) update(L,R,o,l,mid,rt<<1);
39     if(mid+1<=R) update(L,R,o,mid+1,r,rt<<1|1);
40     pushup(r-l+1,rt);
41 }
42 void build(int l,int r,int rt){
43     add[rt]=0;
44     if(l==r){
45         sum[rt]=lsum[rt]=rsum[rt]=1;
46         lv[rt]=rv[rt]=a[l];
47         return;
48     }
49     int mid=(l+r)>>1;
50     build(l,mid,rt<<1);
51     build(mid+1,r,rt<<1|1);
52     pushup(r-l+1,rt);
53 }
54 int query(int L,int R,int l,int r,int rt){
55     if(L<=l&&r<=R){
56         return sum[rt];
57     }
58     int mid=(l+r)>>1,r1,r2,r3;
59     int len=r-l+1;
60     r1=r2=r3=-1;
61     pushdown(rt);
62     if(L<=mid) r1=query(L,R,l,mid,rt<<1);
63     if(mid+1<=R) r2=query(L,R,mid+1,r,rt<<1|1);
64     if(rv[rt<<1]<lv[rt<<1|1]) r3=min(rsum[rt<<1],mid-L+1)+min(lsum[rt<<1|1],R-mid);
65     return max(r1,max(r2,r3));
66 }
67 int main()
68 {
69     //freopen("data.in","r",stdin);
70     int i,j,_;
71     char c;
72     int l,r,o;
73     int n,q,txt=1;
74     scanf("%d",&_);
75     while(_--){
76         printf("Case #%d:\n",txt++);
77         scanf("%d%d",&n,&q);
78         for(i=1;i<=n;i++)
79             scanf("%d",&a[i]);
80         build(1,n,1);
81         while(q--){
82             scanf(" %c",&c);
83             if(c=='a'){
84                 scanf("%d%d%d",&l,&r,&o);
85                 update(l,r,o,1,n,1);
86             }
87             else{
88                 scanf("%d%d",&l,&r);
89                 int ret=query(l,r,1,n,1);
90                 printf("%d\n",ret);
91             }
92         }
93     }
94     return 0;
95 }

 

这篇关于UESTC 360(1425) another LCIS的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032904

相关文章

企业级大数据平台建设参考 | 淘宝滴滴美团360快手京东

点击上方蓝色字体,选择“设为星标” 回复”资源“获取更多资源 本文结合小编自己的经验并且参考了淘宝&滴滴&美团&360&快手等各个大厂大数据平台建设的思路。在尊重事实的基础上重新组织了语言和内容,旨在给读者揭开一个完善的大数据平台的组成和发展过程。 大数据平台是为了计算,现今社会所产生的越来越大的数据量,以存储、运算、展现作为目的的平台。大数据技术是指从各种各样类型的数据中,快速获得有价值信息

【HDU】4960 Another OCD Patient 【DP】

传送门:【HDU】4960 Another OCD Patient 题目分析:比赛的时候写的太乱了,本来不需要合并的地方也合并了,现在重新改了改倒是清爽多了,顺便贴一下。 由于题目需要我们将原数组变成回文串,所以我们可以一开始就将原数组中必须合并的先合并了。那么什么是必须合并的呢?注意到左右对称,所以我们可以将左端的数相加正好等于右端的左右两个块分别合并(一定这样得到的是极小块),怎么相

如何在html中播放本地视频文件【兼容ie、火狐、谷歌、360浏览器等】

查询资料会发现,有的说用object标签,有的用embed标签,其实都是对的。只是针对的情况不一样,前者主要适用ie浏览器,后者用于火狐谷歌等其他浏览器。 <object> 标签用于包含对象,比如图像、音频、视频、Java applets、ActiveX、PDF 以及 Flash。 embed标签定义嵌入的内容,比如插件。 object和embed的区别:1、是为了兼容不同浏览器,I

在Vision Pro上实现360度全景视频播放:HLS360VideoMaterial框架介绍

随着Apple Vision Pro的推出,空间计算技术正在变得越来越普及,而360度全景视频则是其中一种令人兴奋的应用形式。对于希望在visionOS平台上集成360度视频流的开发者而言,找到合适的工具和框架至关重要。今天,我们要介绍的正是这样一个框架——HLS360VideoMaterial,它可以帮助你在Vision Pro上轻松实现360度全景视频的播放,并支持二次开发,让你的应用更上一层

最长公共上升子序列(LCIS)ZOJ 2432

立方算法: #include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#define M 505using namespace std;typedef long long LL;LL a[M],b[M];int dp[M][M];int main(){//freopen("in.txt","

修改360浏览器内核

浏览器内核控制Meta标签说明文档 背景介绍 由于众所周知的情况,国内的主流浏览器都是双核浏览器:基于Webkit内核用于常用网站的高速浏览。基于IE的内核用于兼容网银、旧版网站。以360的几款浏览器为例,我们优先通过Webkit内核渲染主流的网站,只有小量的网站通过IE内核渲染,以保证页面兼容。在过去很长一段时间里,我们主要的控制手段是一个几百k大小网址库,一个通过长期人工运营收集的

python 360 社区 监控 爬虫 in not in 问题

发生个特别奇怪的情况,最近老是收到重复邮件,检查爬虫里面有个地方竟然走了两个分支, 如果用in,元素存在的情况下,竟然会走到else里面,用notin,就不会,实在是太奇怪了,写简单的demo的时候不会出现这个情况,不知道是python的问题还是我的问题 #*-coding:utf-8-*-import urllib2import reimport smtplibimport time

【UESTC】【windy数】

windy数 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit  Status windy定义了一种windy数。 不含前导零且相邻两个数字之差至少为 2 的正整数被称为windy数。 windy想知道,在 A 和 B 之间,包括 A 和

android NDK开发中,用Cygwin调试本地代码时报错“Another debug session running,Use --force to kill it”原因及解决办法

在使用ndk-gdb调试的时候,执行$NDK/ndk-gdb --verbose报错“Another debug session running,Use --force to kill it”。      我查了NDK官方文档,是这样说的:        --force: By default, ndk-gdb aborts if it finds that another nati

ubuntu进行apt-get时候出现Package libpcre3-dev is not available, but is referred to by another package 错误

Package libpcre3-dev is not available, but is referred to by another package 这个问题的原因是ubuntu的/etc/apt/source.list中的源比较旧了,需要更新一下,更新方法: $ sudo apt-get -y update 更新完毕之后,在使用apt-get就没有问题了。