欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 财经 > 创投人物 > [ARC159D] LIS 2 题解

[ARC159D] LIS 2 题解

2024/10/26 12:01:18 来源:https://blog.csdn.net/qq_49785217/article/details/143224603  浏览:    关键词:[ARC159D] LIS 2 题解

[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=1maxi1fj1+1

换成一段一段的区间就长成这样:

img

很好发现: 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+rirj

我们可以把答案存在区间右端点上,然后用动态开点线段树求前缀最大值,就可以转移了。

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;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com