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;
}

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

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

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 3万计算机配置清单,电脑组装知识网预算2万至3万元电脑主机推荐九代酷睿i9-9900K搭RTX2080Ti全能型高配电脑主机配置清单…

    3万计算机配置清单,电脑组装知识网预算2万至3万元电脑主机推荐九代酷睿i9-9900K搭RTX2080Ti全能型高配电脑主机配置清单…本文转自:http://www.dn010.com/peizhi/710.html近日,一位网友联系了小编,说他要配一套高配置的电脑主机,主机预算约为2万至3万元,针对该网友的预算要求,小编提供一套九代酷睿i9-9900K搭RTX2080Ti全能型高配电脑主机配置清单,用户还可根据自己的喜好调整电脑配置。电脑配置清单:注意:由于更新电脑硬件的速度更快,如果产品停产,请使用新产品。另外,硬件价格会随…

    2022年7月16日
    17
  • SQL Server 2012 在sp_executesql 中生成的临时表的可见性

    SQL Server 2012 在sp_executesql 中生成的临时表的可见性在sql存储过程中,经常使用到动态sql语句,写法类似于这样Set@strParameter=N’@StartTimedatetime,@EndTimedatetime’Execsp_executesql@strSql,@strParameter,@StartTime,@EndTime为了满足业务需求,我们经常会在存储过程中使用到临时表。根据作用域的不同,分为全局临时表和用户临时

    2022年5月21日
    30
  • 数据库的查询语句_数据库select from where

    数据库的查询语句_数据库select from where一、温馨提示在dos窗口登录mysql,这里面使用库,给库中表添加一条中文数据—-会出现插入数据有问题,中文错误这是因为:1、在dos窗口中,默认的编码格式gbk,而mysql服务器软件使用的编码utf82、在dos窗口输入一个指令,模糊查询当前mysql数据库中所有带有”character”字符集的变量全部出来SHOWVARIABLESLIKE’%character%’;3、在dos窗口中需要修改setchar…

    2022年9月7日
    3
  • 外包公司怎么样「建议收藏」

    外包公司怎么样「建议收藏」其实大家每天心里都像明镜一样的明白“低技术含量的外包没有前途”,好多人都认为外包没有技术,其实这种思想不对,国外有大量的高端技术外包业务等着我们干,但是反问一句“你们能干吗?”,现在大部分的公司都是平均每个项目开发4个月,干完就再转一个组再做别的项目,从Java.NETCC++到你们没有听说过的RPG,一个有着7年开发经验的外包人员可以说自已会十几种开发语言做过几十个case,但是我们不…

    2022年5月19日
    44
  • 数据仓库(四)之ETL开发

    数据仓库(四)之ETL开发 概述 ETL是数据仓库的后台,主要包含抽取、清洗、规范化、提交四个步骤,传统数据仓库一般分为四层模型。               分层的作用                                      STG层  在维度建模阶段已经确定了源系统,而且对源系统进行了…

    2022年6月13日
    34
  • java8 stream接口终端操作 count,anyMatch,allMatch,noneMatch

    java8 stream接口终端操作 count,anyMatch,allMatch,noneMatch对于中间操作和终端操作的定义,请看《JAVA8stream接口中间操作和终端操作》,这篇主要讲述的是stream的count,anyMatch,allMatch,noneMatch操作,我们先看下函数的定义longcount();booleananyMatch(Predicate<?superT>predicate);…

    2022年10月9日
    1

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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