题意
给出 \(n\) 个区间 \([l_i,r_i]\) 和 \(n\) 个未知数 \(a_1,a_2,\dots,a_n\)，现在你要确定这 \(n\) 个数，使得 \(a_i\in[l_i,r_i]\)，并且这个序列的最长严格上升子序列尽可能大，求这个最大值。
\(1 \leq n\leq 3\times 10^5\)，\(1 \leq l_i,r_i\leq 10^9\)。
题解
首先考虑 \(n^2\) dp, 设 \(dp[i]\) 表示长度为\(i\)的最长上升子序列的末尾最少是多少。
那么转移方程如下。
- \(dp[i - 1] < l, dp[i] = \min(dp[i], l)\)
- $l <= dp[i - 1]< r, dp[i] = dp[i - 1] + 1) $
- \(dp[i - 1] >= r, dp[i] = dp[i]\)
观察知 \(dp_i\) 具有单调性。
对于第三部分我们显然可以不管它。
对于第二部分， 相当于区间平移, 并且区间加 \(+1\).
对于第一部分，就是把第一个大于等于 \(l\) 的值变为 \(l\)
对于区间平移， 相当于在区间前加入一个元素， 并删除区间后的第一个元素。
综上， \(dp\) 转移相当于删除第一个大于等于 \(r\) 的元素,把 \(l \leq dp[i] < r\) 的 \(dp[i]\) 加 \(1\) , 然后在第一个大于等于 \(l\) 的位置前插入一个 \(l\) 。
因为涉及区间操作和插入删除， 考虑 \(splay\) 维护。
时间复杂度: \(\Theta(nlogn)\)
坑
- 要注意哨兵节点大小， 不能就设1e9, 我调了几个小时。
代码
点击查看代码
#include <stdio.h>
#include <string.h>
#include <iostream>
const int N = 6e5, INF = 1e9;
using namespace std;
int n, dp[N + 5], l[N + 5], r[N + 5], Opt;
int cnt, ans;
void read(int &x) {
x = 0; int w = 1; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if (c == '-') w = -1;
for(; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + c - '0'; x *= w;
}
struct spla{
int ch[N + 5][2], fa[N + 5], val[N + 5], tag[N + 5],rt, tot;
void pushdown(int p) {
if (tag[p]) {
if (ch[p][0]) {val[ch[p][0]] += tag[p]; tag[ch[p][0]] += tag[p];}
if (ch[p][1]) {val[ch[p][1]] += tag[p]; tag[ch[p][1]] += tag[p];}
tag[p] = 0;
}
}
int get(int x) {return x == ch[fa[x]][1];}
void rotate(int x) {
int y = fa[x], z = fa[y], k = get(x);
ch[z][get(y)] = x; fa[x] = z;
ch[y][k] = ch[x][k^1]; fa[ch[y][k]] = y;
ch[x][k^1] = y; fa[y] = x;
}
void splay(int x, int k) {
while(fa[x] != k) {
int y = fa[x], z = fa[y];
pushdown(z); pushdown(y); pushdown(x);
if (z != k) {
if (get(x) != get(y)) rotate(x);
else rotate(y);
}
rotate(x);
}
if (!k) rt = x;
}
void insert(int &pos, int v, int f) {
if (!pos) {
pos = ++tot; fa[pos] = f; val[pos] = v;
splay(pos, 0);
return;
}
pushdown(pos);
if (v < val[pos]) insert(ch[pos][0], v, pos);
else insert(ch[pos][1], v, pos);
}
int find(int x) { // 找最后一个小于x
int p = rt, ans = 0;
while(p) {
pushdown(p);
if (val[p] < x) {
ans = p; p = ch[p][1];
}
else p = ch[p][0];
}
return ans;
}
int Nxt(int x) {
splay(x, 0); x = ch[x][1];
while(ch[x][0]) x = ch[x][0];
return x;
}
int Pre(int x) {
splay(x, 0); x = ch[x][0];
while(ch[x][1]) x = ch[x][1];
return x;
}
void del(int x) {
int u = Pre(x), v = Nxt(x);
splay(u, 0); splay(v, u);
fa[x] = 0;ch[v][0] = 0;
}
}t;
int main() {
read(n);
t.insert(t.rt, -INF * 2 - 10, 0); t.insert(t.rt, INF + INF, 0);
int ans = n;
for(int i = 1, l, r; i <= n; ++i) {
scanf("%d%d", &l, &r);
int u = t.find(l), v = t.find(r), nxt = t.Nxt(v);
if (u ^ v) {
t.splay(u, 0); t.splay(nxt, u);
t.val[t.ch[nxt][0]]++; t.tag[t.ch[nxt][0]]++;
}
if (nxt != 2) {t.del(nxt); --ans;}
t.insert(t.rt, l, 0);
}
printf("%d\n", ans);
return 0;
}