BZOJ 3747 POI2015 Kinoman

时间:2022-08-28 18:40:36

因为上午没有准备够题目,结果发现写完这道题没题可写了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的更多相关文章

  1. Bzoj 3747&colon; &lbrack;POI2015&rsqb;Kinoman 线段树

    3747: [POI2015]Kinoman Time Limit: 60 Sec  Memory Limit: 128 MBSubmit: 553  Solved: 222[Submit][Stat ...

  2. BZOJ 3747 POI2015 Kinoman 段树

    标题效果:有m点,每个点都有一个权值.现在我们有这个m为点的长度n该序列,寻求区间,它仅出现一次在正确的点区间内值和最大 想了很久,甚至神标题,奔说是水的问题--我醉了 枚举左点 对于每个请求留点右键 ...

  3. BZOJ 3747&colon; &lbrack;POI2015&rsqb;Kinoman 【线段树】

    Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部. 你可以选择l,r(1<=l< ...

  4. 【BZOJ 3747】 3747&colon; &lbrack;POI2015&rsqb;Kinoman (线段树)

    3747: [POI2015]Kinoman Time Limit: 60 Sec  Memory Limit: 128 MBSubmit: 830  Solved: 338 Description ...

  5. 3747&colon; &lbrack;POI2015&rsqb;Kinoman&vert;线段树

    枚举左区间线段树维护最大值 #include<algorithm> #include<iostream> #include<cstdlib> #include&lt ...

  6. &lbrack;BZOJ 3747&rsqb; &lbrack;POI 2015&rsqb; Kinoman【线段树】

    Problem Link : BZOJ 3747 题解:ZYF-ZYF 神犇的题解 解题的大致思路是,当区间的右端点向右移动一格时,只有两个区间的左端点对应的答案发生了变化. 从 f[i] + 1 到 ...

  7. BZOJ3747&colon; &lbrack;POI2015&rsqb;Kinoman

    传送门 线段树经典运用. 设$last_i$表示上一个与$i$相同的类型.然后每次更新$[last[i]+1,i]$和$[last[last[i]]+1,last[i]]$的答案就行了. //BZOJ ...

  8. BZOJ3747 POI2015 Kinoman 【线段树】&ast;

    BZOJ3747 POI2015 Kinoman Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[ ...

  9. 【BZOJ3747】&lbrack;POI2015&rsqb;Kinoman 线段树

    [BZOJ3747][POI2015]Kinoman Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第 ...

随机推荐

  1. ASIHTTPRequest详解 &lbrack;经典3&rsqb;

    大文件断点续传 0.94 以后支持大文件的断点下载,只需要设置: [ request setAllowResumeForFileDownloads:YES ]; [ request setDownlo ...

  2. ansible 控制windows

    1.installing on the control machine On a Linux control machine: #pip install "pywinrm>=0.1.1 ...

  3. javaScript 类型判断

    直接上例子: 1 判断是否为数组类型 2 判断是否为字符串类型 3 判断是否为数值类型 4 判断是否为日期类型 5 判断是否为函数 6 判断是否为对象 1 判断是否为数组类型 linenum < ...

  4. html5在手机端关于 map area中的自适应

    https://github.com/stowball/jQuery-rwdImageMaps用这一个插件可自适应!!!

  5. Fragement理解

    ■ 初衷 可重用,碎片化UI,适应大屏幕pad和小屏幕手机 ■ 优点 自行控制加入,移除,交换. activity则由framework深度掌管. 切换流畅 模块化(逻辑上切割处理)   缺点带来额外 ...

  6. Vim实用小技巧

    Vim实用小技巧 一些网络上质量较高的Vim资料 从我07年接触Vim以来,已经过去了8个年头,期间看过很多的Vim文章,我自己觉得非常不错,而且创作时间也比较近的文章有如下这些. Vim入门 目前为 ...

  7. 微信小程序入门——怎么建多个项目?(导入官方Demo程序进行学习)

    昨天1月9日微信小程序发布,顿时被朋友圈刷爆,今天看了一下官方文档,自己开始一步一步搭建环境体验小程序开发. 常见问题: 1.微信小程序开发是否需要重新创建开发者账号? 需要,即使之前申请了微信服务号 ...

  8. ios隐藏软键盘

    //判断是否为苹果 var isIPHONE = navigator.userAgent.toUpperCase().indexOf('IPHONE')!= -1; // 元素失去焦点隐藏iphone ...

  9. MAC中使用Vim和GCC编译C程序

    1.打开终端 2.输入以下命令进入vim编辑器: vim a.c 3.进入编辑器后按i进入insert模式,然后键入以下代码: #include<stdio.h> int main(){ ...

  10. jsoup从表单中取数据

    表单的格式如下 <td>user</td> <td>cc</td> </tr> <tr> <td>pass</ ...