「BZOJ3196」JoyOI 1730 二逼平衡树

2014年4月20日11,4150

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行，表示查询结果

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

Sample Output

2
4
3
4
9

题解

学了树套树就来水一水。。。

写完整个人都二逼了，突然发现这几天我bzoj的rank掉了。。。

这题重复结点的处理和普通平衡树相同

不注意就是一直50分

一个数的rank是比它小的数的个数+1

#include<iostream>
#include<cstdlib>
#include<cstdio>
#define inf 100000000
#define N 200001
#define M 3000001
using namespace std;
int n,m,sz,tmp,a[N];
int ls[M],rs[M],rnd[M],v[M],s[M],w[M];
int root[N];
void update(int k)
{s[k]=s[ls[k]]+s[rs[k]]+w[k];}
void rturn(int &k)
{int t=ls[k];ls[k]=rs[t];rs[t]=k;s[t]=s[k];update(k);k=t;}
void lturn(int &k)
{int t=rs[k];rs[k]=ls[t];ls[t]=k;s[t]=s[k];update(k);k=t;}
void insert(int &k,int num)
{
    if(!k){k=++sz;s[k]=w[k]=1;v[k]=num;rnd[k]=rand();return;}
    s[k]++;
    if(num==v[k])w[k]++;
    else if(num<v[k]){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);}
    else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);}
}
void del(int &k,int num)
{
    if(v[k]==num)
    {
        if(w[k]>1){w[k]--;s[k]--;return;}
        if(ls[k]*rs[k]==0)k=ls[k]+rs[k];
        else if(rnd[ls[k]]<rnd[rs[k]]){rturn(k);del(k,num);}
        else {lturn(k);del(k,num);}
    }
    else if(num<v[k])
       {del(ls[k],num);s[k]--;}
    else {del(rs[k],num);s[k]--;}
}
void build(int k,int l,int r,int x,int num)
{
    insert(root[k],num);
    if(l==r)return;
    int mid=(l+r)>>1;
    if(x<=mid)build(k<<1,l,mid,x,num);
    else build(k<<1|1,mid+1,r,x,num);
}
void ask_rank(int k,int num)
{
    if(!k)return;
    if(num==v[k]){tmp+=s[ls[k]];return;}
    else if(num<v[k])ask_rank(ls[k],num);
    else {tmp+=s[ls[k]]+w[k];ask_rank(rs[k],num);}
}
void get_rank(int k,int l,int r,int x,int y,int num)
{
    if(l==x&&r==y){ask_rank(root[k],num);return;}
    int mid=(l+r)>>1;
    if(mid>=y)get_rank(k<<1,l,mid,x,y,num);
    else if(mid<x)get_rank(k<<1|1,mid+1,r,x,y,num);
    else
    {
        get_rank(k<<1,l,mid,x,mid,num);
        get_rank(k<<1|1,mid+1,r,mid+1,y,num);
    }
}
void get_index(int x,int y,int z)
{
    int l=0,r=inf,ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        tmp=1;get_rank(1,1,n,x,y,mid);
        if(tmp<=z){l=mid+1;ans=mid;}
        else r=mid-1;
        }
    printf("%d\n",ans);
}
void change(int k,int l,int r,int x,int num,int y)
{
    del(root[k],y);
    insert(root[k],num);
    if(l==r)return;
    int mid=(l+r)>>1;
    if(x<=mid)change(k<<1,l,mid,x,num,y);
    else change(k<<1|1,mid+1,r,x,num,y);
}
void before(int k,int num)
{
    if(!k)return;
    if(v[k]<num){tmp=max(v[k],tmp);before(rs[k],num);}
    else before(ls[k],num);
}
void after(int k,int num)
{
    if(!k)return;
    if(v[k]>num){tmp=min(v[k],tmp);after(ls[k],num);}
    else after(rs[k],num);
}
void ask_after(int k,int l,int r,int x,int y,int num)
{
    if(l==x&&r==y){after(root[k],num);return;}
    int mid=(l+r)>>1;
    if(mid>=y)ask_after(k<<1,l,mid,x,y,num);
    else if(mid<x)ask_after(k<<1|1,mid+1,r,x,y,num);
    else
    {
        ask_after(k<<1,l,mid,x,mid,num);
        ask_after(k<<1|1,mid+1,r,mid+1,y,num);
    }
}
void ask_before(int k,int l,int r,int x,int y,int num)
{
    if(l==x&&r==y){before(root[k],num);return;}
    int mid=(l+r)>>1;
    if(mid>=y)ask_before(k<<1,l,mid,x,y,num);
    else if(mid<x)ask_before(k<<1|1,mid+1,r,x,y,num);
    else
    {
        ask_before(k<<1,l,mid,x,mid,num);
        ask_before(k<<1|1,mid+1,r,mid+1,y,num);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)build(1,1,n,i,a[i]);
    for(int i=1;i<=m;i++)
    {
        int f;scanf("%d",&f);
        int x,y,k;
        switch(f)
        {
            case 1:scanf("%d%d%d",&x,&y,&k);tmp=1;get_rank(1,1,n,x,y,k);printf("%d\n",tmp);break;
            case 2:scanf("%d%d%d",&x,&y,&k);get_index(x,y,k);break;
            case 3:scanf("%d%d",&x,&y);change(1,1,n,x,y,a[x]);a[x]=y;break;
            case 4:scanf("%d%d%d",&x,&y,&k);tmp=0;ask_before(1,1,n,x,y,k);printf("%d\n",tmp);break;
            case 5:scanf("%d%d%d",&x,&y,&k);tmp=inf;ask_after(1,1,n,x,y,k);printf("%d\n",tmp);break;
            } 
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

#include<iostream>

#include<cstdlib>

#include<cstdio>

#define inf 100000000

#define N 200001

#define M 3000001

using namespace std;

int n,m,sz,tmp,a[N];

int ls[M],rs[M],rnd[M],v[M],s[M],w[M];

int root[N];

void update(int k)

{s[k]=s[ls[k]]+s[rs[k]]+w[k];}

void rturn(int &k)

{int t=ls[k];ls[k]=rs[t];rs[t]=k;s[t]=s[k];update(k);k=t;}

void lturn(int &k)

{int t=rs[k];rs[k]=ls[t];ls[t]=k;s[t]=s[k];update(k);k=t;}

void insert(int &k,int num)

{

if(!k){k=++sz;s[k]=w[k]=1;v[k]=num;rnd[k]=rand();return;}

s[k]++;

if(num==v[k])w[k]++;

else if(num<v[k]){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);}

else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);}

}

void del(int &k,int num)

{

if(v[k]==num)

{

if(w[k]>1){w[k]--;s[k]--;return;}

if(ls[k]*rs[k]==0)k=ls[k]+rs[k];

else if(rnd[ls[k]]<rnd[rs[k]]){rturn(k);del(k,num);}

else {lturn(k);del(k,num);}

}

else if(num<v[k])

{del(ls[k],num);s[k]--;}

else {del(rs[k],num);s[k]--;}

}

void build(int k,int l,int r,int x,int num)

{

insert(root[k],num);

if(l==r)return;

int mid=(l+r)>>1;

if(x<=mid)build(k<<1,l,mid,x,num);

else build(k<<1|1,mid+1,r,x,num);

}

void ask_rank(int k,int num)

{

if(!k)return;

if(num==v[k]){tmp+=s[ls[k]];return;}

else if(num<v[k])ask_rank(ls[k],num);

else {tmp+=s[ls[k]]+w[k];ask_rank(rs[k],num);}

}

void get_rank(int k,int l,int r,int x,int y,int num)

{

if(l==x&&r==y){ask_rank(root[k],num);return;}

int mid=(l+r)>>1;

if(mid>=y)get_rank(k<<1,l,mid,x,y,num);

else if(mid<x)get_rank(k<<1|1,mid+1,r,x,y,num);

else

{

get_rank(k<<1,l,mid,x,mid,num);

get_rank(k<<1|1,mid+1,r,mid+1,y,num);

}

void get_index(int x,int y,int z)

{

int l=0,r=inf,ans;

while(l<=r)

{

int mid=(l+r)>>1;

tmp=1;get_rank(1,1,n,x,y,mid);

if(tmp<=z){l=mid+1;ans=mid;}

else r=mid-1;

}

printf("%d\n",ans);

}

void change(int k,int l,int r,int x,int num,int y)

{

del(root[k],y);

insert(root[k],num);

if(l==r)return;

int mid=(l+r)>>1;

if(x<=mid)change(k<<1,l,mid,x,num,y);

else change(k<<1|1,mid+1,r,x,num,y);

}

void before(int k,int num)

{

if(!k)return;

if(v[k]<num){tmp=max(v[k],tmp);before(rs[k],num);}

else before(ls[k],num);

}

void after(int k,int num)

{

if(!k)return;

if(v[k]>num){tmp=min(v[k],tmp);after(ls[k],num);}

else after(rs[k],num);

}

void ask_after(int k,int l,int r,int x,int y,int num)

{

if(l==x&&r==y){after(root[k],num);return;}

int mid=(l+r)>>1;

if(mid>=y)ask_after(k<<1,l,mid,x,y,num);

else if(mid<x)ask_after(k<<1|1,mid+1,r,x,y,num);

else

{

ask_after(k<<1,l,mid,x,mid,num);

ask_after(k<<1|1,mid+1,r,mid+1,y,num);

}

void ask_before(int k,int l,int r,int x,int y,int num)

{

if(l==x&&r==y){before(root[k],num);return;}

int mid=(l+r)>>1;

if(mid>=y)ask_before(k<<1,l,mid,x,y,num);

else if(mid<x)ask_before(k<<1|1,mid+1,r,x,y,num);

else

{

ask_before(k<<1,l,mid,x,mid,num);

ask_before(k<<1|1,mid+1,r,mid+1,y,num);

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)scanf("%d",&a[i]);

for(int i=1;i<=n;i++)build(1,1,n,i,a[i]);

for(int i=1;i<=m;i++)

{

int f;scanf("%d",&f);

int x,y,k;

switch(f)

{

case 1:scanf("%d%d%d",&x,&y,&k);tmp=1;get_rank(1,1,n,x,y,k);printf("%d\n",tmp);break;

case 2:scanf("%d%d%d",&x,&y,&k);get_index(x,y,k);break;

case 3:scanf("%d%d",&x,&y);change(1,1,n,x,y,a[x]);a[x]=y;break;

case 4:scanf("%d%d%d",&x,&y,&k);tmp=0;ask_before(1,1,n,x,y,k);printf("%d\n",tmp);break;

case 5:scanf("%d%d%d",&x,&y,&k);tmp=inf;ask_after(1,1,n,x,y,k);printf("%d\n",tmp);break;

}

return 0;

}

« 「zoj2112」Dynamic Rankings 「CF413E」Maze 2D »

hzwer.com _ Home | http://hzwer.com

「BZOJ3196」JoyOI 1730 二逼平衡树

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论