Lxzyzby Lxzyzby

Luogu P4309 [TJOI2013]最长上升子序列

in FHQ Treap,线段树 read (46) 文章转载请注明来源!

题目链接

用平衡树求出最后的序列,之后因为每一个数都不同,且从 $1-N$ 的操作,全都是递增的操作,所以考虑在线段树中,寻找 $[1,k-1]$ 中最大的连续序列,之后更换新 $k$ 位的值即可

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
const int MAXN = 2e5;
const int Inf = 0x3f3f3f3f;
struct FHQ_Treap {
    int lc[MAXN], rc[MAXN], val[MAXN], siz[MAXN];
    int root, rnd[MAXN], cnt, id[MAXN], fa[MAXN];
    FHQ_Treap() {
        root = cnt = 0;
    }
    int newnode(int x) {
        val[++cnt] = x; lc[cnt] = rc[cnt] = fa[cnt] = 0;
        rnd[cnt] = rand(); siz[cnt] = 1; id[x] = cnt; 
        return cnt; 
    }
    void PushUp(int rt) {
        siz[rt] = 1;
        if(lc[rt]) siz[rt] += siz[lc[rt]], fa[lc[rt]] = rt;
        if(rc[rt]) siz[rt] += siz[rc[rt]], fa[rc[rt]] = rt;
    }
    void split(int rt, int C, int &x, int &y) {
        if(!rt) return x = y = 0, void();
        if(siz[lc[rt]] + 1 <= C) x = rt, split(rc[rt], C - siz[lc[rt]] - 1, rc[rt], y);
        else y = rt, split(lc[rt], C, x, lc[rt]);
        PushUp(rt);
    }
    int merge(int x, int y) {
        if(!x || !y) return x + y;
        if(rnd[x] < rnd[y]) return rc[x] = merge(rc[x], y), PushUp(x), x;
        else return lc[y] = merge(x, lc[y]), PushUp(y), y;
    }
    void insert(int pos, int C) {
        int x, y;
        split(root, pos-1, x, y);
        x = merge(x, newnode(C));
        root = merge(x, y);
    }
    void dfs(int rt, vector<int> &a) {
        if(lc[rt]) dfs(lc[rt], a);
        a.push_back(val[rt]);
        if(rc[rt]) dfs(rc[rt], a);
    }
}t;
int n;
namespace Segment_Tree {
    struct Node {
        int mx;
    }v[MAXN<<2];
    #define lch rt<<1
    #define rch rt<<1|1
    void PushUp(int rt) {
        v[rt].mx = max(v[lch].mx, v[rch].mx);
    }
    void Update(int L, int C, int l, int r, int rt) {
        if(l == r) {
            v[rt].mx = C;
            return;
        }
        int mid = (l + r) >> 1;
        if(L <= mid) Update(L, C, l, mid, lch);
        else Update(L, C, mid+1, r, rch);
        PushUp(rt);
    }
    int Query(int L, int R, int l, int r, int rt) {
        if(L <= l && r <= R) return v[rt].mx;
        int mid = (l + r) >> 1, ans = -Inf;
        if(L <= mid) ans = max(ans, Query(L, R, l, mid, lch));
        if(R > mid) ans = max(ans, Query(L, R, mid+1, r, rch));
        return ans;
    }
}
vector<int> a;
int pos_a[MAXN];
int main() {
    // freopen("input", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    srand(time(0));
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        int pos; cin >> pos; pos++; 
        t.insert(pos, i);
    }
    t.dfs(t.root, a);
    for(int i = 0; i < int(a.size()); i++) 
        pos_a[a[i]] = i+1; 
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int mx = Segment_Tree::Query(1, pos_a[i], 1, n, 1);
        Segment_Tree::Update(pos_a[i], mx+1, 1, n, 1);
        ans = max(ans, mx+1);
        cout << ans << endl;
    }
    return 0;
}

本文基于《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
文章链接:https://zby.xyz/index.php/archives/84/ (转载时请注明本文出处及文章链接)

FHQ Treap线段树
发表新评论
博客已萌萌哒运行
© 2020 由 Typecho 强力驱动.Theme by YoDu
PREVIOUS NEXT
雷姆
拉姆