[ARC159D] LIS 2
题面：
题面翻译
给定 n n n 个操作，每次操作给出 l , r l,r l,r，并在 a a a 序列里依次添加 i ∈ [ l , r ] i\in[l,r] i∈[l,r]。
求最后 a a a 的最长上升子序列。
题目描述
数列 $ X $ があります。初め、$ X $ は空です。
高橋君は $ i=1,2,\ldots,N $ の順に次の操作をしました。
- $ X $ の末尾に $ l_i,l_i+1,\ldots,r_i $ をこの順番で追加する。
操作後の $ X $ の狭義単調増加部分列の長さの最大値を求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ l_1 $ $ r_1 $ $ \vdots $ $ l_{N} $ $ r_{N} $
输出格式
答えを出力せよ。
样例 #1
样例输入 #1
4 1 1 2 4 10 11 7 10样例输出 #1
8样例 #2
样例输入 #2
4 1 1 1 1 1 1 1 1样例输出 #2
1样例 #3
样例输入 #3
1 1 1000000000样例输出 #3
1000000000提示
制約
- $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
- $ 1\ \leq\ l_i\ \leq\ r_i\ \leq\ 10^9 $
- 入力はすべて整数
Sample Explanation 1
操作後の $ X $ は $ (1,2,3,4,10,11,7,8,9,10) $ です。 この数列の $ 1,2,3,4,7,8,9,10 $ 項目からなる部分列は狭義単調増加であり、かつこれが長>さが最大のものです。
Sample Explanation 2
操作後の $ X $ は $ (1,1,1,1) $ です。
线段树优化 d p dp dp 入门。
我们来具象化这个求得最长上升子序列的过程：
首先，我们都会基础最长上升子序列的 d p dp dp: f i = max j = 1 i − 1 f j − 1 + 1 f_i = \max\limits_{j = 1}^{i - 1}{f_{j - 1}} + 1 fi=j=1maxi−1fj−1+1
换成一段一段的区间就长成这样：
很好发现： f i = max r j < r i f j + r i − r j f_{i} = \max\limits_{r_j < r_i}{f_j + r_i - r_j} fi=rj<rimaxfj+ri−rj
我们可以把答案存在区间右端点上，然后用动态开点线段树求前缀最大值，就可以转移了。
AC-code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 0) f = -1,x *= f;
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
if(f == -1) putchar('-');
while (top) putchar(sta[--top] + 48);
}
const int N = 2e5+5;
const int inf = 0x3f3f3f3f3f3f3f3fLL;
int n,f[N],rt[2];
struct sgt{
#define mid ((pl + pr) >> 1)
int mx[N * 50],cnt,ls[N * 50],rs[N * 50];
sgt(){memset(mx,0xcf,sizeof(mx));}
void push_up(int p) {
mx[p] = max(mx[ls[p]],mx[rs[p]]);
}
void update(int &p,int pl,int pr,int k,int d) {
if(!p) p = ++cnt;
if(pl == pr) {mx[p] = max(mx[p],d);return;}
if(k <= mid) update(ls[p],pl,mid,k,d);
else update(rs[p],mid+1,pr,k,d);
push_up(p);
}
int query(int p,int pl,int pr,int l,int r) {
if(!p) return -inf;
if(l <= pl && pr <= r) return mx[p];
if(r <= mid) return query(ls[p],pl,mid,l,r);
else if(l > mid) return query(rs[p],mid+1,pr,l,r);
else return max(query(ls[p],pl,mid,l,r),query(rs[p],mid+1,pr,l,r));
}
};
sgt T[2];
signed main() {
n = rd();int ans = 0;
T[0].update(rt[0],0,1e9,0,0);
T[1].update(rt[1],0,1e9,0,0);
for(int i = 1;i<=n;i++) {
int l = rd(),r = rd();
f[i] = max(T[0].query(rt[0],0,1e9,l,r) + r,T[1].query(rt[1],0,1e9,0,l - 1) + r - l + 1);
T[0].update(rt[0],0,1e9,r,f[i] - r);
T[1].update(rt[1],0,1e9,r,f[i]);
ans = max(ans,f[i]);
}
wt(ans);
return 0;
}
