最近怎么这么多 CDQ 分治优化 DP。我 CDQ 还只会模版呢 qwq。另一道 CDQ 分治优化 DP 我是神秘转化 + 树状数组写的，看来还是不能偷懒。
赛时 T1 学艺不精没做出来，导致破防没细想 T2，其实赛时的做法只需要套一个 CDQ 分治优化就过了。
关键观察是只有中位数有贡献。这个东西其实比较好猜，因为如果你直接暴力 DP 就可以直接发现只有中位数的答案是对的，其他都是 \(-\infty\)。
::::info[证明]{open}
考虑 DP 的本质。一个合法的分段方法要满足：
- 这个段内 \( 的数要 \(<\) 这个段内 \(\ge x\) 的数，反之中位数 \(。
- 这个段内 \(>x\) 的数要 \(<\) 这个段内 \(\le x\) 的数，反之中位数 \(>x\)。
注意到，每个段都需要满足上述两个条件，那么总体上：
- 完整区间 \(\ge x\) 的数要 \(\ge \lceil\frac{n}{2}\rceil\)，反之全局中位数 \(。
- 完整区间 \(\le x\) 的数也要 \(\ge \lceil \frac{n}{2} \rceil\)，反之全局中位数 \(>x\)。
为了使得这两个条件同时满足，那么 \(x=\) 全局中位数。
::::
根据这个，我们就可以直接做了。对于合法区间的判定，上面的证明提到过了。那么，我们可以对这个序列染色，转化为区间存在颜色的大小情况。这里的设计比较巧妙（我赛时的设计没有达到这个水准，被迫拆成了两次染色）：
-
设 \(a_i=x\) 的为 \(0\)，\(>x\) 为 \(+1\)，反之 \( 为 \(-1\)。
-
为了统一规则（防止染色多次），我们需要特殊处理 \(a_i=x\) 的个数，维护这个东西的区间和 \(c\)。然后为了维护大小关系，我们维护权值区间和 \(s\)。则一个区间合法显然：
- 满足段内 \( 的数要 \(<\) 段内 \(\ge x\) 的数，即 \(\sum_{i=l}^r[a_ix]< c[l,r]\)，稍微转化一下就是 \(c[l,r]+s[l,r]> 0\)。
- 满足段内 \(>x\) 的数要 \(<\) 段内 \(\le x\) 的数，即 \(\sum_{i=l}^r[a_i>x]-[a_i，也稍微转化一下就是 \(c[l,r]-s[l,r]> 0\)。
-
然后我们考虑转为前缀和。注意还有区间长度的限制
- \(c_r-c_{l-1}+s_{r}-s_{l-1}> 0\iff s_r+c_r>s_{l-1}+c_{l-1}\)。（不知道为什么这里推出来和题解不一样 qwq）
- \(c_r-c_{l-1}-s_r+s_{l-1}>0\iff c_r-s_r>c_{l-1}-s_{l-1}\)。
那么我们这个就可以直接 DP 去做了，设 \(f_i\) 为前 \(i\) 个的最多分段：
那么这个过程显然是一个三维偏序的过程（\(c_r-s_{r}>c_{l-1}-s_{l-1}\land c_r+s_r>c_{l-1}+s_{l+1}\land r>l-1\)），我们只需要按照这个东西实现 CDQ 分治即可。
::::success[Code]{open}
#define FileIO
#include
using namespace std;
#define ll long long
#define fi first
#define se second
#define il inline
bool stMem; double stT=clock();
const int N=2e5+10;
const ll P=998244353;
il ll qp(ll a,ll b=P-2){ll res=1;for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;return res;
}
// ---------------------------------------------------- //
int n,a[N],s[N],c[N],d[N],x,f[N];
int sub[N], add[N]; // l le, ri;
il bool cmp_by_sub(int i,int j){ return sub[i]>1;cdq_solve(l,mid);le.clear(), ri.clear(); // 这两个数组维护左右两侧合并值顺序 for(int i=l;i<=mid;++i) le.push_back(i);for(int i=mid+1;i<=r;++i) ri.push_back(i);sort(le.begin(),le.end(),cmp_by_sub);sort(ri.begin(),ri.end(),cmp_by_sub);int lp=0; vector> upd;for(auto rp:ri){// 枚举 sub 维合法贡献while(lp<(int)le.size()&&sub[le[lp]]-1e9) t[add_t].update(add_p,f[le[lp]]), upd.push_back({add_t,add_p}); ++lp;}// 统计 add 维合法贡献int qry_t=!(add[rp]%2), qry_p=z(add[rp]-1); // 注意奇数长度int max_dp=t[qry_t].query(qry_p);f[rp]=max(f[rp],max_dp+1);}for(auto v:upd) t[v.fi].clear(v.se);cdq_solve(mid+1,r);
}
// ---------------------------------------------------- //
il void solve(){cin>>n;for(int i=1;i<=n;++i) cin>>a[i], d[i]=a[i];sort(d+1,d+n+1); x=d[n/2];for(int i=1;i<=n;++i)c[i]=c[i-1]+(a[i]==x),s[i]=s[i-1]+(a[i]>x?+1:(a[i]>T;while(T--) solve();cerr<<"\n";cerr<<"[Info] End Of Running. \n";cerr<<" Time Used : "<<(clock()-stT)/CLOCKS_PER_SEC*1000.00<<" ms\n";cerr<<" Memory Used : "<<(&stMem-&edMem)/1048576.00<<" Mib\n";return 0;
}::::
https://www.luogu.com.cn/article/3g2gwcan