题目大意

给你一个排列以及若干区间，对于每个区间，问包含它的最小的优美序列的区间。

所谓优美序列，即将权值排序后能够得到连续的排列。

---

思考历程

优美序列显然满足这个条件：\(mx-mn=r-l\)

想了半天没有想出正解，于是开始打水法。

首先\(n,m\leq 1000\)的时候可以暴力地求出每个区间是否是优美区间，然后更新它们子区间的答案就行了。

建两棵线段树（其实如果是\(ST\)表会更好），一个按照下标建，维护区间最大最小值；

一个按照权值建，维护权值区间的最左最右下标。

离线，将所有询问丢进一个堆里，每次取出最小的区间来搞。找出最大最小值，再找出最大最小值之间的最左最右下标，将区间扩展。

如果现在这个区间之前处理过，那就直接用并查集将两者的答案合并在一起。可以在长度为第一关键字的时候以左端点为第二关键字，那么如果这个区间被处理过，它肯定是上一个区间。

扩展后的区间重新丢到堆里。如果不能扩展，就说明找到了答案。

这个方法可以得到很优秀的\(76\)分。

---

水法

不得不提YYT大爷的水法。

题目说是随机排列（但由于是在题面上说而不是数据上，这多少有些不可信。），按照这样的性质，可得优美序列不会太多。

于是就将所有的优美序列求出来。

枚举一个左端点\(l\)，从区间\([l,l+1]\)开始，利用上面的水法进行扩展。如果扩展后左端点不为\(l\)则退出（因为已经算过了）。这样就可以处理出所有的优美序列。

后面就是一个二维偏序的问题了。

---

正解

题解的做法是分治。看起来好有道理，实际上……根本不知道怎么做。（题解过于简略）

题解说的时间复杂度是\(O(n\lg^2 n)\)的。

WHH在分治的基础上想到了一个\(O(n\lg^3 n)\)的做法。就在这里随便介绍一下。

同样分治。根据\(mx\)和\(mn\)分别在左边或右边分成四种情况来处理，还要用主席树来搞……

有个绝对的正解是析合树，正在学习……（WMY会了%%%）

这题就是析合树的模板啊……

晚上的时候我在床上思考，想出了一个分块的做法。

枚举右端点\(r\)，左端点要满足\(l+mx_l-mn_l=r\)。设式子左边的值为\(s_l\)。

之前见过类似的题目。可以用两个单调栈分别维护\(mx_l\)和\(mn_l\)，然后维护\(s_l\)。

由于我要使得等式的两边相等，所以要打分块。

对于每个分块开个桶就好了。

对于一个询问\([l,r]\)，从右端点开始向后枚举，找到第一个\(i\)满足存在一个区间\([j,i]\)包含\([l,r]\)。那么这个区间就是答案（多个右端点相同的区间取最小的）。

为什么呢？如果说存在\(i<i'\)，有区间\([j',i']\)也包含\([l,r]\)且长度小于\([j,i]\)，那么两个区间的交\([j',i]\)必然也是个优美序列，所以答案应该是\([j',i]\)这个区间。

两个优美序列的交必定也是优美序列，证明就不再赘述了。

然后就可以\(O(n\sqrt n)\)卡过这道题。

后来发现了一个令人悲伤的真相：实际上，\(mx_l-mn_l\geq r-l\)

原因就不用说了吧……

在线段树上维护\(s_l\)的最小值就好了，寻找的时候在线段树上二分，找到满足不等式左右两边相等的\(l\)。

时间复杂度\(O(n \lg n)\)，优化了好多……

我觉得这才是真正意义上的正解。分治做法还不知道是什么东西，析合树又是新的知识点，而这个方法应该是适于完全没有学过析合树的，用来锻炼思维的方法……

---

代码

只打了分块做法……

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 100010#define maxK 400inline int input(){    char ch=getchar();    while (ch<'0' || '9'
        
         a[i]){            change(smn[tmn-1]+1,smn[tmn],a[smn[tmn]]-a[i]);            tmn--;        }        smn[++tmn]=i;        while (tmx && a[smx[tmx]]
         
          =mnl){ int t=*h; pop_heap(h,h+nh--,cmph); for (;k>=1;--k) if (hav[k][i-tag[k]]==bz[k] && lef[k][i-tag[k]]<=q[t].l) break; if (pushdown(k)) rebuild(k); for (int ii=min(q[t].l,end[k]);ii>end[k-1];--ii) if (s[ii]==i){ ansl[q[t].num]=ii; ansr[q[t].num]=i; break; } } } for (int i=1;i<=m;++i) printf("%d %d\n",ansl[i],ansr[i]); return 0;}
         
        
       
      
     
    

---

总结

很多时候有许多隐藏的不等关系，需要细心地寻找。

然后，一定要学会析合树！