From b56ee90644b4e78328eb422bda7f04753c650b66 Mon Sep 17 00:00:00 2001
From: Dennis Yang <dennisyang@hotmail.co.jp>
Date: Fri, 15 Nov 2013 20:00:21 +0800
Subject: [PATCH] Persistent Segment Tree

---
 BZOJ/1901.cpp | 106 +++++++++++++++++++++++++++
 BZOJ/1901.pas | 228 ----------------------------------------------------------
 2 files changed, 106 insertions(+), 228 deletions(-)
 create mode 100644 BZOJ/1901.cpp
 delete mode 100644 BZOJ/1901.pas

diff --git a/BZOJ/1901.cpp b/BZOJ/1901.cpp
new file mode 100644
index 0000000..877af59
--- /dev/null
+++ b/BZOJ/1901.cpp
@@ -0,0 +1,106 @@
+/**************************************************************
+    Problem: 1901
+    User: dennisyang
+    Language: C++
+    Result: Accepted
+    Time:1012 ms
+    Memory:59508 kb
+****************************************************************/
+ 
+//Algorithm: Fenwick Tree & Persistent Segment Tree
+#include <cstdio>
+#include <vector>
+ 
+const int maxnode = 5e6 + 10,maxn = 1e4 + 10,rlim = 1<<30;
+ 
+struct node {
+    int size;
+    node *ch[2];
+} pool[maxnode],*tot = &pool[0],*root[maxn];
+ 
+int n,m,orig[maxn];
+ 
+node* Insert(node* orig, int l, int r, int pos, int val) {
+    if (orig == NULL) orig = tot++;
+    orig->size += val;
+    if (l == r) return orig;
+    int m = (l + r) >> 1;
+    if (pos <= m) orig->ch[0] = Insert(orig->ch[0],l,m,pos,val); else orig->ch[1] = Insert(orig->ch[1],m+1,r,pos,val);
+    return orig;
+}
+ 
+inline int lowbit(int x) { return x & -x; }
+ 
+inline void get(std::vector<node*> &tree, int idx) {
+    tree.clear();
+    while (idx) {
+        tree.push_back(root[idx]);
+        idx -= lowbit(idx);
+    }
+}
+ 
+inline int getsum(std::vector<node*> &tree) {
+    int res = 0;
+    std::vector<node*>::iterator iter;
+    for (iter = tree.begin(); iter != tree.end(); ++iter)
+        if ((*iter) && (*iter) -> ch[0]) res += (*iter) -> ch[0] -> size;
+    return res;
+}
+ 
+inline void turn(std::vector<node*> &tree, bool d) {
+    std::vector<node*>::iterator iter;
+    for (iter = tree.begin(); iter != tree.end(); ++iter)
+        if (*iter) *iter = (*iter) -> ch[d];
+}
+ 
+inline void update(int idx, int pos, int val) {
+    while (idx <= n) {
+        root[idx] = Insert(root[idx],0,rlim,pos,val);
+        idx += lowbit(idx);
+    }
+}
+ 
+int Query(int l, int r, int k, std::vector<node*> lt, std::vector<node*> rt) {
+    if (l == r) return l;
+    int m = (l + r) >> 1, cnt = getsum(rt) - getsum(lt);
+    bool d = k > cnt;
+    turn(lt,d);
+    turn(rt,d);
+    if (d) {
+        l = m + 1;
+        k -= cnt;
+    } else r = m;
+    return Query(l,r,k,lt,rt);
+}
+ 
+inline int query(int l, int r, int k) {
+    std::vector<node*> tree[2];
+    get(tree[0],l-1);
+    get(tree[1],r);
+    return Query(0,rlim,k,tree[0],tree[1]);
+}
+ 
+int main() {
+    std::scanf("%d%d",&n,&m);
+    for (int i = 1,t; i <= n; ++i) {
+        std::scanf("%d",orig + i);
+        update(i,orig[i],1);
+    }
+    char op;
+    int pos,num,l,r,k;
+    while (m--) {
+        std::scanf(" %c",&op);
+        switch (op) {
+            case 'C':
+                std::scanf("%d%d",&pos,&num);
+                update(pos,orig[pos],-1);
+                update(pos,orig[pos] = num,1);
+                break;
+            case 'Q':
+                std::scanf("%d%d%d",&l,&r,&k);
+                std::printf("%d\n",query(l,r,k));
+                break;
+        }
+    }
+    return 0;
+}
\ No newline at end of file
diff --git a/BZOJ/1901.pas b/BZOJ/1901.pas
deleted file mode 100644
index e68498e..0000000
--- a/BZOJ/1901.pas
+++ /dev/null
@@ -1,228 +0,0 @@
-type
-  treapnode=record
-              v,p,size,l,r:longint;
-              //v: value, p: priority, l: lson, r: rson
-            end;
-
-  segment=record
-            l,r:longint;
-            bst:longint; //bst: root of the treap
-            lson,rson:longint;
-          end;
-
-var
-  treap:array [0..1100000] of treapnode;
-  segtree:array [0..100100] of segment;
-  pos,top,x,root:longint;
-  data:array [0..50010] of longint;
-
-//Implementation of Treap
-
-procedure new_treap(v,root:longint);
-begin
-  treap[root].p:=random(maxlongint);
-  treap[root].l:=0;
-  treap[root].r:=0;
-  treap[root].v:=v;
-  treap[root].size:=1;
-end;
-
-procedure RightRotate(var p:longint);
-var
-  q:longint;
-
-begin
-  q:=treap[p].l;
-  treap[p].l:=treap[q].r;
-  treap[q].r:=p;
-  p:=q;
-end;
-
-procedure LeftRotate(var p:longint);
-var
-  q:longint;
-
-begin
-  q:=treap[p].r;
-  treap[p].r:=treap[q].l;
-  treap[q].l:=p;
-  p:=q;
-end;
-
-procedure update(p:longint);
-begin
-  if p=0 then exit;
-  treap[p].size:=treap[treap[p].l].size+treap[treap[p].r].size+1;
-end;
-
-procedure add(v:longint; var root:longint); overload;
-begin
-  if root=0 then
-    begin
-      inc(pos);
-      root:=pos;
-      new_treap(v,root);
-      exit;
-    end;
-  if v<treap[root].v then
-    begin
-      add(v,treap[root].l);
-      if treap[treap[root].l].p<treap[root].p then RightRotate(root);
-    end
-  else
-    begin
-      add(v,treap[root].r);
-      if treap[treap[root].r].p<treap[root].p then LeftRotate(root);
-    end;
-  update(root);
-  update(treap[root].l);
-  update(treap[root].r);
-end;
-
-procedure del(k:longint; var root:longint);
-begin
-  if k<treap[root].v then del(k,treap[root].l) else
-    if k>treap[root].v then del(k,treap[root].r) else
-      begin
-        if (treap[root].l=0) and (treap[root].r=0) then
-          begin
-            root:=0;
-            exit;
-          end;
-        if (treap[root].l>0) and (treap[root].r=0) then root:=treap[root].l else
-          if (treap[root].l=0) and (treap[root].r>0) then root:=treap[root].r else
-            begin
-              if treap[treap[root].l].p<treap[root].p then
-                begin
-                  RightRotate(root);
-                  del(k,treap[root].r);
-                end
-              else
-                begin
-                  LeftRotate(root);
-                  del(k,treap[root].l);
-                end;
-            end;
-      end;
-  update(root);
-  update(treap[root].l);
-  update(treap[root].r);
-end;
-
-function succ(k,root:longint):longint;
-begin
-  if root=0 then exit(0);
-  if k>=treap[root].v then exit(treap[treap[root].l].size+1+succ(k,treap[root].r));
-  exit(succ(k,treap[root].l));
-end;
-
-//end of Treap
-
-//Implementation of SegmentTree
-
-function mid(root:longint):longint; inline;
-begin
-  exit((segtree[root].l+segtree[root].r) shr 1);
-end;
-
-procedure BuildTree(l,r:longint; var root:longint);
-var
-  i:longint;
-
-begin
-  inc(top);
-  root:=top;
-  segtree[root].l:=l;
-  segtree[root].r:=r;
-  segtree[root].bst:=0;
-  segtree[root].lson:=0;
-  segtree[root].rson:=0;
-  for i:=l to r do add(data[i],segtree[root].bst);
-  if l=r then exit;
-  BuildTree(l,mid(root),segtree[root].lson);
-  BuildTree(mid(root)+1,r,segtree[root].rson);
-end;
-
-procedure change(p,v,root:longint); inline;
-begin
-  del(p,segtree[root].bst);
-  add(v,segtree[root].bst);
-end;
-
-procedure modify(p,v,root:longint); overload;
-begin
-  change(data[p],v,root);
-  if segtree[root].l=segtree[root].r then exit;
-  if p<=mid(root) then modify(p,v,segtree[root].lson) else modify(p,v,segtree[root].rson);
-end;
-
-function askrank(l,r,v,root:longint):longint;
-begin
-  if (segtree[root].l>=l) and (segtree[root].r<=r) then exit(succ(v,segtree[root].bst));
-  if r<=mid(root) then exit(askrank(l,r,v,segtree[root].lson)) else
-    if l>mid(root) then exit(askrank(l,r,v,segtree[root].rson)) else
-      exit(askrank(l,r,v,segtree[root].lson)+askrank(l,r,v,segtree[root].rson));
-end;
-
-function ask(l,r,v:longint):longint; overload;
-var
-  p,q,mid,t1,t2:longint;
-
-begin
-  p:=0;
-  q:=maxlongint shr 1;
-  while p<=q do
-    begin
-      mid:=(p+q) shr 1;
-      t1:=askrank(l,r,mid,1);
-      t2:=askrank(l,r,mid-1,1);
-      if (v<=t1) and (v>t2) then exit(mid);
-      if t1<v then p:=mid+1 else q:=mid;
-    end;
-end;
-
-procedure modify(p,v:longint); overload;
-begin
-  modify(p,v,1);
-  data[p]:=v;
-end;
-
-procedure main;
-var
-  n,m,i,x,y,k:longint;
-  order:char;
-
-begin
-  pos:=0;
-  top:=0;
-  readln(n,m);
-  for i:=1 to n do read(data[i]);
-  readln;
-  root:=1;
-  BuildTree(1,n,root);
-  repeat
-    read(order);
-    case order of
-      'C':begin
-            readln(x,k);
-            modify(x,k);
-          end;
-      'Q':begin
-            readln(x,y,k);
-            writeln(ask(x,y,k));
-          end;
-    end;
-    dec(m);
-  until m=0;
-end;
-
-begin
-  randomize;
-//readln(x);
-  x:=1;
-//This is the difference between BZOJ1901&ZOJ2112
-  repeat
-    dec(x);
-    main;
-  until x=0;
-end.
-- 
2.11.4.GIT