二維差分 為什麼我為OI淚目？因為我菜得離譜...... 引入 一維差分用來O(1)修改區間，配合上一維首碼和就是O(N)的查詢區間和。 差分為首碼和的逆運算。 二維差分同理。 接下來這道題就用二維差分來解決。 \(例題：地毯>>\) 地毯 題目描述 在 \(n\times n\) 的格子上有 \( ...
思路：
首先考慮離線。
設 \(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\) 造成貢獻的點，維護一個 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;
}
