欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest(Gym 100962)

程序员文章站 2022-05-22 10:49:55
...

2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest(Gym 100962)

I

题意:给一个序列,选出一个子序列,满足a[l] == a[r]且a[l] >= a[i] (l <= i <= r),求这样的子序列的最大长度。
题解
询问离线,按右端点排序。
维护一个单调栈,元素单调递减,对栈内每个元素i开一个vector,储存数值为i的元素出现的位置,可以证明这个单调栈内每个元素对应的位置的出现范围是递增的。维护线段树 T1、T2表示栈外、栈内的情况。T1上的i位置表示以i为询问左端点,出栈位置的最大贡献。T2上的i位置表示,栈中第i个元素的最大贡献。
插入操作:遍历到元素a[i],先从栈中弹出比它小的元素,当一个元素出栈,对于它的每一个出现位置,用(maxpos - pos)更新T1上[1, pos]区间。(表示以pos为左端点,以maxpos为右端点,maxpos指这个元素出现的最大位置)。弹栈结束后,插入a[i],用(pos - minpos)更新T2上stop位置。
查询操作:栈外查询T1的L位置;栈内,先二分出第一个最小出现位置比L大的位置(先前说过这些位置的区间是递增的因此可以二分),然后再T2上查询后缀。最后处理栈内临界元素,即它的一部分出现位置比L小,一部分比L大,再次二分即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=5e5+10;
struct TREE{
	int v,fv,fg;	
}tree[2][N*4];
struct NODE{
	int x,y,id;
	bool operator <(const NODE & other)
	const { return y<other.y;}
}node[N];
int que[N],a[N],stop,n,ans[N];
vector<int>vec[N];
void pushdown(int opt,int x)
{
	int i;
	if(tree[opt][x].fg)
	{
		for(i=x*2;i<=x*2+1;i++)
		{
			tree[opt][i].v=max(tree[opt][i].v,tree[opt][x].fv);
			tree[opt][i].fv=max(tree[opt][i].fv,tree[opt][x].fv);
			tree[opt][i].fg=1;
		}
		tree[opt][x].fg=0;
	}
}
void pushup(int opt,int x)
{
	tree[opt][x].v=max(tree[opt][x*2].v,tree[opt][x*2+1].v);
}
void insert(int opt,int x,int l,int r,int ll,int rr,int v)
{
	if(rr<ll||r<ll||rr<l)
		return; 
	if(ll<=l&&r<=rr)
	{
		if(v<0)
		{
			tree[opt][x].v=0;
			tree[opt][x].fv=0;
		}
		else
		{
			tree[opt][x].v=max(tree[opt][x].v,v);
			tree[opt][x].fv=max(tree[opt][x].fv,v);
		}
		tree[opt][x].fg=1; 
		return;
	}
	int mid=(l+r)>>1;
	pushdown(opt,x);
	insert(opt,x*2,l,mid,ll,rr,v);
	insert(opt,x*2+1,mid+1,r,ll,rr,v);
	pushup(opt,x); 
}
int query(int opt,int x,int l,int r,int ll,int rr)
{
	if(rr<ll||r<ll||rr<l)
		return 0;
	if(ll<=l&&r<=rr)
		return tree[opt][x].v;
	int mid=(l+r)>>1;
	pushdown(opt,x);
	return max(query(opt,x*2,l,mid,ll,rr),query(opt,x*2+1,mid+1,r,ll,rr)); 
}
void del()
{
	int lenth,maxa,i;
	lenth=vec[stop].size();
	maxa=vec[stop][lenth-1]; 
	for(i=0;i<lenth;i++)
		insert(0,1,1,n,1,vec[stop][i],maxa-vec[stop][i]);
	insert(1,1,1,n,stop,stop,-1);
	vec[stop].clear();
	stop--;
}
void ins(int x,int id)
{
	if(que[stop]!=x)
		que[++stop]=x;
	vec[stop].push_back(id); 
	insert(1,1,1,n,stop,stop,id-vec[stop][0]);
} 
int get_pos1(int x)
{
	int l,r,mid;
	l=1;
	r=stop+1;
	while(r-l>1)
	{
		mid=(l+r)>>1;
		if(vec[mid][0]<=x)
			l=mid;
		else
			r=mid;
	}
	return l;
}
int get_pos2(int pos1,int x)
{
	int l,r,mid;
	l=-1;
	r=vec[pos1].size()-1;
	while(r-l>1)
	{
		mid=(l+r)>>1;
		if(vec[pos1][mid]<x)
			l=mid;
		else
			r=mid;
	}	
	return r;
} 
int solve(int x)
{
	int nans,pos1,pos2,lenth;
	nans=0;
	nans=max(nans,query(0,1,1,n,x,n));
	pos1=get_pos1(x); 
	nans=max(nans,query(1,1,1,n,pos1+1,stop));
	lenth=vec[pos1].size()-1;
	pos2=get_pos2(pos1,x);
	nans=max(nans,vec[pos1][lenth]-vec[pos1][pos2]);
	return nans; 
}
int main()
{
	int m,i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&node[i].x,&node[i].y);
		node[i].id=i; 
	} 
	sort(node+1,node+m+1);
	stop=0;
	j=0;
	for(i=1;i<=n;i++)
	{
		while(stop>0&&que[stop]<a[i])
			del();
		ins(a[i],i);
		while(j+1<=m&&node[j+1].y<=i)
		{
			j++;
			ans[node[j].id]=solve(node[j].x);
		}
	}
	for(i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
 } 
相关标签: 训练赛

上一篇: 1179:奖学金

下一篇: hdu 1179