标题效果：有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;

}