这次集训总共做了五六十道dp题(结果集训还没有结束)
在其中有一些很麻烦的题，造成了很大的困难。
这里就专门整理一下这些题。
(要不然你整理简单的干啥？)
这些题可能不按难度顺序排列。
(因为第一道就很恶心)
L题：「THUSC2021 D1T2」白兰地厅的西瓜
问题
问题描述
给出一棵 $n$ 个点的树，每个点都有一个权值 $a_i$。
你可以在树上选一条简单路径，使路径上的最长上升子序列最长，求这个最大长度。
输入格式
输入格式
第一行一个整数 $n$。
第二行 $n$ 个数 $a_i$。
接下来 $n-1$ 行，每行两个数 $u_i$ 与 $v_i$ 。
输出格式
一个整数答案。
样例输入
10
6 4 1 4 5 5 9 8 3 8
8 7
1 5
9 4
10 9
2 3
9 5
3 9
8 9
6 1
样例输出
4
提示
对于 $ 20\% $ 的数据，$1 \le n \le 20$ ；
对于另外 $ 20\% $ 的数据，$u_i=i$，$v_i=i+1$ ；
对于 $ 20\% $ 的数据，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$，$1 \le {u_i,v_i} \le n$。
思路
毒瘤题
一般的最长上升子序列，都是在序列上进行的。
但这个不同，它是在一颗树上求一遍最长上升子序列。
那又怎么做呢？
对于一对点 $s$ 与 $t$，我们显然可以找到他们的 $LCA$。
看到 $LCA$，我们就想到了将他们拆成两条链。
一条是从下往上的链 $s \to LCA$，另一条是从上往下的链 $ LCA \to t$。
那么，我们实际上可以枚举一颗子树。
假设该子树的根为 $u$，我们可以让 $u$ 为最长上升子序列中间的某个点。即从某个点到 $u$,再从 $u$ 到另外的某个点。当然，为了方便考虑，这些点都应该是在 $u$ 这颗子树内。
那么初始状态就有了，设 $f_u$ 表示以 $u$ 为根的子树中，最长上升子序列的长度是多少。
$g_u$ 则与 $f_u$ 恰好相反，表示最长下降子序列。
转移：$f_u = \max(f_u,f_j+1)$，其中：$j \supseteq son_u$ 且 $a_j <a_u$。
$son_u$ 表示 $u$ 的儿子。
最长下降子序列类似。
考虑到合并状态的过程中，我们只需要选择拼接最长上升子序列与最长下降子序列即可，因此可以线段树合并。
线段树中存储值域，剩下的套模板即可。
当然，因为值域过大，我们要先离散化。
代码
#include<iostream>
#include<cstring>
#include<algorithm>
#define pii pair<int,int>
using namespace std;
const int N=2e5+10;
int h[N],e[N],ne[N],idx;
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int w[N];
int w2[N];
int n;
struct tree{
int f,g;
int l,r;
}tr[N<<5];
int num;
void push_up(int u){
tr[u].g=max(tr[tr[u].l].g,tr[tr[u].r].g);
tr[u].f=max(tr[tr[u].l].f,tr[tr[u].r].f);
}
void add(int x,int f,int g,int &u,int l,int r){
if(!u){
u=++num;
}
if(l==r){
tr[u].f=max(tr[u].f,f);
tr[u].g=max(tr[u].g,g);
return;
}
int mid=(l+r)>>1;
if(x<=mid){
add(x,f,g,tr[u].l,l,mid);
}else{
add(x,f,g,tr[u].r,mid+1,r);
}
push_up(u);
}
int root[N];
int ans;
int merge(int a,int b,int l,int r){
// cout<<a<<' '<<b<<endl;
if(!a){
return b;
}
if(!b){
return a;
}
if(l==r){
tr[a].f=max(tr[a].f,tr[b].f);
tr[a].g=max(tr[a].g,tr[b].g);
return a;
}
ans=max(ans,tr[tr[a].l].f+tr[tr[b].r].g);
ans=max(ans,tr[tr[b].l].f+tr[tr[a].r].g);
tr[a].f=max(tr[a].f,tr[b].f);
tr[a].g=max(tr[a].g,tr[b].g);
int mid=(l+r)>>1;
tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
push_up(a);
return a;
}
pii query(int u,int l,int r,int l2,int r2){
// cout<<u<<endl;
if(l>r){
return {0,0};
}
if(l2>=l&&r2<=r){
return {tr[u].f,tr[u].g};
}
pii res={0,0};
int mid=(l2+r2)>>1;
if(l<=mid){
res=query(tr[u].l,l,r,l2,mid);
}
if(r>mid){
pii t=query(tr[u].r,l,r,mid+1,r2);
res.first=max(res.first,t.first);
res.second=max(res.second,t.second);
}
// cout<<res.first<<' '<<res.second<<endl;
return res;
}
int f[N],g[N];
void dfs(int u,int fa){
bool is_leaf=1;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa){
continue;
}
is_leaf=0;
dfs(j,u);
int t1=query(root[j],1,w[u]-1,1,n).first;
int t2=query(root[j],w[u]+1,n,1,n).second;
f[u]=max(f[u],t1+1);
g[u]=max(g[u],t2+1);
int ans1=query(root[u],1,w[u]-1,1,n).first+t2+1;
int ans2=query(root[u],w[u]+1,n,1,n).second+t1+1;
int res=max(ans1,ans2);
ans=max(ans,res);
root[u]=merge(root[u],root[j],1,n);
}
if(is_leaf){
f[u]=1;
g[u]=1;
}
// cout<<u<<' '<<f[u]<<' '<<g[u]<<endl;
add(w[u],f[u],g[u],root[u],1,n);
}
int main(){
memset(h,-1,sizeof h);
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
w2[i]=w[i];
}
sort(w2+1,w2+n+1);
for(int i=1;i<=n;i++){
w[i]=lower_bound(w2+1,w2+n+1,w[i])-w2;
}
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,-1);
// cout<<num<<endl;
cout<<ans;
}
M题：[TJOI2013]最长上升子序列
问题
问题描述
给定一个序列，初始为空。现在我们将 $1$ 到 $n$ 的数字插入到序列中，每次将一个数字插入到一个特定的位置，该位置以及之后的数字往后移动。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？
输入格式
第一行一个整数 $n$，表示我们要将 $1$ 到 $n$ 插入序列中，接下是 $n$ 个数字，第 $k$ 个数字 $x_k$，表示我们将 $k$ 插入到位置 $x_k$（$0 \le x_k \le k-1$，$1 \le k \le n$）
输出格式
$n$ 行，第 $i$ 行表示 $i$ 插入 $x_i$ 位置后序列的最长上升子序列的长度是多少。
样例输入
3
0 0 2
样例输出
1
1
2
提示
对于 $100\%$ 的数据，$n \le 200000$。
思路
又是一道毒瘤题
这道题比上一道题还是要好一点。
考虑朴素做法：
可以发现，对于当前这个数，对它产生贡献的只有在它之前插入的数中，位置比它靠前的数。处理完这个后，我们只需要每一次将位置在它后面的数（这里包括自己）整体平移就好了。
时间复杂度为 $O(n^2)$，显然不可行。
这里有插入与查询最大值两种操作。如果学过平衡树，这道题就可以用 FHQ-Treap 或 splay 来做，时间复杂度为 $O(n \log n)$，可以通过。
只可惜我不会平衡树。
这里提供一种 $O(n (\log n)^2)$ 的做法。
可以发现，我们可以再输入完后，倒序还原出整个序列。
具体的，我们先将所有数设为 $1$，表示所有位置都没用过。每一次，我们找到第 $x_i$ 个为 $1$ 的位置（当然这个位置一定存在），然后这个位置上的数就是当前枚举的数，将该位置赋值为 $0$。
因为时间复杂度过高，我们可以采用二分+数据结构的方式来优化。这里选用树状数组（因为线段树常数太大，在我们那个 OJ 上被卡了）。
处理完后，就可以正常采用 $O(n \log n)$ 的方法求最长上升子序列了。
有一个细节，就是你每一次要与前面求出的最长上升长度求一个最大值，毕竟你要求的是全局最大值，而非只求以这个数结尾的最长上升子序列。
代码
这里同时附上 线段树+二分 与 树状数组+二分。
树状数组+二分：
#include<iostream>
using namespace std;
int n;
const int N=2e5+10;
int a[N];
int f[N];
inline int lowbit(int x){
return x&-x;
}
int d[N];
inline void modify(int x,int k){
for(int i=x;i<=n;i+=lowbit(i)){
d[i]=max(d[i],k);
}
return;
}
inline int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res=max(res,d[i]);
}
return res;
}
int c2[N];
void modify3(int x,int k){
for(int i=x;i<=n;i+=lowbit(i)){
c2[i]+=k;
}
}
int query2(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res+=c2[i];
}
return res;
}
int c[N];
inline int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)){
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x;
}
void write(int x){
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
a[i]++;
}
for(int i=1;i<=n;i++){
modify3(i,1);
}
for(int i=n;i;i--){
int l=a[i],r=n;
while(l<r){
int mid=(l+r)>>1;
if(query2(mid)>=a[i]){
r=mid;
}else{
l=mid+1;
}
}
c[l]=i;
modify3(l,-1);
}
for(int i=1;i<=n;i++){
int res=query(c[i]-1)+1;
f[c[i]]=res;
modify(c[i],res);
}
for(int i=1;i<=n;i++){
f[i]=max(f[i],f[i-1]);
write(f[i]);
putchar('\n');
}
}
线段树+二分：
#include<iostream>
using namespace std;
int n;
const int N=2e5+10;
int a[N];
int f[N];
inline int lowbit(int x){
return x&-x;
}
int d[N];
inline void modify(int x,int k){
for(int i=x;i<=n;i+=lowbit(i)){
d[i]=max(d[i],k);
}
return;
}
inline int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res=max(res,d[i]);
}
return res;
}
struct tree{
int l,r;
int cnt;
}tr[N<<2];
inline void push_up(int u){
tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;
}
void build(int u,int l,int r){
tr[u].l=l,tr[u].r=r;
if(l==r){
tr[u].cnt=1;
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
push_up(u);
}
void modify2(int u,int x){
if(tr[u].l==tr[u].r){
tr[u].cnt=0;
return;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid){
modify2(u<<1,x);
}else{
modify2(u<<1|1,x);
}
push_up(u);
}
int query1(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].cnt;
}
int res=0;
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid){
res=query1(u<<1,l,r);
}
if(r>mid){
res+=query1(u<<1|1,l,r);
}
return res;
}
int c[N];
inline int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)){
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x;
}
void write(int x){
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
a[i]++;
}
build(1,1,n);
for(int i=n;i;i--){
int l=a[i],r=n;
while(l<r){
int mid=(l+r)>>1;
if(query1(1,1,mid)>=a[i]){
r=mid;
}else{
l=mid+1;
}
}
c[l]=i;
modify2(1,l);
}
for(int i=1;i<=n;i++){
int res=query(c[i]-1)+1;
f[c[i]]=res;
modify(c[i],res);
}
for(int i=1;i<=n;i++){
f[i]=max(f[i],f[i-1]);
write(f[i]);
putchar('\n');
}
}
