3747: [POI2015]Kinoman
Time Limit: 60 Sec Memory Limit: 128 MB
Submit: 553 Solved: 222
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
2 3 1 1 4 1 2 4 1
5 3 6 6
Sample Output
样例解释:
观看第2,3,4,5,6,7天内放映的电影,其中看且仅看过一次的电影的编号为2,3,4。
HINT
Source
题解:
线段树。。。
用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 线段树的更多相关文章
-
BZOJ 3747 POI2015 Kinoman 段树
标题效果:有m点,每个点都有一个权值.现在我们有这个m为点的长度n该序列,寻求区间,它仅出现一次在正确的点区间内值和最大 想了很久,甚至神标题,奔说是水的问题--我醉了 枚举左点 对于每个请求留点右键 ...
-
3747: [POI2015]Kinoman|线段树
枚举左区间线段树维护最大值 #include<algorithm> #include<iostream> #include<cstdlib> #include< ...
-
BZOJ 3747: [POI2015]Kinoman 【线段树】
Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部. 你可以选择l,r(1<=l< ...
-
【BZOJ3747】[POI2015]Kinoman 线段树
[BZOJ3747][POI2015]Kinoman Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第 ...
-
BZOJ 3747 POI2015 Kinoman
因为上午没有准备够题目,结果发现写完这道题没题可写了QAQ 又因为这道题范围是100w,我写了发线段树,以为要T,上午就花了一个小时拼命卡常数 结果下午一交居然过了QAQ 我们考虑枚举L,求最大R使得 ...
-
【bzoj3747】[POI2015]Kinoman 线段树区间合并
题目描述 一个长度为n的序列,每个数为1~m之一.求一段连续子序列,使得其中之出现过一次的数对应的价值之和最大. 输入 第一行两个整数n,m(1<=m<=n<=1000000). 第 ...
-
【bzoj3747】[POI2015]Kinoman - 线段树(经典)
Description 共有m部电影,编号为1~m,第i部电影的好看值为w[i]. 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部. 你可以选择l,r(1<=l< ...
-
BZOJ3747:[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 ...
随机推荐
-
Application.DoEvents():概念
When you run a Windows Form, it creates the new form, which then waits for events to handle. Each ti ...
-
Volley框架之网络请求和图片加载
Volley是 Google 推出的 Android 异步网络请求框架和图片加载框架. Volley的特性 (1).封装了的异步的请求API.Volley 中大多是基于接口的设计,可配置性强.(2). ...
-
《Linux内核设计与实现》课程学习重点问题总结
(问题均是同学提出或是老师上课重点讲解的部分内容,根据自身理解和笔记总结出自己的答案.如有不对,还请指教.) week2 [Q1]命令qemu -kernel 内核可执行文件 -initrd root ...
-
Qt 中使用vector
新建Empty qmake project,包含如下两个文件: .pro文件 SOURCES += \ main.cpp QT += core CONFIG += c++11 // 支持C++11 . ...
-
oh-my-zsh的使用
一.自动安装wget https://github.com/robbyrussell/oh-my-zsh/raw/master/tools/install.sh -O - | sh 二.配置文件~/. ...
-
做了codility网站上一题:CountBoundedSlices
在写上一随笔之前,在Codility网站上还做了一个道题(非Demo题):CountBoundedSlices,得了60分(害臊呀).今天又重新做了一下这个算法,性能提高了不少,但由于此题不是Demo ...
-
【BZOJ】1012: [JSOI2008]最大数maxnumber 树状数组求区间最值
题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1012 题意:维护一个数列,开始时没有数值,之后会有两种操作, Q L :查询数列末 ...
-
iOS7新特性-NSURLSession详解
前言:本文由DevDiv版主@jas 原创翻译,转载请注明出处!原文:http://www.shinobicontrols.com/b ... day-1-nsurlsession/ 大家都知道,过去 ...
-
slf4j 之logback日志之环境安装【一】
一.maven引用. 传送门:http://www.slf4j.org/manual.html#projectDep <dependency> <groupId>ch.qos. ...
-
OpenGL—Android 开机动画源码分析二
引自http://blog.csdn.net/luoshengyang/article/details/7691321/ BootAnimation类的成员函数的实现比较长,我们分段来阅读: 第三个开 ...