| 记录编号 |
99608 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[TYVJ1730]二逼平衡树 |
最终得分 |
100 |
| 用户昵称 |
 OI永别 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
3.208 s |
| 提交时间 |
2014-04-28 21:18:33 |
内存使用 |
40.37 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1050010
struct arr{
int l,r,root;
}t[N];
struct aerr{
int l,r,dat,ran;
int ll,rr;
}t1[N];
int n,m;
int a[N];
int size = 0;
bool flag = 0;
void read(int &x){
bool hx=0;
char ch;
while ((ch=getchar())&& (ch>'9' || ch<'0')){
if (ch=='-')hx=1;
};
x=ch-'0';
while ((ch=getchar())&& (ch<='9' && ch>='0'))x=x*10+ch-'0';
if (hx)x=-x;
}
void right(int &x){
int tem = t1[x].r;
t1[x].r = t1[tem].l;
t1[tem].l = x;
t1[x].rr = t1[tem].ll;
t1[tem].ll = t1[x].ll + t1[x].rr + 1;
x = tem;
return;
}
void left(int &x){
int tem = t1[x].l;
t1[x].l = t1[tem].r;
t1[tem].r = x;
t1[x].ll = t1[tem].rr;
t1[tem].rr = t1[x].ll + t1[x].rr + 1;
x = tem;
return;
}
void insert(int & x,int y){
if (!x){
x = ++size;
t1[x].l = t1[x].r = 0;
t1[x].ll = t1[x].rr = 0;
t1[x].dat = y;
t1[x].ran = rand()*rand();
}
else{
if (y >= t1[x].dat){
insert(t1[x].r,y);
t1[x].rr ++;
if (t1[x].ran > t1[t1[x].r].ran) right(x);
}
else{
insert(t1[x].l,y);
t1[x].ll ++;
if (t1[x].ran > t1[t1[x].l].ran) left(x);
}
}
return;
}
void build(int p,int l,int r){
t[p].l = l,t[p].r = r;
if (l == r){
insert(t[p].root,a[l]);
return;
}
for (int i = l; i <= r; i++){
insert(t[p].root,a[i]);
}
int mid = (l + r) >> 1;
build(p << 1,l,mid);
build((p << 1)+ 1,mid + 1,r);
return;
}
int ask(int x,int y){
if (! x) return 0;
if (t1[x].dat == y) {
flag = 1;
}
if (t1[x].dat >= y){
return ask(t1[x].l,y);
}
else return t1[x].ll + 1 + ask(t1[x].r,y);
}
int asknum(int p,int x,int y,int z){
if (t[p].l >= x && t[p].r <= y){
int tem;
tem = ask(t[p].root,z);
return tem;
}
int mid = (t[p].l + t[p].r) >> 1;
int ans = 0;
if (mid >= x) ans += asknum(p << 1,x,y,z);
if (mid < y) ans += asknum((p << 1) + 1,x,y,z);
return ans;
}
int askrank(int p,int x,int y,int z){
int tt = t[p].root;
flag = 0;
int ans;
int tem = asknum(1,x,y,t1[tt].dat) + 1;
while (tt){
if (tem <= z){
if (flag) ans = t1[tt].dat;
if (tem == z && flag) break;
if (tt != t1[tt].r){
flag = 0;
tem = asknum(1,x,y,t1[t1[tt].r].dat) + 1;
}
tt = t1[tt].r;
}
else{
if (tt != t1[tt].l){
flag = 0;
tem = asknum(1,x,y,t1[t1[tt].l].dat) + 1;
}
tt = t1[tt].l;
}
}
return ans;
}
void del(int &x,int y){
if (t1[x].dat == y){
if (t1[x].l == 0 || t1[x].r == 0){
if (t1[x].l == 0){
x = t1[x].r;
return;
}
if (t1[x].r == 0){
x = t1[x].l;
return;
}
}
else{
if (t1[t1[x].l].ran >= t1[t1[x].r].ran){
right(x);
t1[x].ll--;
del(t1[x].l,y);
}
else{
left(x);
t1[x].rr --;
del(t1[x].r,y);
}
}
}
else{
if (t1[x].dat < y) {
t1[x].rr --;
del(t1[x].r,y);
}
else{
t1[x].ll --;
del(t1[x].l,y);
}
}
}
void change(int p,int x,int y){
if (t[p].l == t[p].r){
del(t[p].root,t1[t[p].root].dat);
insert(t[p].root,y);
return;
}
del(t[p].root,a[x]);
insert(t[p].root,y);
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid) change(p << 1,x,y);
if (x > mid) change((p << 1)+ 1,x,y);
return;
}
int pre(int x,int y){
if (! x) return y;
int ans = 0;
if (y <= t1[x].dat) ans = pre(t1[x].l,y);
else{
ans = pre(t1[x].r,y);
if (ans == y) ans = t1[x].dat;
}
return ans;
}
int askpre(int p,int x,int y,int z){
if (t[p].l >= x && t[p].r <= y){
int tem = pre(t[p].root,z);
if (tem == z) tem = -0x3f;
return tem;
}
int ans = -0x3f,mid = (t[p].l + t[p].r) >> 1;
if (x <= mid) ans = max(ans,askpre(p << 1,x,y,z));
if (y > mid) ans = max(ans,askpre((p << 1) + 1,x,y,z));
if (ans == z) ans = -0x3f;
return ans;
}
int succ(int x,int y){
if (!x) return y;
int ans = 0;
if (y >= t1[x].dat) ans = succ(t1[x].r,y);
else{
ans = succ(t1[x].l,y);
if (ans == y) ans = t1[x].dat;
}
return ans;
}
int asksucc(int p,int x,int y,int z){
if (t[p].l >= x && t[p].r <= y){
int tem = succ(t[p].root,z);
if (tem == z) tem = 0x7fffffff;
return tem;
}
int ans = 0x7fffffff,mid = (t[p].l + t[p].r) >> 1;
if (x <= mid) ans = min(ans,asksucc(p << 1,x,y,z));
if (y > mid) ans = min(ans,asksucc((p << 1)+1,x,y,z));
if (ans == z) ans = 0x7fffffff;
return ans;
}
int main(){
freopen("psh.in","r",stdin);
freopen("psh.out","w",stdout);
read(n);read(m);
for (int i = 1; i <= n; i++) read(a[i]);//scanf("%d",&a[i]);
build(1,1,n);
int cc,x,y,z;
while (m--){
scanf("%d",&cc);
switch (cc){
case 1:{
read(x);read(y);read(z);
//scanf("%d%d%d",&x,&y,&z);
int ans = asknum(1,x,y,z);
printf("%d\n",ans + 1);
break;
}
case 2:{
read(x);read(y);read(z);
//scanf("%d%d%d",&x,&y,&z);
int ans = askrank(1,x,y,z);
printf("%d\n",ans);
break;
}
case 3:{
read(x);read(z);
// scanf("%d%d",&x,&z);
change(1,x,z);
a[x] = z;
break;
}
case 4:{
read(x);read(y);read(z);
// scanf("%d%d%d",&x,&y,&z);
int ans = askpre(1,x,y,z);
printf("%d\n",ans);
break;
}
case 5:{
read(x);read(y);read(z);
//scanf("%d%d%d",&x,&y,&z);
int ans = asksucc(1,x,y,z);
printf("%d\n",ans);
break;
}
}
}
return 0;
}