[题解] [CERC2017]Intrinsic Interval
¶凉笙
·
·
题解
[题解] [CERC2017]Intrinsic Interval
点此看题
如果你做过类似的一类模型题，你确实会认为这道思维题，其实就是一道套路题。
建模
见到此类给你一些区间，求解合法区间个数或者是什么的问题，可以往这里想。
-
把询问区间按照右端点排序。
-
从左到右依次枚举右端点，用数据结构来维护左端点。
当然，最重要的是第二步，第一步是离线思想，第二步是统计思想。
通常，在并非特别复杂的情况下，第二步的数据结构采用线段树即可，但具体的不是用什么，而是怎么维护。
那么就需要发现题目性质：本征区间为极差减去区间长度等于 -1 的且包含询问区间的一个区间，或者说，满足 max-min=r-l，注意 r-l 并不是区间长度。
发现这个关键性质，就可以考虑线段树维护这个东西了。
max-min-(r-l)\geq0
当取等时，这就是一个合法的左端点，因此可以维护这个东西的最小值来判断。
这个模型关键的是第三步：
- 考虑加入当前右端点对已有的左端点的影响。
通俗的讲，加入当前右端点 r 后，之前所有的 [l,r-1] 的区间都会扩展一个单位，这需要我们在线段树上更新左端点的信息，也就是更新 max,min,(r-l) 这三个信息。
对于 $max,min$ 的维护，设 $l_1,l_2$ 依次为 $r$ **从右往左数第一个比 $a_r$ 大和比 $a_r$ 小的位置**，对于这类问题，可以用单调栈维护（比较常见）。
那么处于 $[l_1+1,r]$ 的这部分左端点，它们到右端点 $r$ 的最大值都会取到 $a_r$，可以在维护单调栈的时候进行撤销，然后再把 $a_r$ 的值更新进去。
具体来说，对于单调栈（不妨设单调递减）中相邻的两个点 $u,v$，$[u+1,v-1]$ 这一段的值均 $\leq a_v$ .
在维护单调栈单调性的同时，顺便维护一下撤销的东西即可。
最后就是查询，有一个结论是：
**如果当前的 $r$ 对应于一个合法的最大的 $l$，那么这个 $[l,r]$ 就是最小的区间。**
证明自己反证法证一下。
而这个题也可以有一个变式：
如果不是排列了怎么办？
借用 HH的项链 的思想，**区间数颜色的关键在于在最后一次出现的位置统计答案**，因此记录 $last$ 更换一下 $r-l$ 的维护即可。
[Continuous Intervals](https://codeforces.com/gym/102222/problem/L)，可以说是加强版，需要区间数颜色并且维护合法区间的个数。
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
}
return fl?-x:x;
}
#include <vector>
#include <set>
const int maxn = 1e5 + 10;
#define Pair pair<int,int>
#define mp make_pair
namespace Tree{
struct tree{
int l,r;
int mn,tag;
}t[maxn<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
inline void pushup(int p){
t[p].mn=min(t[ls].mn,t[rs].mn);
}
inline void pushdown(int p){
if(!t[p].tag)return ;
t[ls].mn+=t[p].tag;t[rs].mn+=t[p].tag;
t[ls].tag+=t[p].tag;t[rs].tag+=t[p].tag;
t[p].tag=0;
}
void build(int p,int l,int r){
t[p].l=l;t[p].r=r;
if(l==r)return t[p].mn=l,void();
build(ls,l,mid);build(rs,mid+1,r);
pushup(p);
}
void update(int p,int x,int y,int val){
int l=t[p].l,r=t[p].r;
if(x>y)return ;
if(x<=l && r<=y){
t[p].mn+=val;t[p].tag+=val;return ;
}
pushdown(p);
if(x<=mid)update(ls,x,y,val);
if(y>mid)update(rs,x,y,val);
pushup(p);
}
int query(int p,int x,int y){
int l=t[p].l,r=t[p].r;
if(t[p].mn>0)return -1;
if(l==r)return l;
pushdown(p);
if(y>mid && !t[rs].mn){
int res=query(rs,x,y);
if(res!=-1)return res;
}
if(x<=mid && !t[ls].mn)return query(ls,x,y);
return -1;
}
}using namespace Tree;
int n,m,a[maxn];
int stk1[maxn],stk2[maxn],top1,top2;
vector<Pair> pos[maxn];
multiset<Pair> s;
Pair ans[maxn];
#define read() read<int>()
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
m=read();
for(int i=1;i<=m;i++){
int l=read(),r=read();
pos[r].emplace_back(l,i);
}
build(1,1,n);
for(int i=1;i<=n;i++){
int x,y;
while(top1 && a[stk1[top1]]<a[i]){
y=stk1[top1];top1--;
x=stk1[top1]+1;
update(1,x,y,-a[y]);
}
x=stk1[top1]+1;y=i;
update(1,x,y,a[y]);
stk1[++top1]=i;
while(top2 && a[stk2[top2]]>a[i]){
y=stk2[top2];top2--;
x=stk2[top2]+1;
update(1,x,y,a[y]);
}
x=stk2[top2]+1;y=i;
update(1,x,y,-a[y]);
stk2[++top2]=i;
update(1,1,n,-1);
for(auto x:pos[i])s.insert(x);
while(s.size()){
auto it=s.end();it--;
int l=it->first,res=query(1,1,l);
if(res==-1)break;
s.erase(it);
ans[it->second].first=res;
ans[it->second].second=i;
}
}
for(int i=1;i<=m;i++)printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}
```