結果
問題 |
No.686 Uncertain LIS
|
ユーザー |
![]() |
提出日時 | 2025-02-22 20:59:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 239 ms / 2,000 ms |
コード長 | 2,424 bytes |
コンパイル時間 | 2,046 ms |
コンパイル使用メモリ | 207,660 KB |
実行使用メモリ | 10,388 KB |
最終ジャッジ日時 | 2025-02-22 20:59:59 |
合計ジャッジ時間 | 8,264 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct Node { int l, r, val, sz, pri; int add; Node() { l = r = val = sz = 0; add = 0; pri = -1; } Node(int x) { l = r = 0; sz = 1; val = x; add = 0; pri = rand(); } }; struct FHQ_Treap { int n, rt; vector<Node> a; FHQ_Treap() { n = rt = 0; a = vector<Node>(300005); } void pushup(int x) { a[x].sz = a[a[x].l].sz + a[a[x].r].sz + 1; } void mktag(int x, int v) { a[x].val += v; a[x].add += v; } void pushdown(int x) { mktag(a[x].l, a[x].add); mktag(a[x].r, a[x].add); a[x].add = 0; } void spt_sz(int x, int k, int &L, int &R) { if (x == 0) { L = R = 0; return ; } pushdown(x); if (a[a[x].l].sz + 1 <= k) L = x, spt_sz(a[x].r, k - a[a[x].l].sz - 1, a[x].r, R); else R = x, spt_sz(a[x].l, k, L, a[x].l); pushup(x); } void spt_val(int x, int k, int &L, int &R) { if (x == 0) { L = R = 0; return ; } pushdown(x); if (a[x].val < k) L = x, spt_val(a[x].r, k, a[x].r, R); else R = x, spt_val(a[x].l, k, L, a[x].l); pushup(x); } int mrg(int L, int R) { if (L == 0 || R == 0) return L + R; pushdown(L); pushdown(R); if (a[L].pri > a[R].pri) { a[L].r = mrg(a[L].r, R); pushup(L); return L; } else { a[R].l = mrg(L, a[R].l); pushup(R); return R; } } int pre(int v) { //v??? int L, M, R, ans; spt_val(rt, v, L, R); spt_sz(L, a[L].sz - 1, L, M); ans = a[M].val; rt = mrg(L, mrg(M, R)); return ans; } int nxt(int v) { //v??? int L, M, R, ans; spt_val(rt, v + 1, L, R); spt_sz(R, 1, M, R); if (M == 0) return 0; ans = a[M].val; rt = mrg(L, mrg(M, R)); return ans; } void insrt(int v) { int L, M = ++n, R; a[M] = Node(v); spt_val(rt, v, L, R); rt = mrg(L, mrg(M, R)); } void del(int x) { //??x int L, M, R; spt_val(rt, x, L, R); spt_sz(R, 1, M, R); rt = mrg(L, R); } void mdf(int l, int r, int v) { //????[l,r)??v int L, M, R; spt_val(rt, l, L, R); spt_val(R, r, M, R); mktag(M, v); rt = mrg(L, mrg(M, R)); } } t; int n, l, r; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> l >> r; if (i == 1) { t.insrt(l); continue; } int nxtt = t.nxt(r - 1); t.mdf(l, r, 1); // cout << nxtt << ':'; if (nxtt) t.del(nxtt); t.insrt(l); // cout << t.a[t.rt].sz << endl; } cout << t.a[t.rt].sz << endl; return 0; } /* 5 1 1 100 100 102 102 105 105 3 102 */