#C241012B. 序列
标签（Label）
- 笛卡尔树
网址（Website）
题解（Solution）
关于笛卡尔树的性质：
- 类似堆的性质，如果是小根堆，子节点的权值一定比父节点大；
- 左儿子节点的位置一定在左边，右儿子在右边；
- 单调栈建树后，根节点位置为 $\verb!st[1]!$ 。
可以拿来干什么呢？
在 $O(n)$ 时间内处理有关点权大小的问题。
例题：滑动窗口（可以用单调栈做）
这道题其实是一个道理，建树后稍微维护一下就好了。
出题者题解
算法分析
由于答案有可二分性，直接获得 $O(nm \log n)$ 做法。
下面是正解：
考虑每次建出小根笛卡尔树，并且在笛卡尔树上 $dp$。
我们对于每个节点，维护子树内 $a_i$ 最大值 $mx$，区间长度 $sz$，最长合法子段长度 $len$。
假设 $u$ 的两个儿子为 $lc, rc$，那么考虑合并 $lc, rc$ 的信息来得到 $u$ 的信息。
$mx, sz$ 的合并是显然的。考虑 $len$ 的合并，首先，假如合法子段不经过 $u$，那么就是 $\text{len}u \leftarrow \max(\text{len}{lc}, \text{len}{rc})$。 假设存在 $u \in [l, r]$ 使得 $[l, r]$ 是合法子段，那么假设 $\max{i \in [l, u-1]}{a_i} \geq \max_{i \in [u+1, r]}{a_i}$，此时我们可以发现，如果 $l > u - sz_{lc} \land r > u$，那么 $[l-1, r-1]$ 也是合法的。
那么就可以知道，我们可以认为跨越 $u$ 的合法子段要么一个端点是 $u$，要么一个端点是 $u - sz_{lc}$ 或 $u + sz_{rc}$。
这里可以发现，假如 $[l, u]$ 是合法子段且 $l > u - sz_{lc}$，那么 $[l-1, u-1]$ 也是合法子段，所以说一个端点是 $u$ 且另一个端点不是 $u - sz_{lc}$ 或 $u + sz_{rc}$ 的情况一定不优于 $\max(\text{len}{lc}, \text{len}{rc})$。
那么我们只需要考虑一个端点在 $u - sz_{lc}$ 或 $u + sz_{rc}$，并且过 $u$ 的情况了（也就是说，我们只需要考虑至少把一颗子树完全包含的情况)，这个转移是显然的。
复杂度 $O(nm)$。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 1012345;
bool ST;
int a[N],b[N],c[N];
int n,m;
int mx[N], f[N], siz[N];
int ch[N][2];
inline void dfs(int x){
siz[x] = 1, mx[x] = a[x];
f[x] = a[x] > 0;
for(auto i:{0, 1}){
int y = ch[x][i];
if(y){
dfs(y);
siz[x] += siz[y];
mx[x] = max(mx[x], mx[y]);
f[x] = max(f[x], f[y]);
if(mx[y] + a[x] > siz[y]+1){//如果满足条件
f[x] = max(f[x], mx[y] + a[x] - 1);
}else f[x] = max(f[x], a[x]*2-1);
}
}f[x] = min(f[x], siz[x]);
}
int st[N],tp;
inline void solve(){
n = rd(), m = rd();For(i,1,n) a[i] = rd();
For(id,0,m){
if(id){
int k = rd();
while(k--) swap(a[rd()], a[rd()]);
}
tp = 0;
For(i,1,n){
ch[i][0] = ch[i][1] = 0;
while(tp && a[st[tp]] > a[i]) ch[i][0] = st[tp--];
if(tp) ch[st[tp]][1] = i;
st[++tp] = i;
}
dfs(st[1]);
printf("%d\n",f[st[1]]);
}
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
// freopen("ex_sequence1.in","r",stdin);
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
int T = 1, Tim = clock();
while(T--) solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
