2018.08.15 bzoj3747: [POI2015]Kinoman(线段树)
2024-08-28 19:26:21
传送门
简单题。
先不管时间复杂度看看怎么做。
对于一段区间[l,r],如果从右端加入一个数a[r+1],对这个区间有什么影响?显然如果区间中已经有了a[r+1]这个数就会产生-a[i+1]的影响,否则就会产生a[i+1]的影响。
于是对于每个数维护一个pred[i]表示上一个a[i]这个数值的下标。
如果我们枚举右端点i,对于每一个i维护一个[j,i]的最大值。这样每次相当于对[pred[i]+1,i]这段区间做一个区间加,对[pred[pred[i]]+1,pred[i]]有一个区间减的效果。
直接搞是O(n^2)的,无法接受。
所以果断线段树优化一波就行了。
代码:
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m,f[N],pred[N],last[N];
ll w[N];
struct node{int l,r;ll add,mx;}T[N<<2];
inline ll max(ll a,ll b){return a>b?a:b;}
inline void pushup(int p){T[p].mx=max(T[lc].mx,T[rc].mx);}
inline void pushnow(int p,ll v){T[p].add+=v,T[p].mx+=v;}
inline void pushdown(int p){if(T[p].add)pushnow(lc,T[p].add),pushnow(rc,T[p].add),T[p].add=0;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].add=0;
if(l==r)return;
build(lc,l,mid),build(rc,mid+1,r);
}
inline void update(int p,int ql,int qr,ll v){
if(ql>T[p].r||qr<T[p].l)return;
if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
pushup(p);
}
inline ll query(int p,int ql,int qr){
if(ql>T[p].r||qr<T[p].l)return 0;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].mx;
pushdown(p);
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return max(query(lc,ql,mid),query(rc,mid+1,qr));
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i)f[i]=read();
for(int i=1;i<=m;++i)w[i]=read();
for(int i=1;i<=n;++i)pred[i]=last[f[i]],last[f[i]]=i;
ll ans=0;
build(1,1,n);
for(int i=1;i<=n;++i){
update(1,pred[i]+1,i,w[f[i]]);
if(pred[i])update(1,pred[pred[i]]+1,pred[i],-w[f[i]]);
ans=max(ans,query(1,1,i));
}
cout<<ans;
return 0;
}
最新文章
- Javascript实用方法
- 探索c#之不可变数据类型
- ERROR 1267 (HY000): Illegal mix of collations (utf8_general_ci,IMPLICIT) and (utf8_unicode_ci,IMPLICIT) for operation &#39;=&#39;
- 提示用户一直输入数字(默认为正整数),当用户输入end的时候显示当前输入数字中的最大值。
- ubuntu 安装phpmyadmin
- Android自定义控件(二)——有弹性的ScrollView
- webpack 打包成功,但是css不起作用
- Mac下使用终端连接远程使用ssh协议的git服务器
- Web API中的路由(二)——属性路由
- MySQL 之 MHA + ProxySQL + keepalived 实现读写分离,高可用(一)
- golang学习笔记8 beego参数配置 打包linux命令
- 09:vuex组件间通信
- 安装composer,以及通过composer安装laravel
- jQuery插件初级练习4答案
- ASP.NET开发,从二层至三层,至面向对象 (4)
- 如何控制dedecms描述的长度?
- Beta冲刺二——《WAP团队》
- sqoop操作之HIVE导出到ORACLE
- git忽略某个文件夹
- (转)Android 读取联系人(详细)
热门文章
- leetcode521
- Caused by: java.lang.IllegalStateException: Expected raw type form of org.springframework.web.servlet.handler.AbstractHandlerMethodMapping$Match
- 表格(table)
- 基于OpenGL编写一个简易的2D渲染框架-05 渲染文本
- python 3 属性查找与绑定方法
- 15 python re 模块
- eclipse中创建多模块maven web项目
- Nagios自定义扩展
- jemalloc for mysql
- vim跳转到指定行