【POI2015】Kinoman（思维，线段树）_「poi2015」kinoman-CSDN博客

本文链接：https://blog.csdn.net/Patrickpwq/article/details/86694367

这篇博客介绍了POI2015竞赛中的一道题目Kinoman，讨论了如何利用线段树解决区间修改与查询最大值的问题。博主指出，通过维护每个数上一次出现的位置pre[i]，可以实现动态更新区间，并避免区间减法导致的错误。每加入一个数，对相应区间进行增减操作，重点在于只对pre[pre[i]]+1~pre[i]区间进行减法修正。最终，通过线段树维护区间内的最大值，实现高效求解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

这是一道不错的题，不过我并没有思考充分就实在忍不住看了题解，有点遗憾

记pre[i]表示原序列i位置的数上一次出现的位置

每加入一个数，我们发现pre[i+1]~i作为左端点的答案就增加了w，1~pre[i]减少了w

我们可以枚举右端点，每加入一个数进行区间加/减操作，不过我们发现，虽然从理论上来讲的确是1~pre[i]减少了w，不过如果每次都区间减，那会减出问题的。所以实际上，每次只需要对pre[pre[i]]+1~pre[i]减就行了。

至于答案，每加入新端点就查询1~n的最大值即可

区间修改+最大=线段树

#include<bits/stdc++.h>
#define ll long long
const int N=1000005;
using namespace std;
template<class T>
inline void read(T &x)
{
	x=0; int f=1;
	static char ch=getchar();
	while(!isdigit(ch))	{if(ch=='-') f=-1;ch=getchar();} 
	while(isdigit(ch))	x=x*10+ch-'0',ch=getchar();
	x*=f;
}
int n,m,pre[N],f[N],base[N];
ll w[N];
struct Tree
{
	int l,r;
	ll maxv,f;
}tree[4*N];
inline void build(int now,int l,int r)
{
	tree[now].l=l; tree[now].r=r;
	if(l==r) return;
	int m=(tree[now].l+tree[now].r)>>1;
	build(now<<1,l,m);
	build(now<<1|1,m+1,r);
}
inline void pushdown(int now)
{
	if(!tree[now].f)	return;
	tree[now<<1].maxv+=tree[now].f; tree[now<<1].f+=tree[now].f;
	tree[now<<1|1].maxv+=tree[now].f; tree[now<<1|1].f+=tree[now].f;
	tree[now].f=0;
}
inline void modify(int now,int l,int r,ll x)
{
	if(l<=tree[now].l&&tree[now].r<=r)
	{
		tree[now].maxv+=x;
		tree[now].f+=x;
		return;
	}
	pushdown(now);
	int m=(tree[now].l+tree[now].r)>>1;
	if(l<=m) modify(now<<1,l,r,x);
	if(r>m)	modify(now<<1|1,l,r,x);
	tree[now].maxv=max(tree[now<<1].maxv,tree[now<<1|1].maxv);
}
inline ll query(int now,int l,int r)
{
	if(l<=tree[now].l&&tree[now].r<=r)
		return tree[now].maxv;
	pushdown(now);
	int m=(tree[now].l+tree[now].r)>>1;
	ll ans=0;
	if(l<=m) ans=max(ans,query(now<<1,l,r));
	if(r>m)	ans=max(ans,query(now<<1|1,l,r));
	return ans;
}
int main()
{
	read(n); read(m);
	for(int i=1;i<=n;i++)	
	{
		read(f[i]);
		pre[i]=base[f[i]];
		base[f[i]]=i;
	}
	build(1,1,n);
	for(int i=1;i<=m;i++) read(w[i]);
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		modify(1,pre[i]+1,i,w[f[i]]);
		if(pre[i]) modify(1,pre[pre[i]]+1,pre[i],-w[f[i]]);
		ans=max(ans,query(1,1,n));
	}
	cout<<ans;
	return 0;
}