讲解 P8037 [COCI2015-2016#7] Prokletnik。

使用扫描线，单调栈，线段树等算法。

思路：

首先考虑离线。

设 \(Min-nxt_i\) 表示下一个小于 \(a_i\) 处的位置，\(Max-nxt_i\) 表示下一个大于 \(a_i\) 处的位置。

那么 \([l,r]\) 是魔法区间当且仅当：

• \(r\) 是 \([l,r]\) 的最大值，且 \(r < Min - nxt_l\)。

• \(r\) 是 \([l,r]\) 的最小值，且 \(r < Max - nxt_l\)。

再令 \(Min-pre_i\) 表示上一个小于 \(a_i\) 处的位置，\(Max-pre_i\) 表示上一个大于 \(a_i\) 处的位置。

那么我们可以对于每个 \(r\)，求出对应的 \(l\) 的氛围：

• 若 \(r\) 是 \([l,r]\) 的最大值，则 \(l \in [Max-pre_r+1,r]\)。

• 若 \(r\) 是 \([l,r]\) 的最小值，则 \(l \in [Min-pre_r+1,r]\)。

则可以在扫描线扫到 \(r\) 时，对上述两个区间更新答案；注意到对于 \(l\) 的答案是 \(r-l+1\)，那么对于区间 \([a,b]\)，其的右端点若都是 \(r\)，要使得贡献最大，应该选择 \([a,r]\) 区间，但是有些点是无法对 \(r\) 造成贡献的（对于这类点的处理见下文），于是我们需要找到 \([a,b]\) 内最小的能对 \(r\) 造成贡献的点，维护一个 <code>set 二分即可，需要支持删除。

但是我们需要满足 \(r < Min-nxt_l\) 或 \(r<Max-nxt_l\)，那么可以在 \(Min-nxt_l\) 和 \(Max-nxt_l\) 处将 \(l\) 此处赋值为无穷小即可。

注意到就算 \(l\) 处被赋值为无穷小，即无法对 \(r\) 与 \(r\) 后面的数造成贡献，但是其本身也有贡献，需要用另外一个线段树维护无法造成新贡献的点的区间最大贡献。

时间复杂度为 \(O((N+Q) \log^2 N)\)。

完整代码：

#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef int ll;

bool Begin;

const ll N=5e5+10;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

ll n,q,l,r,top;

ll a[N],ans[N],stk[N],Mi_pre[N],Ma_pre[N],Mi_nxt[N],Ma_nxt[N];

vector<ll> F[N],G[N];

vector<pi> Q[N];

class St{

public:

ll X[N<<2];

void pushup(ll k){

X[k]=max(X[k<<1],X[k<<1|1]);

}

void build(ll k,ll l,ll r){

X[k]=0;

if(l==r)

return ;

ll mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

}

void add(ll k,ll l,ll r,ll i,ll v){

if(l==i&&i==r){

X[k]=v;

return ;

}

ll mid=(l+r)>>1;

if(i<=mid)

add(k<<1,l,mid,i,v);

else

add(k<<1|1,mid+1,r,i,v);

pushup(k);

}

ll query(ll k,ll L,ll R,ll l,ll r){

if(L==l&&r==R)

return X[k];

ll mid=(L+R)>>1;

if(r<=mid)

return query(k<<1,L,mid,l,r);

else if(l>mid)

return query(k<<1|1,mid+1,R,l,r);

else

return max(query(k<<1,L,mid,l,mid),query(k<<1|1,mid+1,R,mid+1,r));

}

}TT;

class Tree{

public:

set<ll> S;

struct Node{

ll l,r;

ll Max;

ll tag;

}X[N<<2];

ll get(ll x){

return (*S.lower_bound(x));

}

void add(ll k,ll v){

ll t=get(X[k].l);

if(t>X[k].r)

X[k].Max=-1e9;

else

X[k].Max=v-t+1;

X[k].tag=v;

}

void push_down(ll k){

if(X[k].tag){

add(k<<1,X[k].tag);

add(k<<1|1,X[k].tag);

X[k].tag=0;

}

}

void pushup(ll k){

X[k].Max=max(X[k<<1].Max,X[k<<1|1].Max);

}

void build(ll k,ll l,ll r){

X[k].l=l,X[k].r=r;

X[k].tag=X[k].Max=0;

if(l==r){

S.insert(l);

return ;

}

ll mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

}

void add(ll k,ll i,ll v){

if(X[k].l==i&&i==X[k].r){

TT.add(1,1,n,i,X[k].Max);

S.erase(i);

X[k].Max=v;

return ;

}

push_down(k);

ll mid=(X[k].l+X[k].r)>>1;

if(i<=mid)

add(k<<1,i,v);

else

add(k<<1|1,i,v);

pushup(k);

}

void update(ll k,ll l,ll r,ll v){

if(X[k].l==l&&r==X[k].r){

//cerr<<"1:"<<l<<' '<<r<<' '<<v<<'\n';

add(k,v);

//cerr<<"2:"<<l<<' '<<r<<' '<<X[k].Max<<'\n';

return ;

}

push_down(k);

ll mid=(X[k].l+X[k].r)>>1;

if(r<=mid)

update(k<<1,l,r,v);

else if(l>mid)

update(k<<1|1,l,r,v);

else{

update(k<<1,l,mid,v);

update(k<<1|1,mid+1,r,v);

}

pushup(k);

//cerr<<"3:"<<X[k].l<<' '<<X[k].r<<' '<<X[k].Max<<'\n';

}

ll query(ll k,ll l,ll r){

//cerr<<"4:"<<X[k].l<<' '<<X[k].r<<' '<<X[k].Max<<'\n';

if(X[k].l==l&&r==X[k].r)

return X[k].Max;

push_down(k);

ll mid=(X[k].l+X[k].r)>>1;

if(r<=mid)

return query(k<<1,l,r);

else if(l>mid)

return query(k<<1|1,l,r);

else

return max(query(k<<1,l,mid),query(k<<1|1,mid+1,r));

}

}T;

bool End;

int main(){

n=read();

for(int i=1;i<=n;i++)

a[i]=read();

q=read();

for(int i=1;i<=q;i++){

l=read(),r=read();

Q[r].push_back({l,i});

}

for(int i=1;i<=n;i++){

while(top&&a[stk[top]]>a[i]){

Mi_nxt[stk[top]]=i;

top--;

}

stk[++top]=i;

}

top=0;

for(int i=1;i<=n;i++){

while(top&&a[stk[top]]<a[i]){

Ma_nxt[stk[top]]=i;

top--;

}

stk[++top]=i;

}

top=0;

for(int i=n;i>=1;i--){

while(top&&a[stk[top]]>a[i]){

Mi_pre[stk[top]]=i;

top--;

}

stk[++top]=i;

}

top=0;

for(int i=n;i>=1;i--){

while(top&&a[stk[top]]<a[i]){

Ma_pre[stk[top]]=i;

top--;

}

stk[++top]=i;

}

for(int i=1;i<=n;i++){

F[Mi_nxt[i]].push_back(i);

G[Ma_nxt[i]].push_back(i);

}

T.build(1,1,n);

TT.build(1,1,n);

for(int i=1;i<=n;i++){

for(auto v:F[i])

T.add(1,v,-1e9);

T.update(1,Ma_pre[i]+1,i,i);

for(auto t:Q[i])

ans[t.se]=max({ans[t.se],T.query(1,t.fi,i),TT.query(1,1,n,t.fi,i)});

}

T.build(1,1,n);

TT.build(1,1,n);

for(int i=1;i<=n;i++){

for(auto v:G[i])

T.add(1,v,-1e9);

T.update(1,Mi_pre[i]+1,i,i);

for(auto t:Q[i])

ans[t.se]=max({ans[t.se],T.query(1,t.fi,i),TT.query(1,1,n,t.fi,i)});

}

for(int i=1;i<=q;i++){

write(ans[i]);

putchar('\n');

}

return 0;

}