4149: [AMPPZ2014]Global Warming
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 112 Solved: 38
[Submit][Status][Discuss]
Description
给定一个序列a[1],a[2],...,a[n]。请从中选出一段连续子序列，使得该区间最小值唯一、最大值也唯一。
输出选出的子序列的长度的最大值以及取到最大值时左端点的最小值。
Input
第一行包含一个正整数n(1<=n<=500000)，表示序列长度。
第二行包含n个正整数，依次表示a[1],a[2],...,a[n](-10^9<=a[i]<=10^9)。
Output
包含一行两个整数l,k，其中l表示选出的子序列的长度的最大值，k表示取到最大值时左端点的最小值。
Sample Input
10
8 3 2 5 2 3 4 6 3 6
8 3 2 5 2 3 4 6 3 6
Sample Output
6 4
HINT
选出的子序列为5,2,3,4,6,3，只有唯一的最小值2和唯一的最大值6。
Source
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
struct data{int x,s,y,next;} g[N],h[N];
struct node{int l,r;} x[N],y[N];
int n,m,a[N],q[N],t,ans,Pos,j,cnth,cntg,v[N<<2],headh[N],headg[N];
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Inserth(int x,int s,int y){h[++cnth] = (data){x,s,y,headh[x]};headh[x] = cnth;}
void Insertg(int x,int s,int y){g[++cntg] = (data){x,s,y,headg[x]};headg[x] = cntg;}
void Ins(int x,int val){
int l = 1,r = n,pos = 1;
while (1){
v[pos] = max(v[pos],val);
if (l==r) return;
int mid = (l+r)>>1;
if (x<=mid){r = mid;pos = pos<<1;}
else {l = mid+1;pos = pos<<1|1;}
}
}
int Query(int pos,int l,int r,int x,int y){
if (l==x && r==y){return v[pos];}
int mid = (x+y)>>1;
if (r<=mid) return Query(pos<<1,l,r,x,mid);
else if (l>mid) return Query(pos<<1|1,l,r,mid+1,y);
else return max(Query(pos<<1,l,mid,x,mid),Query(pos<<1|1,mid+1,r,mid+1,y));
}
void work(){
for (int i=1;i<=n;i++) Insertg(x[i].l,i,x[i].r),Inserth(y[i].l,i,y[i].r);
for (int x=1;x<=n;x++){
for (int k=headh[x];k;k=h[k].next) Ins(h[k].s,h[k].y);
for (int k=headg[x];k;k=g[k].next){
j = Query(1,x,g[k].y,1,n);
if (j<g[k].s) continue;
if ((t=min(j,g[k].y)-x+1)>ans){ans = t;Pos = x;}
else if (t==ans){Pos = min(Pos,x);}
}
}
}
int main(){
n = read();
for (int i=1;i<=n;i++) a[i] = read();
q[0] = 0;t = 0;
for (int i=1;i<=n;i++){while (t && a[q[t]]>a[i]) t--;x[i].l = q[t]+1;q[++t] = i;}
q[0] = n+1;t = 0;
for (int i=n;i;i--){while (t && a[q[t]]>a[i]) t--;x[i].r = q[t]-1;q[++t] = i;}
q[0] = 0;t = 0;
for (int i=1;i<=n;i++){while (t && a[q[t]]<a[i]) t--;y[i].l = q[t]+1;q[++t] = i;}
q[0] = n+1;t = 0;
for (int i=n;i;i--){while (t && a[q[t]]<a[i]) t--;y[i].r = q[t]-1;q[++t] = i;}
work();
cntg = cnth = 0;memset(v,0,sizeof(v));
for (int i=1;i<=n;i++) headh[i] = headg[i] = 0;
for (int i=1;i<=n;i++) swap(x[i],y[i]);
work();
printf("%d %d",ans,Pos);
}
评论 (0)
