Bzoj 3747: [POI2015]Kinoman 线段树

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

3747: [POI2015]Kinoman

Time Limit: 60 Sec  Memory Limit: 128 MB
Submit: 553  Solved: 222
[Submit][Status][Discuss]

Description

共有m部电影,编号为1~m,第i部电影的好看值为w[i]。
在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n),并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

Input

第一行两个整数n,m(1<=m<=n<=1000000)。
第二行包含n个整数f[1],f[2],…,f[n](1<=f[i]<=m)。
第三行包含m个整数w[1],w[2],…,w[m](1<=w[j]<=1000000)。

Output

输出观看且仅观看过一次的电影的好看值的总和的最大值。

Sample Input

9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

Sample Output

15
样例解释:
观看第2,3,4,5,6,7天内放映的电影,其中看且仅看过一次的电影的编号为2,3,4。

HINT

 

Source

鸣谢Jcvb

题解:

线段树。。。

用last[]记录每个位置的电影的上一个位置。

然后从头到尾依次遍历,每次把 (当前位置的电影的上一个位置,当前位置] 这个区间加上当前电影的好看值。然后把 (当前位置的电影的上上一个位置,当前位置的电影的上一个位置] 这个区间减去当前电影的好看值。每次求区间最大值即可。

这个用线段树维护即可。。。

 #include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define LL long long
struct node
{
int left,right;
LL tag,mx;
}tree[];
int f[],w[],last[],pre[];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void Build(int k,int l,int r)
{
tree[k].left=l;tree[k].right=r;tree[k].tag=;tree[k].mx=;
if(l==r)return;
int mid=(l+r)/;
Build(k*,l,mid);Build(k*+,mid+,r);
}
void Pushup(int k)
{
tree[k].mx=max(tree[k*].mx,tree[k*+].mx);
}
void Pushdown(int k)
{
if(tree[k].tag!=)
{
tree[k*].tag+=tree[k].tag;
tree[k*+].tag+=tree[k].tag;
tree[k*].mx+=tree[k].tag;
tree[k*+].mx+=tree[k].tag;
tree[k].tag=;
}
}
void Add(int k,int l,int r,int add)
{
if(l<=tree[k].left&&tree[k].right<=r)
{
tree[k].tag+=(LL)add;
tree[k].mx+=(LL)add;
return;
}
Pushdown(k);
int mid=(tree[k].left+tree[k].right)/;
if(r<=mid)Add(k*,l,r,add);
else if(l>mid)Add(k*+,l,r,add);
else {Add(k*,l,mid,add);Add(k*+,mid+,r,add);}
Pushup(k);
}
int main()
{
int n,m,i;
LL ans;
n=read();m=read();
for(i=;i<=n;i++)f[i]=read();
for(i=;i<=m;i++)w[i]=read();
memset(last,,sizeof(last));
memset(pre,,sizeof(pre));
for(i=;i<=n;i++)
{
last[i]=pre[f[i]];
pre[f[i]]=i;
}
Build(,,n);
ans=-INF;
for(i=;i<=n;i++)
{
Add(,last[i]+,i,w[f[i]]);
if(last[i]!=)
{
Add(,last[last[i]]+,last[i],-w[f[i]]);
}
ans=max(ans,tree[].mx);
}
printf("%lld",ans);
return ;
}

Bzoj 3747: [POI2015]Kinoman 线段树的更多相关文章

  1. BZOJ 3747 POI2015 Kinoman 段树

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

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

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

  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. 【BZOJ3747】&lbrack;POI2015&rsqb;Kinoman 线段树

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

  5. BZOJ 3747 POI2015 Kinoman

    因为上午没有准备够题目,结果发现写完这道题没题可写了QAQ 又因为这道题范围是100w,我写了发线段树,以为要T,上午就花了一个小时拼命卡常数 结果下午一交居然过了QAQ 我们考虑枚举L,求最大R使得 ...

  6. 【bzoj3747】&lbrack;POI2015&rsqb;Kinoman 线段树区间合并

    题目描述 一个长度为n的序列,每个数为1~m之一.求一段连续子序列,使得其中之出现过一次的数对应的价值之和最大. 输入 第一行两个整数n,m(1<=m<=n<=1000000). 第 ...

  7. 【bzoj3747】&lbrack;POI2015&rsqb;Kinoman - 线段树(经典)

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

  8. BZOJ3747&colon;&lbrack;POI2015&rsqb;Kinoman&lpar;线段树&rpar;

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

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

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

随机推荐

  1. Application&period;DoEvents&lpar;&rpar;&colon;概念

    When you run a Windows Form, it creates the new form, which then waits for events to handle. Each ti ...

  2. Volley框架之网络请求和图片加载

    Volley是 Google 推出的 Android 异步网络请求框架和图片加载框架. Volley的特性 (1).封装了的异步的请求API.Volley 中大多是基于接口的设计,可配置性强.(2). ...

  3. 《Linux内核设计与实现》课程学习重点问题总结

    (问题均是同学提出或是老师上课重点讲解的部分内容,根据自身理解和笔记总结出自己的答案.如有不对,还请指教.) week2 [Q1]命令qemu -kernel 内核可执行文件 -initrd root ...

  4. Qt 中使用vector

    新建Empty qmake project,包含如下两个文件: .pro文件 SOURCES += \ main.cpp QT += core CONFIG += c++11 // 支持C++11 . ...

  5. oh-my-zsh的使用

    一.自动安装wget https://github.com/robbyrussell/oh-my-zsh/raw/master/tools/install.sh -O - | sh 二.配置文件~/. ...

  6. 做了codility网站上一题:CountBoundedSlices

    在写上一随笔之前,在Codility网站上还做了一个道题(非Demo题):CountBoundedSlices,得了60分(害臊呀).今天又重新做了一下这个算法,性能提高了不少,但由于此题不是Demo ...

  7. 【BZOJ】1012&colon; &lbrack;JSOI2008&rsqb;最大数maxnumber 树状数组求区间最值

    题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1012 题意:维护一个数列,开始时没有数值,之后会有两种操作, Q L :查询数列末 ...

  8. iOS7新特性-NSURLSession详解

    前言:本文由DevDiv版主@jas 原创翻译,转载请注明出处!原文:http://www.shinobicontrols.com/b ... day-1-nsurlsession/ 大家都知道,过去 ...

  9. slf4j 之logback日志之环境安装【一】

    一.maven引用. 传送门:http://www.slf4j.org/manual.html#projectDep <dependency> <groupId>ch.qos. ...

  10. OpenGL—Android 开机动画源码分析二

    引自http://blog.csdn.net/luoshengyang/article/details/7691321/ BootAnimation类的成员函数的实现比较长,我们分段来阅读: 第三个开 ...