P8277 [USACO22OPEN] Up Down Subsequence P 题解
题目传送门。
给一种码量有点大，但是思维难度不大的线段树优化 dp 做法。
一开始想了好久二分答案然后 check 的思路……
题意很简单，不说了。考虑 dp。
设 \(f_{i,0/1}\) 表示以 \(i\) 结尾，取出来后对应的字符为 U 或 D 的选取最大值。
转移：
更新 U：需要保证 \(j<i\) 并且 \(f_{j,0/1}\) 对应的字符是 U。因为我们正在更新 U。
同理，更新 D 需要保证 \(j>i\) 且 \(f_{j,0/1}\) 对应的字符是 D。
所以我们就得到了 \(O(n^2)\) 的部分分程序：
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
const int N=3e5+5;
int n,f[N][2],a[N],ans;
string s;
int main(){ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;++i)cin>>a[i];cin>>s;s=" "+s;for(int i=1;i<=n;++i){int x=a[i];f[x][0]=f[x][1]=1;for(int j=1;j<i;++j){int y=a[j];if(y<x){if(s[f[y][0]]=='U')f[x][0]=max(f[x][0],f[y][0]+1);if(s[f[y][1]]=='U')f[x][0]=max(f[x][0],f[y][1]+1);}if(y>x){if(s[f[y][0]]=='D')f[x][1]=max(f[x][1],f[y][0]+1);if(s[f[y][1]]=='D')f[x][1]=max(f[x][1],f[y][1]+1);}}ans=max(ans,max(f[x][0],f[x][1]));}
// for(int i=1;i<=n;++i)
// {
// cout<<i<<": ";
// cout<<f[i][0]<<' '<<f[i][1]<<'\n';
// }cout<<ans-1<<'\n';return 0;
}
然后考虑优化。
注意到每次查询，要么是 \([1,x-1]\)，要么是 \([x+1,n]\)，是一段连续的区间。
所以可以考虑用线段树维护最大值。
具体地，为 U 和 D 各开一个线段树。编号还是 \(0\) 对应 U，\(1\) 对应 D。
然后每次转移就只要 query 一下线段树就可以了，单次时间复杂度 \(O(\log n)\)。
最后考虑更新线段树。
首先线段树编号对应 \(0\) 或 \(1\)。
然后就是把 \(f_{i,0/1}\) 插入线段树 \(i\) 号位。
注意有可能 \(f_{i,0}\) 与 \(f_{i,1}\) 都插进了 \(i\) 号位，所以线段树更新的时候要 node[p][i].maxn=max(val,node[p][i].maxn);，而不是 node[p][i].maxn=val;。
总时间复杂度 \(O(n\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
const int N=3e5+5;
int lowbit(int x){return x&(-x);}
int n,f[N][2],a[N],ans,maxu,maxd;
string s;
struct NODE{int l,r,maxn;
}node[N*4][2];
#define lc (p<<1)
#define rc (p<<1|1)
void pushup(int p,int i)
{if(node[p][i].l==node[p][i].r)return;node[p][i].maxn=max(node[lc][i].maxn,node[rc][i].maxn);return;
}
void bld(int l,int r,int p,int i)
{node[p][i].l=l;node[p][i].r=r;if(l==r)return;int mid=(node[p][i].l+node[p][i].r)/2;bld(l,mid,lc,i);bld(mid+1,r,rc,i);pushup(p,i);return;
}
void addx(int x,int val,int p,int i)
{
// cout<<node[p][i].l<<' '<<node[p][i].r<<'\n';if(node[p][i].l==node[p][i].r){node[p][i].maxn=max(val,node[p][i].maxn);return; }int mid=(node[p][i].l+node[p][i].r)/2;if(x<=mid)addx(x,val,lc,i);elseaddx(x,val,rc,i);pushup(p,i);return;
}
int query(int l,int r,int p,int i)
{if(l<=node[p][i].l&&node[p][i].r<=r)return node[p][i].maxn;int mid=(node[p][i].l+node[p][i].r)/2,ans=0;if(l<=mid)ans=max(ans,query(l,r,lc,i));if(mid<r)ans=max(ans,query(l,r,rc,i));return ans;
}
int main(){ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;++i)cin>>a[i];cin>>s;s=" "+s;bld(1,n,1,0);bld(1,n,1,1);for(int i=1;i<=n;++i){int x=a[i];f[x][0]=f[x][1]=1;f[x][0]=max(f[x][0],query(1,x-1,1,0)+1);f[x][1]=max(f[x][1],query(x+1,n,1,1)+1);ans=max(ans,max(f[x][0],f[x][1]));if(s[f[x][0]]=='U')addx(x,f[x][0],1,0);if(s[f[x][1]]=='U')addx(x,f[x][1],1,0);if(s[f[x][0]]=='D')addx(x,f[x][0],1,1);if(s[f[x][1]]=='D')addx(x,f[x][1],1,1);}
// for(int i=1;i<=n;++i)
// {
// cout<<i<<": ";
// cout<<f[i][0]<<' '<<f[i][1]<<'\n';
// }cout<<ans-1<<'\n';return 0;
}你说得对，但是本来想用树状数组的，但是发现好像不太容易用 \([1,r]\) 的答案减去 \([1,l-1]\) 的答案，于是用了线段树。虽然常数大了点，但好歹思维难度不高。
UPD：写完后想了想，发现其实可以用树状数组。因为只有 \([x+1,n]\) 这类型的区间，所以可以反着再建树状数组，反着查询。不过这太麻烦了。