CodeForces 809D Hitchhiking in the Baltic States（FHQ-Treap）

题意

给你长度为$n$的序列，序列中的每个元素$i$有一个区间限制$[l_i,r_i]$，你从中选出一个子序列，并给它们标号$x_i$，要求满足 $，∀i<j，x_i<x_j$，且$， ∀i，x_i∈[l_i,r_i]$。问满足条件子序列的长度最长为多少？

其中$1\leq n\leq3\times 10^5\ 1\leq l_i\leq r_i\leq 10^9$

题解

不妨设$f[i][j]$表示已经选到第$i$个，其中最大值为$j$最多能选几个。

显然是开不下的...但是还记得$O(nlogn)$的$LIS$吗？它利用了二分栈！

所以我们不妨考虑设$f[i][j]$表示当前选到第$i$个，已经选了$j$个的末尾最小元素。

如果不选，显然$f[i+1][j]=f[i][j]$

如果$r[i+1]>f[i][j]$，那么，则有$f[i+1][j+1]=max(f[i][j]+1,l[i+1])$

不难发现可以用滚动数组滚掉第一维，所以第一个方程直接作废：

$ f[j+1]=max(f[j]+1,l[i+1]) $

但是时间还是$O(n^2)$的啊，枚举一个$i$，枚举一个$j$。

不急，咱们分开考虑，对于一个$l[i]<f<r[i]$

它的当前$dp$值可以直接$+1$，那么位置也将$+1$因为多选了一个嘛。

剩下的话，就是$f<l[i]$的情况，直接就等于$l[i]$了。

用一颗$FHQ-Treap$维护一下就行了。

$PS$：注意数组开两倍（最开始$n$个以及$dp$中的$n$个新节点）

#include <ctime>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 6e5 + 10, Inf = 1e9 + 7;

int n, l, r;

int rt, tot, val[N], add[N], lc[N], rc[N], pri[N];

inline int node(int x) { val[++tot] = x, pri[tot] = rand(); return tot; }

inline void pushdown(int o) {

    if(add[o]) {

        val[o] += add[o];

        if(lc[o]) add[lc[o]] += add[o];

        if(rc[o]) add[rc[o]] += add[o];

        add[o] = 0;

    }

}

int merge(int l, int r) {

    if(!l || !r) return l + r;

    pushdown(l), pushdown(r);

    if(pri[l] < pri[r]) { rc[l] = merge(rc[l], r); return l; }

    else { lc[r] = merge(l, lc[r]); return r; }

}

void split(int o, int k, int &l, int &r) {

    if(!o) { l = r = 0; return ; } pushdown(o);

    if(val[o] <= k) l = o, split(rc[o], k, rc[o], r);

    else r = o, split(lc[o], k, l, lc[o]);

}

int min(int o) { pushdown(o); return lc[o] ? min(lc[o]) : val[o]; }

int calc(int o) {

    if(!o) return 0; pushdown(o);

    return calc(lc[o]) + calc(rc[o]) + (val[o] < Inf);

}

int main () {

    read(n), srand(19260817); int x, y, k, p;

    for(int i = 1; i <= n; ++i) rt = merge(rt, node(Inf));

    for(int i = 1; i <= n; ++i) {

        read(l), read(r);

        split(rt, l - 1, x, y), split(y, r - 1, k, y);

        if(k) ++add[k];

        split(y, min(y), p, y);

        rt = merge(merge(merge(x, node(l)), k), y);

    } printf("%d\n", calc(rt));

    return 0;

}

巴特西

CodeForces 809D Hitchhiking in the Baltic States（FHQ-Treap）

题意

题解

最新文章

热门文章