题意
定义一个区间 $l,r$ 为好的当且仅当最小值为 $a_l$ 且最大值为 $a_r$ 或 最大值为 $a_l$ 且最小值为 $a_r$。
我们先考虑最小值为 $a_l$ 且最大值为 $a_r$ 的,另一个我们翻转过来在搞一遍就好了。
先考虑将询问离线按 $r$ 排序,容易发现,对于每个右端点 $r$ 对应的合法左端点是一段单调递增的数,若我们将 $r$ 从小到大跑,最后一次给左端点 $l$ 赋值的右端点 $r$ 一定是最优的,这很显然,因为固定了 $l$,$r$ 越大,长度越大。
然后由于对应的合法左端点是一段单调递增的数,可以用单调栈存,考虑开两个线段树分别维护单调栈里的和不在单调栈里的,这里注意,由于 $r$ 前面可能有比 $a_r$ 大的数,所以要二分判单调栈内第一个合法位置在哪。
由于每个数最多进栈出栈一次,所以时间是可以保证的,线段树则需要能满足单点覆盖和区间加,区间求最大值。
最后求答案,直接二分栈里第一个下标大于等于 $q_l$ 的数,同时求不在单调栈里的 $q_l$ 到 $q_r$ 的最大值就行。
然后在反着做一遍就完了,代码有部分注释方便理解。
code
#include<bits/stdc++.h>
#define mid ((L+R)>>1)
#define ls (p<<1)
#define rs ((p<<1)+1)
using namespace std;
namespace IO
{
template<typename T>
void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
template<typename T,typename... Args>
void read(T &_x,Args&...others){Read(_x);Read(others...);}
const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
#define pc(x) buf[plen++]=x
#define flush(); fwrite(buf,1,plen,stdout),plen=0;
template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 1e6+10;
int n,q,a[N],lg[N],st[N][22],ans[N],fg[N<<2],bj[N<<2],cnt,t[N],cnt1,l,r,m1d,sum,o,o1;
struct w
{
int l,r,id;
}b[N];
struct w1
{
int mx;
}c[N<<2][2];
inline bool cmp(w x,w y){return x.r < y.r;}
void build(int p,int L,int R,int id)
{
fg[p] = bj[p] = 0;
if(L == R)
{
if(id == 0) c[p][id].mx = -l+1;//由于是求区间长度,提前减去左端点就好了
return;
}
build(ls,L,mid,id),build(rs,mid+1,R,id);
c[p][id].mx = max(c[ls][id].mx,c[rs][id].mx);
}
inline void push_up1(int p,int id,int L,int R)
{
if(id == 1) c[ls][id].mx = -t[L]+1,c[rs][id].mx = -t[R]+1;
else c[ls][id].mx = -L+1,c[rs][id].mx = -R+1;
bj[ls] = bj[rs] = 0;
fg[ls] = fg[rs] = 1;
fg[p] = 0;
}
inline void push_up(int p,int id)
{
c[ls][id].mx += bj[p],c[rs][id].mx += bj[p];
bj[ls] += bj[p],bj[rs] += bj[p];
bj[p] = 0;
}
void change(int p,int l,int r,int k,int id,int L,int R)
{
if(l <= L && R <= r)
{
if(k == -1)
{
if(id == 1) c[p][id].mx = -t[L]+1,bj[p] = 0,fg[p] = 1;//注意这是栈里的数,赋的不一样
else c[p][id].mx = -L+1,bj[p] = 0,fg[p] = 1;//clear
}
else
{
if(id == 1) c[p][id].mx += k,bj[p] += k;
else c[p][id].mx = max(c[p][id].mx,k);
}
return;
}
if(fg[p] && id == 1) push_up1(p,id,L,mid+1);
if(bj[p] && id == 1) push_up(p,id);
if(l <= mid) change(ls,l,r,k,id,L,mid);
if(mid < r) change(rs,l,r,k,id,mid+1,R);
c[p][id].mx = max(c[ls][id].mx,c[rs][id].mx);
}
void query(int p,int l,int r,int id,int L,int R)
{
if(l <= L && R <= r)
{
sum = max(sum,c[p][id].mx);
return;
}
if(fg[p] && id == 1) push_up1(p,id,L,mid+1);
if(bj[p] && id == 1) push_up(p,id);
if(l <= mid) query(ls,l,r,id,L,mid);
if(mid < r) query(rs,l,r,id,mid+1,R);
}
signed main()
{
read(n); build(1,1,n,0),build(1,1,n,1);
for(int i = 2;i <= n;i++) lg[i] = lg[i/2]+1;
for(int i = 1;i <= n;i++) read(a[i]),st[i][0] = a[i];
read(q);
for(int i = 1;i <= q;i++) read(b[i].l),read(b[i].r),b[i].id = i;
sort(b+1,b+1+q,cmp);
for(int i = 1;i <= lg[n];i++)
for(int j = 1;j+(1<<i)-1 <= n;j++)
st[j][i] = max(st[j][i-1],st[j+(1<<(i-1))][i-1]);//st表求出最大值
cnt = 1;
for(int i = 1;i <= n;i++)
{
while(cnt1 && a[t[cnt1]] > a[i])
{
sum = 0; query(1,cnt1,cnt1,1,1,n);
change(1,t[cnt1],t[cnt1],sum,0,1,n);//清空后赋值
cnt1--;
}
t[++cnt1] = i;
int k = lg[i-1];
l = 1,r = cnt1,o = cnt1;
while(l <= r)//二分出合法位置
{
m1d = (l+r)/2;
int k = lg[i-t[m1d]+1];
o1 = max(st[t[m1d]][k],st[i-(1<<k)+1][k]);//如果这一段最大值=a_r,这可行
if(o1 != a[i]) l = m1d+1;
else r = m1d-1,o = m1d;
}
change(1,o,cnt1,-1,1,1,n);//清空,应为要给新的右端点了
change(1,o,cnt1,i,1,1,n);
while(cnt <= q && b[cnt].r == i)//处理右端点为i的询问
{
sum = 0; query(1,b[cnt].l,b[cnt].r,0,1,n);//先求出栈外的
l = 1,r = cnt1,o = 0;
while(l <= r)//二分出合法位置
{
m1d = (l+r)/2;
if(b[cnt].l <= t[m1d]) o = m1d,r = m1d-1;
else l = m1d+1;
}
if(o) query(1,o,cnt1,1,1,n);
ans[b[cnt].id] = sum; cnt++;
}
}
//从大到小
for(int i = 1;i <= lg[n];i++)//下半部分思路同上,就左端点变成最大了
for(int j = 1;j+(1<<i)-1 <= n;j++)
st[j][i] = min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
build(1,1,n,0),build(1,1,n,1); cnt1 = 0,cnt = 1;
for(int i = 1;i <= n;i++)
{
while(cnt1 && a[t[cnt1]] < a[i])
{
sum = 0; query(1,cnt1,cnt1,1,1,n);
change(1,t[cnt1],t[cnt1],sum,0,1,n);//清空后赋值
cnt1--;
}
t[++cnt1] = i;
int k = lg[i-1];
l = 1,r = cnt1,o = cnt1;
while(l <= r)
{
m1d = (l+r)/2;
int k = lg[i-t[m1d]+1];
o1 = min(st[t[m1d]][k],st[i-(1<<k)+1][k]);
if(o1 != a[i]) l = m1d+1;
else r = m1d-1,o = m1d;
}
change(1,o,cnt1,-1,1,1,n);
change(1,o,cnt1,i,1,1,n);
while(cnt <= q && b[cnt].r == i)
{
sum = 0; query(1,b[cnt].l,b[cnt].r,0,1,n);
l = 1,r = cnt1,o = 0;
while(l <= r)
{
m1d = (l+r)/2;
if(b[cnt].l <= t[m1d]) o = m1d,r = m1d-1;
else l = m1d+1;
}
if(o) query(1,o,cnt1,1,1,n);
ans[b[cnt].id] = max(ans[b[cnt].id],sum); cnt++;
}
}
for(int i = 1;i <= q;i++) print(ans[i]),pc('\n');
flush();
return 0;
}
标签:ch,端点,题解,COCI2015,cnt1,plen,2016,最大值,单调
From: https://www.cnblogs.com/kkxacj/p/18657426