BZOJ 3196 二逼平衡树
splay 线段树 树套树   发布于 2017-04-06   208人围观  0条评论
splay 线段树 树套树   发表于 2017-04-06   208人围观  0条评论

### Description

1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

### Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

2
4
3
4
9

### HINT

1.n和m的数据范围：n,m<=50000
2.序列中每个数的数据范围：[0,1e8]
3.虽然原题没有，但事实上5操作的k可能为负数

### 代码

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 5e4+5;
const int lg = 30;
const int INF = 2147483647;
int a[maxn],n,m,x,y,z;
struct splay_node{
splay_node *pre,*ch[2];
int siz,cnt,v;
void update();
int get_wh();
void set_ch(int wh,splay_node *child);
}pool[maxn*lg],*null;
int top = 0;
int splay_node::get_wh(){
return pre->ch[0] == this ? 0 : 1;
}
void splay_node::update(){
siz = ch[0]->siz + ch[1]->siz + cnt;
}
void splay_node::set_ch(int wh,splay_node *child){
ch[wh] = child;
if(child != null)child->pre = this;
update();
}
splay_node *get_new(int value){
splay_node *newone = pool + ++top;
newone->siz = newone->cnt = 1;
newone->pre = newone->ch[0] = newone->ch[1] = null;
newone->v = value;
return newone;
}
struct segment{
segment *lc,*rc;
int l,r;
splay_node *root;
void rotate(splay_node *&now){
splay_node *fa = now->pre,*grand = now->pre->pre;
int wh = now->get_wh();
fa->set_ch(wh,now->ch[wh^1]);
now->set_ch(wh^1,fa);
now->pre = grand;
if(grand != null)
grand->ch[grand->ch[0] == fa ? 0 : 1] = now;
}
void splay(splay_node *now,splay_node *tar){
for(;now->pre != tar;rotate(now))
if(now->pre->pre != tar)now->get_wh() == now->pre->get_wh() ? rotate(now->pre) : rotate(now);
if(tar == null)root = now;
}
void insert(int pos){
splay_node *now = root;
splay_node *last = now;
while(now != null){
last = now;
if(now->v == a[pos]){
now->cnt++;
now->siz++;
splay(now,null);
return;
}
else if(now->v < a[pos])now = now->ch[1];
else now = now->ch[0];
}
if(last == null)root = get_new(a[pos]);
else{
splay_node *newone = get_new(a[pos]);
last->set_ch(last->v < newone->v ? 1 : 0,newone);
splay(newone,null);
}
return;
}
splay_node *find(splay_node *now,int value){
if(now->v == value)return now;
else if(now->v < value)return find(now->ch[1],value);
else return find(now->ch[0],value);
}
void del(int value){
splay_node *now = find(root,value);
splay(now,null);
if(now->cnt > 1){
now->siz -= 1;
now->cnt -= 1;
return;
}
if(now->ch[0] == null && now->ch[1] == null)root = null;
else if(now->ch[0] == null && now->ch[1] != null){
now->ch[1]->pre = null;
root = now->ch[1];
return;
}
else if(now->ch[1] == null && now->ch[0] != null){
now->ch[0]->pre = null;
root = now->ch[0];
return;
}
else{
splay_node *tar = now->ch[0];
while(tar->ch[1] != null)tar = tar->ch[1];
splay(tar,now);
tar->set_ch(1,now->ch[1]);
tar->pre = null;
root = tar;
return;
}
}
void get_splay(){
root = null;
insert(0);
for(int i = l;i <= r;++i)insert(i);
return;
}
int get_pre(int value){
splay_node *now = root;
int ret = -INF;
while(now != null){
if(now->v >= value)now = now->ch[0];
else{
ret = now->v;
now = now->ch[1];
}
}
return ret;
}
int get_next(int value){
splay_node *now = root;
int ret = INF;
while(now != null){
if(now->v <= value)now = now->ch[1];
else{
ret = now->v;
now = now->ch[0];
}
}
return ret;
}
void get_rank(int value,int &lr,int &rr){
splay_node *now = root;
while(now != null){
if(now->v == value){
lr += now->ch[0]->siz;
rr += now->cnt + now->ch[0]->siz;
break;
}
else if(now->v > value)now = now->ch[0];
else{
lr += now->ch[0]->siz + now->cnt;
rr += now->ch[0]->siz + now->cnt;
now = now->ch[1];
}
}
return;
}
}nil[maxn<<2],*nul,*rot;
int tot = 0;
void init(){
null = pool;
null->pre = null->ch[0] = null->ch[1] = null;
null->v = null->siz = null->cnt = 0;
nul = nil;
nul->l = nul->r = 0;
nul->lc = nul->rc = nul;
nul->root = null;
rot = nul;
}
segment *build(int l,int r){
segment *now = nil + ++tot;
now->l = l;now->r = r;
now->lc = now->rc = nul;
now->get_splay();
if(l == r)return now;
int mid = (l + r) >> 1;
now->lc = build(l,mid);
now->rc = build(mid+1,r);
return now;
}
void update(segment *now,int pos,int pre_value){
now->del(pre_value);
now->insert(pos);
if(now->l == now->r)return;
int mid = (now->l + now->r) >> 1;
if(pos <= mid)update(now->lc,pos,pre_value);
else if(pos > mid)update(now->rc,pos,pre_value);
return;
}
int query_pre(segment *now,int l,int r,int value){
if(now->l >= l && now->r <= r)
return now->get_pre(value);
int mid = (now->l + now->r) >> 1;
int ret = -INF;
if(l <= mid)ret = max(ret,query_pre(now->lc,l,r,value));
if(r > mid)ret = max(ret,query_pre(now->rc,l,r,value));
return ret;
}
int query_next(segment *now,int l,int r,int value){
if(now->l >= l && now->r <= r)
return now->get_next(value);
int mid = (now->l + now->r) >> 1;
int ret = INF;
if(l <= mid)ret = min(ret,query_next(now->lc,l,r,value));
if(r > mid)ret = min(ret,query_next(now->rc,l,r,value));
return ret;
}
void query_rank(segment *now,int l,int r,int value,int &rank1,int &rank2){
if(now->l >= l && now->r <= r){
now->get_rank(value,rank1,rank2);
return;
}
int mid = (now->l + now->r) >> 1;
if(l <= mid)query_rank(now->lc,l,r,value,rank1,rank2);
if(r > mid)query_rank(now->rc,l,r,value,rank1,rank2);
return;
}
void solve(int l,int r,int k){
int rank1 = 0,rank2 = 0;
int L = 0,R = 1e8,mid = 0;
while(L <= R){
mid = (L + R) >> 1;
rank1 = rank2 = 0;
query_rank(rot,l,r,mid,rank1,rank2);
rank1 += 1;
if(k >= rank1 && k <= rank2)break;
if(k < rank1)R = mid - 1;
else if(k > rank2)L = mid + 1;
}
printf("%d\n",mid);
return;
}
int opt;
int main(){
init();
n = get_num();
m = get_num();
for(int i = 1;i <= n;++i)
a[i] = get_num();
a[0] = INF;
rot = build(1,n);
while(m--){
opt = get_num();
if(opt == 3){
x = get_num();y = get_num();
z = a[x];
a[x] = y;
update(rot,x,z);
continue;
}
x = get_num();y = get_num();z = get_num();
if(opt == 1){
int rank1 = 0,rank2 = 0;
query_rank(rot,x,y,z,rank1,rank2);
printf("%d\n",rank1+1);
continue;
}
if(opt == 2){
solve(x,y,z);
continue;
}
if(opt == 4){
printf("%d\n",query_pre(rot,x,y,z));
continue;
}
if(opt == 5){
printf("%d\n",query_next(rot,x,y,z));
}
}
return 0;
}﻿​```

0 条评论