您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

ZOJ 2112 Dynamic Rankings：線段樹套平衡樹 (Treap) 解決區間第 K 大帶修改

編輯：關於C++

問題描述

動態序列，支持：單點修改、區間查詢第 k 大。N≤50000, M≤10000。經典「線段樹套 Treap」或「主席樹套 BIT」問題。

方案一：按值域建線段樹 + Treap 存位置 (離線)

值域離散化（包含修改值）
線段樹節點維護 Treap，存該值域範圍內元素的位置
查詢第 k 大：左子樹位置在 [L,R] 計數 ≥k 走左，否則 k-=計數走右
修改：舊值位置從 Treap 刪除，新值位置插入
複雜度：建樹/查詢/修改均 O(log²N)

方案二：按位置建線段樹 + Treap 存值 (在線)

線段樹節點維護 Treap，存該區間內元素的值
查詢：二分答案值域，BIT 風格查詢 ≤mid 個數
處理重複值：查
複雜度：查詢 O(log³N)，修改 O(log²N)

核心 Treap 實現 (方案一)

struct Node {
    Node *ch[2]; int r, v, s;
    int cmp(int x) { return x==v ? -1 : (xs + ch[1]->s; }
} treap[MAXN*15], *null = treap;
int ncnt;
Node* newNode(int v) { Node* o=&treap[ncnt++]; o->ch[0]=o->ch[1]=null; o->r=rand(); o->v=v; o->s=1; return o; }
void rotate(Node* &o, int d) { Node* k=o->ch[d^1]; o->ch[d^1]=k->ch[d]; k->ch[d]=o; o->maintain(); k->maintain(); o=k; }
void insert(Node* &o, int v) { if(o==null){o=newNode(v);return;} int d=o->cmp(v); insert(o->ch[d],v); if(o->ch[d]->r>o->r) rotate(o,d^1); o->maintain(); }
void remove(Node* &o, int v) { int d=o->cmp(v); if(d==-1){ if(o->ch[0]!=null&&o->ch[1]!=null){int d2=o->ch[0]->r>o->ch[1]->r; rotate(o,d2); remove(o->ch[d2],v);} else o=o->ch[0]!=null?o->ch[0]:o->ch[1];} else remove(o->ch[d],v); if(o!=null) o->maintain(); }
int queryGE(Node* o, int v) { if(o==null) return 0; if(o->v>=v) return o->ch[1]->s+1+queryGE(o->ch[0],v); return queryGE(o->ch[1],v); }

線段樹操作

Node* seg[4*MAXN];
void build(int l,int r,int rt){ seg[rt]=null; if(l==r)return; build(ls); build(rs); }
void insertPos(int pos,int val,int l,int r,int rt){ insert(seg[rt],pos); if(l==r)return; if(pos<=mid) insertPos(ls); else insertPos(rs); }
void removePos(int pos,int val,int l,int r,int rt){ remove(seg[rt],pos); if(l==r)return; if(pos<=mid) removePos(ls); else removePos(rs); }
int queryKth(int L,int R,int k,int l,int r,int rt){
    if(l==r) return l;
    int cnt = queryGE(seg[ls],L) - queryGE(seg[ls],R+1);
    if(cnt>=k) return queryKth(L,R,k,ls);
    return queryKth(L,R,k-cnt,rs);
}