我当然想选最大的子段和啦 但要选M次 那不一定就是最好的
所以提供一个反悔的选项,我选了一段以后,就把它们乘个-1,然后再选最好的(类似于网络流的思路)
这个可以用线段树来维护,记一个区间包含左端点/右端点的最大值、最小值(因为要乘-1),还有它们的端点位置
然后一直找 直到最大值<=0
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=1e5+,inf=0x3f3f3f3f; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
}
struct Pos{
int v,l,r;
Pos (int a=,int b=,int c=){v=a,l=b,r=c;}
};
struct Node{
Pos lmas,rmas,lmis,rmis,ma,mi,sum;
}tr[maxn<<]; bool laz[maxn<<];
int N,M,v[maxn]; bool operator <(Pos a,Pos b){
return a.v<b.v;
}
Pos operator +(Pos a,Pos b){
return Pos(a.v+b.v,a.l,b.r);
}
Pos operator -(Pos x){return Pos(-x.v,x.l,x.r);} Node operator +(Node a,Node b){
Node x;
x.sum=a.sum+b.sum;
x.lmas=max(a.lmas,a.sum+b.lmas);
x.rmas=max(b.rmas,a.rmas+b.sum);
x.lmis=min(a.lmis,a.sum+b.lmis);
x.rmis=min(b.rmis,a.rmis+b.sum);
x.ma=max(a.rmas+b.lmas,max(a.ma,b.ma));
x.mi=min(a.rmis+b.lmis,min(a.mi,b.mi));
return x;
} inline void build(int p,int l,int r){
if(l==r){
tr[p].sum=tr[p].lmas=tr[p].rmas=tr[p].lmis=tr[p].rmis=tr[p].ma=tr[p].mi=Pos(v[l],l,r);
}else{
int m=l+r>>;
build(p<<,l,m),build(p<<|,m+,r);
tr[p]=tr[p<<]+tr[p<<|];
}
} void deal(int p){
laz[p]^=;
Pos t=tr[p].lmas;
tr[p].lmas=-tr[p].lmis;tr[p].lmis=-t;
t=tr[p].rmas;
tr[p].rmas=-tr[p].rmis;tr[p].rmis=-t;
t=tr[p].ma;
tr[p].ma=-tr[p].mi;tr[p].mi=-t;
tr[p].sum=-tr[p].sum;
} inline void pushdown(int p){
if(!laz[p]) return;
deal(p<<),deal(p<<|);
laz[p]=;
} inline void rever(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) deal(p);
else{
pushdown(p);
int m=l+r>>;
if(x<=m) rever(p<<,l,m,x,y);
if(y>=m+) rever(p<<|,m+,r,x,y);
tr[p]=tr[p<<]+tr[p<<|];
}
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),M=rd();
for(i=;i<=N;i++)
v[i]=rd();
int ans=;
build(,,N);
for(i=;i<=M;i++){
Pos x=tr[].ma;if(x.v<=) break;
ans+=x.v;
rever(,,N,x.l,x.r);
}
printf("%d\n",ans);
return ;
}
bzoj2288 生日礼物 (线段树)的更多相关文章
-
2018.09.30 bzoj2288:生日礼物(贪心+线段树)
传送门 线段树经典题目. 每次先找到最大子段和来更新答案,然后利用网络流反悔退流的思想把这个最大字段乘-1之后放回去. 代码: #include<bits/stdc++.h> #defin ...
-
【BZOJ-4556】字符串 后缀数组+二分+主席树 / 后缀自动机+线段树合并+二分
4556: [Tjoi2016&Heoi2016]字符串 Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 657 Solved: 274[Su ...
-
字符串(tjoi2016,heoi2016,bzoj4556)(sam(后缀自动机)+线段树合并+倍增+二分答案)
佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物.生日礼物放在一个神奇的箱子中.箱子外边写了 一个长为\(n\)的字符串\(s\),和\(m\)个问题.佳媛姐姐必须正确回答这\(m\)个问题, ...
-
BZOJ4556 Tjoi2016&;Heoi2016 字符串【后缀自动机+倍增+线段树合并】
Description 佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物.生日礼物放在一个神奇的箱子中.箱子外边写了 一个长为n的字符串s,和m个问题.佳媛姐姐必须正确回答这m个问题,才能打开 ...
-
bzoj3932--可持久化线段树
题目大意: 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分.超级计算机中的 任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第 ...
-
codevs 1082 线段树练习 3(区间维护)
codevs 1082 线段树练习 3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 Description 给你N个数,有两种操作: 1:给区 ...
-
codevs 1576 最长上升子序列的线段树优化
题目:codevs 1576 最长严格上升子序列 链接:http://codevs.cn/problem/1576/ 优化的地方是 1到i-1 中最大的 f[j]值,并且A[j]<A[i] .根 ...
-
codevs 1080 线段树点修改
先来介绍一下线段树. 线段树是一个把线段,或者说一个区间储存在二叉树中.如图所示的就是一棵线段树,它维护一个区间的和. 蓝色数字的是线段树的节点在数组中的位置,它表示的区间已经在图上标出,它的值就是这 ...
-
codevs 1082 线段树区间求和
codevs 1082 线段树练习3 链接:http://codevs.cn/problem/1082/ sumv是维护求和的线段树,addv是标记这歌节点所在区间还需要加上的值. 我的线段树写法在运 ...
随机推荐
-
AC自动机
AC自动机,全称Aho-Corasick自动机.如果没记错的话好像就是前缀自动机. 其实AC自动机就是KMP上树的产物.理解了KMP,那AC自动机应该也是很好理解的. 与KMP类似,AC自动机也是扔一 ...
-
bbs网站 models
bbs网站 models #!/usr/bin/env python #_*_coding:utf-8_*_ from django.db import models from django.cont ...
-
jQuery Ajax 实例 具体介绍$.ajax、$.post、$.get的使用
Jquery在异步提交方面封装的非常好.直接用AJAX非常麻烦须要处理浏览器之间的兼容问题,Jquery大大简化了我们的这些操作操作.不用在考虑浏览器这方面的问题,能够直接使用! $.post.$.g ...
-
openssl使用+Demo
1. websiteSSL(secure Socket Layer)TLS(transport Layer Security) - SSL3.0基础之上提出的安全通信标准,目前版本是1.0openss ...
-
HTML5_图片合成_刮刮卡
刮刮卡(图片合成) 定义: globalCompositeOperation 属性,设置或返回如何将源图像 将 myCanvas 的背景图设置为一张图片,(刮开后显示) // 目标图像(已有的,外面一 ...
-
【bzoj4811】[Ynoi2017]由乃的OJ 树链剖分+线段树区间合并
题解: 好像和noi那题并没有什么区别 只是加上了修改和变成树上 比较显然我们可以用树链剖分来维护
-
centos实现永久修改hostname
前言 介绍一下centos的两种修改hostname的方式. 查看hostname [root@slave02 ~]# hostname slave02 临时性修改 [root@slave02 ~]# ...
-
C# 反编译防范
C# 编写的代码通过VS编译器生成 dll 或 exe ,很容易被一些反编译工具查看到源码或对源码进行修改.为防止代码被反编译或被篡改,我们可以进行一定的防范措施.但不能杜绝,因为DotNet编写代码 ...
-
day056 多表增加和查询
今日总结: 多表的增删改查操作 多表操作 增 book id title book_detail publish author onetoone manytoone manytomany book_o ...
-
C#构造方法--实例化类时初始化的方法
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Cons ...