Bzoj 3747 poi2015 kinoman segment tree

Hello everyone , I meet you again , I'm the king of the whole stack , I've prepared for you today Idea Registration code .

Title Effect ： Yes m spot , Each point has a weight . Now we have this m Is the length of the point n This sequence , Seek the interval , It only appears once in the correct point interval and the maximum

I thought for a long time. , Even God's title , Ben said it was a water problem …… I'm drunk

Enumerate left points For each request, right click Tree maintenance maximum

Consider the contribution of each number to the answer Record an array next Indicates the position of the next occurrence of the point on this position Then the scope of contribution of this point is [i,next[i]-1] Suppose there is no next Namely [i,n]

So we first add the contribution of all the first numbers to the answer to the line segment tree Then scan it from left to right After counting the answers every time i The contribution to the answer is removed And then put next[i] The contribution to the answer increases the segment tree

I'm also drunk with this constant …… Second to last in speed The positive solution must not be like this ……

Besides POI2015 I'm wearing the wrong age ？

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

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/117735.html Link to the original text ：https://javaforall.cn