bzoj2288 生日礼物 (线段树)

时间:2022-10-01 11:38:08

我当然想选最大的子段和啦 但要选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 生日礼物 (线段树)的更多相关文章

  1. 2018&period;09&period;30 bzoj2288&colon;生日礼物(贪心&plus;线段树)

    传送门 线段树经典题目. 每次先找到最大子段和来更新答案,然后利用网络流反悔退流的思想把这个最大字段乘-1之后放回去. 代码: #include<bits/stdc++.h> #defin ...

  2. 【BZOJ-4556】字符串 后缀数组&plus;二分&plus;主席树 &sol; 后缀自动机&plus;线段树合并&plus;二分

    4556: [Tjoi2016&Heoi2016]字符串 Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 657  Solved: 274[Su ...

  3. 字符串&lpar;tjoi2016&comma;heoi2016&comma;bzoj4556&rpar;&lpar;sam&lpar;后缀自动机&rpar;&plus;线段树合并&plus;倍增&plus;二分答案&rpar;

    佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物.生日礼物放在一个神奇的箱子中.箱子外边写了 一个长为\(n\)的字符串\(s\),和\(m\)个问题.佳媛姐姐必须正确回答这\(m\)个问题, ...

  4. BZOJ4556 Tjoi2016&amp&semi;Heoi2016 字符串【后缀自动机&plus;倍增&plus;线段树合并】

    Description 佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物.生日礼物放在一个神奇的箱子中.箱子外边写了 一个长为n的字符串s,和m个问题.佳媛姐姐必须正确回答这m个问题,才能打开 ...

  5. bzoj3932--可持久化线段树

    题目大意: 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分.超级计算机中的 任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第 ...

  6. codevs 1082 线段树练习 3(区间维护)

    codevs 1082 线段树练习 3  时间限制: 3 s  空间限制: 128000 KB  题目等级 : 大师 Master 题目描述 Description 给你N个数,有两种操作: 1:给区 ...

  7. codevs 1576 最长上升子序列的线段树优化

    题目:codevs 1576 最长严格上升子序列 链接:http://codevs.cn/problem/1576/ 优化的地方是 1到i-1 中最大的 f[j]值,并且A[j]<A[i] .根 ...

  8. codevs 1080 线段树点修改

    先来介绍一下线段树. 线段树是一个把线段,或者说一个区间储存在二叉树中.如图所示的就是一棵线段树,它维护一个区间的和. 蓝色数字的是线段树的节点在数组中的位置,它表示的区间已经在图上标出,它的值就是这 ...

  9. codevs 1082 线段树区间求和

    codevs 1082 线段树练习3 链接:http://codevs.cn/problem/1082/ sumv是维护求和的线段树,addv是标记这歌节点所在区间还需要加上的值. 我的线段树写法在运 ...

随机推荐

  1. AC自动机

    AC自动机,全称Aho-Corasick自动机.如果没记错的话好像就是前缀自动机. 其实AC自动机就是KMP上树的产物.理解了KMP,那AC自动机应该也是很好理解的. 与KMP类似,AC自动机也是扔一 ...

  2. bbs网站 models

    bbs网站 models #!/usr/bin/env python #_*_coding:utf-8_*_ from django.db import models from django.cont ...

  3. jQuery Ajax 实例 具体介绍&dollar;&period;ajax、&dollar;&period;post、&dollar;&period;get的使用

    Jquery在异步提交方面封装的非常好.直接用AJAX非常麻烦须要处理浏览器之间的兼容问题,Jquery大大简化了我们的这些操作操作.不用在考虑浏览器这方面的问题,能够直接使用! $.post.$.g ...

  4. openssl使用&plus;Demo

    1. websiteSSL(secure Socket Layer)TLS(transport Layer Security) - SSL3.0基础之上提出的安全通信标准,目前版本是1.0openss ...

  5. HTML5&lowbar;图片合成&lowbar;刮刮卡

    刮刮卡(图片合成) 定义: globalCompositeOperation 属性,设置或返回如何将源图像 将 myCanvas 的背景图设置为一张图片,(刮开后显示) // 目标图像(已有的,外面一 ...

  6. 【bzoj4811】&lbrack;Ynoi2017&rsqb;由乃的OJ 树链剖分&plus;线段树区间合并

    题解: 好像和noi那题并没有什么区别 只是加上了修改和变成树上 比较显然我们可以用树链剖分来维护

  7. centos实现永久修改hostname

    前言 介绍一下centos的两种修改hostname的方式. 查看hostname [root@slave02 ~]# hostname slave02 临时性修改 [root@slave02 ~]# ...

  8. C&num; 反编译防范

    C# 编写的代码通过VS编译器生成 dll 或 exe ,很容易被一些反编译工具查看到源码或对源码进行修改.为防止代码被反编译或被篡改,我们可以进行一定的防范措施.但不能杜绝,因为DotNet编写代码 ...

  9. day056 多表增加和查询

    今日总结: 多表的增删改查操作 多表操作 增 book id title book_detail publish author onetoone manytoone manytomany book_o ...

  10. C&num;构造方法--实例化类时初始化的方法

    using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Cons ...