因为上午没有准备够题目,结果发现写完这道题没题可写了QAQ
又因为这道题范围是100w,我写了发线段树,以为要T,上午就花了一个小时拼命卡常数
结果下午一交居然过了QAQ
我们考虑枚举L,求最大R使得[L,R]是对于当前L最大权值的区间
考虑每个点的影响
如果从L向右他是第一个,那么他会对后面产生a[f[L]]的贡献
如果从L向右他是第二个,那么他会对后面产生-a[f[L]]的贡献
然后我们维护一棵线段树,每次查询最值并且进行更新即可
include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std; typedef long long LL;
const int maxn=1000010;
int n,m,x,y,v,tim;
int f[maxn];
int a[maxn];
int next[maxn],h[maxn];
LL mx[maxn<<2],add[maxn<<2];
LL ans=0,tot=0; inline void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
}
inline LL Max(LL a,LL b){return a>b?a:b;}
inline void push_down(int o){
int L=(o<<1),R=(L|1);
add[L]+=add[o];mx[L]+=add[o];
add[R]+=add[o];mx[R]+=add[o];
add[o]=0;
}
inline void modify(int o,int L,int R){
if(L>=x&&R<=y){
mx[o]+=v;add[o]+=v;
return;
}
if(add[o]!=0)push_down(o);
int mid=(L+R)>>1;
if(y<=mid)modify(o<<1,L,mid);
else if(x>mid)modify(o<<1|1,mid+1,R);
else modify(o<<1,L,mid),modify(o<<1|1,mid+1,R);
mx[o]=Max(mx[o<<1],mx[o<<1|1]);
}
inline LL ask(int o,int L,int R){
if(L>=x&&R<=y)return mx[o];
if(add[o]!=0)push_down(o);
int mid=(L+R)>>1;
if(y<=mid)return ask(o<<1,L,mid);
else if(x>mid)return ask(o<<1|1,mid+1,R);
else return Max(ask(o<<1,L,mid),ask(o<<1|1,mid+1,R));
}
int main(){
read(n);read(m);y=n;
for(int i=1;i<=n;++i)read(f[i]);
for(int i=1;i<=m;++i)read(a[i]);
for(int i=n;i>=1;--i){
next[i]=h[f[i]];
h[f[i]]=i;
}
for(int i=1;i<=m;++i){
if(h[i]){
x=h[i];v=a[i];
modify(1,1,n);
if(next[h[i]]){
x=next[h[i]];v=-a[i];
modify(1,1,n);
}
}
}
for(int L=1;L<=n;++L){
x=L;
ans=Max(ans,ask(1,1,n)-tot);
tot+=a[f[L]];
int n1=next[L],n2=next[n1];
if(n1){
x=n1;v=(a[f[L]]<<1);
modify(1,1,n);
}
if(n2){
x=n2;v=-a[f[L]];
modify(1,1,n);
}
}printf("%lld\n",ans);
return 0;
}
BZOJ 3747 POI2015 Kinoman的更多相关文章
-
Bzoj 3747: [POI2015]Kinoman 线段树
3747: [POI2015]Kinoman Time Limit: 60 Sec Memory Limit: 128 MBSubmit: 553 Solved: 222[Submit][Stat ...
-
BZOJ 3747 POI2015 Kinoman 段树
标题效果:有m点,每个点都有一个权值.现在我们有这个m为点的长度n该序列,寻求区间,它仅出现一次在正确的点区间内值和最大 想了很久,甚至神标题,奔说是水的问题--我醉了 枚举左点 对于每个请求留点右键 ...
-
BZOJ 3747: [POI2015]Kinoman 【线段树】
Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部. 你可以选择l,r(1<=l< ...
-
【BZOJ 3747】 3747: [POI2015]Kinoman (线段树)
3747: [POI2015]Kinoman Time Limit: 60 Sec Memory Limit: 128 MBSubmit: 830 Solved: 338 Description ...
-
3747: [POI2015]Kinoman|线段树
枚举左区间线段树维护最大值 #include<algorithm> #include<iostream> #include<cstdlib> #include< ...
-
[BZOJ 3747] [POI 2015] Kinoman【线段树】
Problem Link : BZOJ 3747 题解:ZYF-ZYF 神犇的题解 解题的大致思路是,当区间的右端点向右移动一格时,只有两个区间的左端点对应的答案发生了变化. 从 f[i] + 1 到 ...
-
BZOJ3747: [POI2015]Kinoman
传送门 线段树经典运用. 设$last_i$表示上一个与$i$相同的类型.然后每次更新$[last[i]+1,i]$和$[last[last[i]]+1,last[i]]$的答案就行了. //BZOJ ...
-
BZOJ3747 POI2015 Kinoman 【线段树】*
BZOJ3747 POI2015 Kinoman Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[ ...
-
【BZOJ3747】[POI2015]Kinoman 线段树
[BZOJ3747][POI2015]Kinoman Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第 ...
随机推荐
-
ASIHTTPRequest详解 [经典3]
大文件断点续传 0.94 以后支持大文件的断点下载,只需要设置: [ request setAllowResumeForFileDownloads:YES ]; [ request setDownlo ...
-
ansible 控制windows
1.installing on the control machine On a Linux control machine: #pip install "pywinrm>=0.1.1 ...
-
javaScript 类型判断
直接上例子: 1 判断是否为数组类型 2 判断是否为字符串类型 3 判断是否为数值类型 4 判断是否为日期类型 5 判断是否为函数 6 判断是否为对象 1 判断是否为数组类型 linenum < ...
-
html5在手机端关于 map area中的自适应
https://github.com/stowball/jQuery-rwdImageMaps用这一个插件可自适应!!!
-
Fragement理解
■ 初衷 可重用,碎片化UI,适应大屏幕pad和小屏幕手机 ■ 优点 自行控制加入,移除,交换. activity则由framework深度掌管. 切换流畅 模块化(逻辑上切割处理) 缺点带来额外 ...
-
Vim实用小技巧
Vim实用小技巧 一些网络上质量较高的Vim资料 从我07年接触Vim以来,已经过去了8个年头,期间看过很多的Vim文章,我自己觉得非常不错,而且创作时间也比较近的文章有如下这些. Vim入门 目前为 ...
-
微信小程序入门——怎么建多个项目?(导入官方Demo程序进行学习)
昨天1月9日微信小程序发布,顿时被朋友圈刷爆,今天看了一下官方文档,自己开始一步一步搭建环境体验小程序开发. 常见问题: 1.微信小程序开发是否需要重新创建开发者账号? 需要,即使之前申请了微信服务号 ...
-
ios隐藏软键盘
//判断是否为苹果 var isIPHONE = navigator.userAgent.toUpperCase().indexOf('IPHONE')!= -1; // 元素失去焦点隐藏iphone ...
-
MAC中使用Vim和GCC编译C程序
1.打开终端 2.输入以下命令进入vim编辑器: vim a.c 3.进入编辑器后按i进入insert模式,然后键入以下代码: #include<stdio.h> int main(){ ...
-
jsoup从表单中取数据
表单的格式如下 <td>user</td> <td>cc</td> </tr> <tr> <td>pass</ ...