BZOJ 3747 POI2015 Kinoman 段树

BZOJ 3747 POI2015 Kinoman 段树

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

标题效果:有m点,每个点都有一个权值。现在我们有这个m为点的长度n该序列,寻求区间,它仅出现一次在正确的点区间内值和最大

想了很久,甚至神标题,奔说是水的问题……我醉了

枚举左点 对于每个请求留点右键点 树维护最大值

考虑每一个数对答案的贡献 记录一个数组next表示这个位置上的点下一次出现的位置 那么这个点贡献的作用范围就是[i,next[i]-1] 假设没有next就是[i,n]

于是我们先把全部第一个出现的数对答案的贡献增加线段树 然后从左到右扫一遍 每次统计完答案之后把i对答案的贡献去除 然后把next[i]对答案的贡献增加线段树

这常数我也是醉了……速度倒数第二啥的 正解一定不是这种……

此外POI2015是我穿错年代了?

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1001001
using namespace std;
struct Segtree{
	Segtree *ls,*rs;
	long long num,mark;
	void Build_Tree(int x,int y);
	void Update(int x,int y,int l,int r,long long val);
	long long Get_Ans(int x,int y,int l,int r);
}*root=new Segtree,mempool[M<<1],*C=mempool;
int n,m;
int a[M],w[M],next[M],last[M];
bool v[M];
long long ans;
void Segtree :: Build_Tree(int x,int y)
{
	int mid=x+y>>1;
	num=0;mark=0;
	if(x==y) return ;
	ls=C++;rs=C++;
	ls->Build_Tree(x,mid);
	rs->Build_Tree(mid+1,y);
}
void Segtree :: Update(int x,int y,int l,int r,long long val)
{
	int mid=x+y>>1;
	if(x==l&&y==r)
	{
		num+=val;
		mark+=val;
		return ;
	}
	if(mark)
	{
		ls->num+=mark;
		rs->num+=mark;
		ls->mark+=mark;
		rs->mark+=mark;
		mark=0;
	}
	if(r<=mid) ls->Update(x,mid,l,r,val);
	else if(l>mid) rs->Update(mid+1,y,l,r,val);
	else ls->Update(x,mid,l,mid,val),rs->Update(mid+1,y,mid+1,r,val);
	num=max(ls->num,rs->num);
}
long long Segtree ::  Get_Ans(int x,int y,int l,int r)
{
	int mid=x+y>>1;
	if(x==l&&y==r)
		return num;
	if(mark)
	{
		ls->num+=mark;
		rs->num+=mark;
		ls->mark+=mark;
		rs->mark+=mark;
		mark=0;
	}
	if(r<=mid) return ls->Get_Ans(x,mid,l,r);
	if(l> mid) return rs->Get_Ans(mid+1,y,l,r);
	return max( ls->Get_Ans(x,mid,l,mid) , rs->Get_Ans(mid+1,y,mid+1,r) );
}
int main()
{
	int i;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=m;i++)
		scanf("%d",&w[i]);
	for(i=1;i<=n;i++)
	{
		if(last[a[i]])
			next[last[a[i]]]=i;
		else
			v[i]=1;
		last[a[i]]=i;
	}
	root->Build_Tree(1,n);
	for(i=1;i<=n;i++)
		if(v[i])
			root->Update(1,n,i,next[i]?next[i]-1:n,w[a[i]]);
	for(i=1;i<=n;i++)
	{
		ans=max(ans, root->Get_Ans(1,n,i,n) );
		root->Update(1,n,i,next[i]?next[i]-1:n,-w[a[i]]);
		if(next[i])
			root->Update(1,n,next[i],next[next[i]]?next[next[i]]-1:n,w[a[next[i]]]);
	}
	cout<<ans<<endl;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117735.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • dump文件 linux,Linux下快速分析DUMP文件「建议收藏」

    dump文件 linux,Linux下快速分析DUMP文件「建议收藏」dump文件传输到本地进行分析,常常需要大量的等待时间。使用IBM的eclipse的MAT工具可以直接在服务器上进行快速DUMP分析。运行环境要求linux操作系统JDK8以上下载MAT的linux版本Eclipse的MAT工具下载链接MAT支持各种操作系统,找到Linux版本下载下来#运行uname-m看一下linux是x86_64还是x86的帮助你选择下载那个版本。uname-…

  • nginx负载均衡的5种策略及原理

    nginx负载均衡的5种策略及原理nginx的upstream目前支持的5种方式的分配1、轮询(默认)每个请求按时间顺序逐一分配到不同的后端服务器,如果后端服务器down掉,能自动剔除。 upstreambackserver{ server192.168.0.14; server192.168.0.15; } 2、指定权重指定轮询几率,weight和访问比率成正比,用于后端服务器性能不均的情况。 upst…

  • python语言变量命名-以下选项中不符合 Python 语言变量命名规则的是( )。_学小易找答案…[通俗易懂]

    python语言变量命名-以下选项中不符合 Python 语言变量命名规则的是( )。_学小易找答案…[通俗易懂]【单选题】在Python中,正确的赋值语句为()。【单选题】Python语句print(chr(97))的运行结果是()。【多选题】影响管理者道德因素包括()。【单选题】表达式len(range(1,10))的值为()。【判断题】新闻可视化的方式千差万别,但万变不离其宗,就是要把好看的图表做出来,跟新闻故事无关。【单选题】执行语句for(i=1;i++2>6…

  • html两个div占满一行,设置div背景色,用float浮动并让键值对形式的文字键右对齐,值左对齐

    html两个div占满一行,设置div背景色,用float浮动并让键值对形式的文字键右对齐,值左对齐

  • 开源 网管 工具_网管软件

    开源 网管 工具_网管软件Nagios:最大的亮点是轻量灵活,且报警机制很强,如果你只是需要监控服务器/服务是否在运行,Nagios以前只是从目标主机收集信息,,并且有很强大的发送报警信息的功能。适合监视大量服务器上面的大批服务是否正常,重点并不在图形化的监控,其集成的很多功能例如报警,都是cacti没有或者很弱的.cacti主要用途还是用来收集历史数据和画图,所以界面比nagios漂亮很多cact

  • webstorm激活码【中文破解版】

    (webstorm激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlMLZPB5EL5Q-eyJsaWNlbnNlSW…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号