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;
}
推荐阅读
-
2015-2016 Petrozavodsk Winter Training Camp, SPb SU + SPb AU Contest Greedy Game
-
[Gym] - 100886K 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest K - Toll Roads
-
Gym - 100886I 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest I - Archaeological Res
-
Gym - 100886B 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest B - Game on Bipartite
-
2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest(Gym 100962)
-
Gym - 100886F 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest F - Empty Vessels
-
2015-2016 Petrozavodsk Winter Training Camp, Nizhny Novgorod SU Contest (5/9)
-
题解:2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest