记录编号	390950	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	4.606 s
提交时间	2017-04-04 18:37:01	内存使用	5.33 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <cctype>
using namespace std;
struct node{
  node *ls, *rs;
  int fix, value;
  int size;  
  node(int v){
    fix = rand(); size = 1; value = v;
    ls = rs = NULL;
  }
  inline int lsize(){
    return ls?ls->size:0;
  }
  inline int rsize(){
    return rs?rs->size:0;
  }
  inline void pushup(){
    size = 1+lsize()+rsize();
  }
};
node *merge(node *x, node *y){
  if(!x)return y; if(!y)return x;
  if(x->fix < y->fix){
    x->rs = merge(x->rs, y);
    x->pushup(); return x;
  }else{
    y->ls = merge(x, y->ls);
    y->pushup(); return y;
  }
}
typedef pair<node *, node *>droot;
droot split(node *x, int k){
  droot r(NULL, NULL);
  if(!x)return r;
  if(x->lsize() >= k){
    r = split(x->ls, k);
    x->ls = r.second;
    x->pushup();
    r.second = x;
  }else{
    r = split(x->rs, k-x->lsize()-1);
    x->rs = r.first;
    x->pushup();
    r.first = x;
  }
  return r;
}
int lower(node *x, int v){
  if(!x)return 0;
  if(v < x->value)return lower(x->ls, v);
  else return 1+x->lsize()+lower(x->rs, v);
}
node *insert(node *x, int v){
  int k = lower(x, v);
  droot p = split(x, k);
  node *d = new node(v);
  return merge(merge(p.first, d), p.second);
}
node *erase(node *x, int v){
  int k = lower(x, v);
  droot p1 = split(x, k-1);
  droot p2 = split(p1.second, 1);
  if(p2.first && p2.first->value == v){
    delete p2.first; p2.first = NULL;
  }
  return merge(p1.first, merge(p2.first, p2.second));
}
#define MAXN 50001
struct segtree{
  node *root;
  int ls, rs;
}ns[MAXN<<1+2];
int _seglast = 1;
int a[MAXN];
inline 
void build(node *&rt, int l, int r){
  for(int i = l; i <= r; i++)rt = insert(rt, a[i]);
}
int build(int l, int r){
  if(l > r)return 0;
  int c = _seglast++;
  if(l == r){
    ns[c].root = new node(a[l]);
  }else{
    build(ns[c].root, l, r);
    int m = (l+r)>>1;
    ns[c].ls = build(l, m); ns[c].rs = build(m+1, r);
  }
  return c;
}
int query(int c, int p, int l, int r, int L, int R){ // <= p
  if(!c)return 0;
  if(l <= L && R <= r)return lower(ns[c].root, p);
  else{
    int M = (L+R)>>1, ret = 0;
    if(l <= M)ret += query(ns[c].ls, p, l, r, L, M);
    if(r > M)ret += query(ns[c].rs, p, l, r, M+1, R);
    return ret;
  }
}
void update(int c, int p, int v, int L, int R){
  if(!c)return;
  ns[c].root = erase(ns[c].root, a[p]);
  ns[c].root = insert(ns[c].root, v);
  if(L == R && L == p)return;
  int M = (L+R)>>1;
  if(p <= M)update(ns[c].ls, p, v, L, M);
  else update(ns[c].rs, p, v, M+1, R);
}
int n;
inline 
int option1(int l, int r, int v){ // [l, r] rank
  return query(1, v-1, l, r, 1, n)+1;
}
int option2(int l, int r, int k){ // [l, r] kth
  int ans = 0, x = 0, y = 1e8;
  while(x <= y){
    int m = (x+y)>>1;
    if(query(1, m, l, r, 1, n) >= k){
      ans = m;
      y = m-1;
    }else x = m+1;
  }
  return ans;
}
inline 
void option3(int p, int v){ //modfity a[p] = v
  update(1, p, v, 1, n);
  a[p] = v;
}
inline 
int option4(int l, int r, int v){ //prev in [l, r] of v
  return option2(l, r, option1(l, r, v)-1); 
}
inline 
int option5(int l, int r, int v){ //succ in [l, r] of v
  return option2(l, r, option1(l, r, v+1));
}
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char getc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;
  }
  template<typename T>
  void splay(T &r){
    char c; bool s = false;
    while((c = getc())){
      if(c >= '0' && c <= '9'){
        r = c^0x30; break;
      }else if(c == '-')s = true;
    }while(isdigit(c = getc()))
      r = ((r+(r<<2))<<1)+(c^0x30);
    if(s)r = -r;
  }
}using IO::splay;
int main(){
//  freopen("test_data.txt", "r", stdin);
  freopen("psh.in", "r", stdin);
  freopen("psh.out", "w", stdout);
  splay(n); int m; splay(m);
  for(int i = 1; i <= n; i++)splay(a[i]);
  build(1, n);
  while(m--){
    int op; splay(op);
    int l, r, k, p;
    switch(op){
      case 1:{
        splay(l); splay(r); splay(k);
        printf("%d\n", option1(l, r, k));
      }break;
      case 2:{
        splay(l); splay(r); splay(k);
        printf("%d\n", option2(l, r, k));
      }break;
      case 3:{
        splay(p); splay(k);
        option3(p, k);
      }break;
      case 4:{
        splay(l); splay(r); splay(k);
        printf("%d\n", option4(l, r, k));
      }break;
      case 5:{
        splay(l); splay(r); splay(k);
        printf("%d\n", option5(l, r, k));
      }break;
    }
  }
  return 0;
}