CF280D-k-Maximum Subsequence Sum【模拟费用流,线段树】
2024-08-30 10:23:42
正题
题目链接:https://www.luogu.com.cn/problem/CF280D
题目大意
一个长度为\(n\)的序列,\(m\)次操作
- 修改一个数
- 询问一个区间中选出\(k\)段不交子段使得和最大
\(1\leq n\leq 10^5,1\leq m\leq 2\times 10^5,1\leq k\leq 20\)
解题思路
考虑模拟一下费用流,发现费用流的每次增广就是不停找到一个最大的子段取反。
用线段树维护最大子段,然后取反的话维护一个正的一个反的。
每次暴力做\(k\)次再倒流回去就好了。
时间复杂度:\(O(nk\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=1e5+10;
struct node{
int lw,rw,w;
int mx,l,r,L,R;
}w[N<<2],v[N<<2];
int n,m,lazy[N<<2];
stack<pair<int,int> >s;
node Merge(node L,node R){
node tmp;tmp.w=L.w+R.w;
if(L.mx>R.mx)tmp.mx=L.mx,tmp.l=L.l,tmp.r=L.r;
else tmp.mx=R.mx,tmp.l=R.l,tmp.r=R.r;
if(L.rw+R.lw>tmp.mx)tmp.mx=L.rw+R.lw,tmp.l=L.R,tmp.r=R.L;
if(L.lw>=L.w+R.lw)tmp.lw=L.lw,tmp.L=L.L;
else tmp.lw=L.w+R.lw,tmp.L=R.L;
if(R.rw>=R.w+L.rw)tmp.rw=R.rw,tmp.R=R.R;
else tmp.rw=R.w+L.rw,tmp.R=L.R;
return tmp;
}
void Downdata(int x){
if(!lazy[x])return;
lazy[x*2]^=1;swap(w[x*2],v[x*2]);
lazy[x*2+1]^=1;swap(w[x*2+1],v[x*2+1]);
lazy[x]=0;return;
}
void Change(int x,int L,int R,int l,int r){
if(L==l&&R==r){swap(w[x],v[x]);lazy[x]^=1;return;}
int mid=(L+R)>>1;Downdata(x);
if(r<=mid)Change(x*2,L,mid,l,r);
else if(l>mid)Change(x*2+1,mid+1,R,l,r);
else Change(x*2,L,mid,l,mid),Change(x*2+1,mid+1,R,mid+1,r);
w[x]=Merge(w[x*2],w[x*2+1]);
v[x]=Merge(v[x*2],v[x*2+1]);
return;
}
void Updata(int x,int L,int R,int pos,int val){
if(L==R){
w[x].w=w[x].mx=w[x].lw=w[x].rw=val;w[x].l=w[x].r=w[x].L=w[x].R=pos;
v[x].w=v[x].mx=v[x].lw=v[x].rw=-val;v[x].l=v[x].r=v[x].L=v[x].R=pos;
return;
}
int mid=(L+R)>>1;Downdata(x);
if(pos<=mid)Updata(x*2,L,mid,pos,val);
else Updata(x*2+1,mid+1,R,pos,val);
w[x]=Merge(w[x*2],w[x*2+1]);
v[x]=Merge(v[x*2],v[x*2+1]);
return;
}
node Ask(int x,int L,int R,int l,int r){
if(L==l&&R==r)return w[x];
int mid=(L+R)>>1;Downdata(x);
if(r<=mid)return Ask(x*2,L,mid,l,r);
if(l>mid)return Ask(x*2+1,mid+1,R,l,r);
return Merge(Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r));
}
int main()
{
scanf("%d",&n);
for(int i=1,x;i<=n;i++)
scanf("%d",&x),Updata(1,1,n,i,x);
scanf("%d",&m);
while(m--){
int op;scanf("%d",&op);
if(op==0){
int x,w;
scanf("%d%d",&x,&w);
Updata(1,1,n,x,w);
node tmp=Ask(1,1,n,4,9);
tmp.w++;tmp.w--;
}
else{
int l,r,k,ans=0;
scanf("%d%d%d",&l,&r,&k);
while(k){
node tmp=Ask(1,1,n,l,r);
if(tmp.mx>0){
ans+=tmp.mx;k--;
s.push(mp(tmp.l,tmp.r));
Change(1,1,n,tmp.l,tmp.r);
}
else break;
}
printf("%d\n",ans);
while(!s.empty())
Change(1,1,n,s.top().first,s.top().second),s.pop();
}
}
return 0;
}
最新文章
- 3.JAVA之GUI编程Frame窗口
- C# 把日期字符串转换为日期类型 (MM大写为月、小写为分钟)
- MFC程序执行顺序 .
- 安全标识符SID技术介绍及查看技巧
- c.BIO连接器与NIO连接器的对比
- hdu 1240:Asteroids!(三维BFS搜索)
- 【C语言】05-printf和scanf函数
- 2016 Multi-University Training Contest 5 Two
- 高仿百度传课应用客户端源码iOS版
- 学点bootstrap
- MVC的DependencyResolver组件
- select超链接跳转A
- CentOS 7 - 最小化安装后,解决无法使用yum命令问题!!
- 获取进程ID,父进程ID,进程完整路径
- Vue.js $nextTick
- Vagrant入门一(转)
- dede 复制文章,远程图片无法本地化
- RAC with asm on AIX, ORA-01114 error,with ";gipcretAuthFail (22) "; in ocssd.log
- Xilinx zynq-7000系列FPGA移植Linux操作系统详细教程
- ssm-maven 所需添加的所有映射
热门文章
- SpringBoot和mybatis整合报错:Caused by: org.apache.ibatis.builder.BuilderException: Error creating document instance. Cause: org.xml.sax.SAXParseException; lineNumber: 152; columnNumber: 10; 元素类型为 ";mapper";
- springboot如何使用事物注解方式
- webapp网络定位
- 初识apache DBCP连接池
- Linux centos 安装 jenkins &; 本地构建jar &; 远程构建jar
- 打印菱形图案(PTA)
- servlet处理跨域请求
- windows下mysql5.7.17配置
- Java并发之AQS原理解读(二)
- C++模板简介