bzoj 3065: 带插入区间K小值树套树

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3065

替罪羊树套权值线段树，照着hzwer写的…我说一说自己的理解吧

替罪羊树的每个点维护的信息是整颗子树所包含的那个区间，然后每个点有一颗权值线段树，储存它们所维护的那个区间里的权值分布情况，防止MLE，我们对权值线段树进行动态开点以及内存回收，在build替罪羊树时，是暴力进行插入每个点的操作的，复杂度有点高但不会爆炸，应该是O(nlogn^3)的吧..

插入操作：和正常的替罪羊插入时没有什么区别，只不过在经过每一个点的时候，需要进行一次给当前节点线段树的插入，由于题目说的是在第k个前插入一个数，所以我们将k–，这样方便进行计算

修改操作：就是相当于先插入新的值，再找到第x个数是什么，然后进行删除，可以一次递归完成，每次在经过这个点时，进行插入，然后判断左子树线段树中的点数+1（就是左子树大小+1）与x的关系，如果相等就可以记录一下后进行修改与返回，我们可以将返回值设为我们要删除的值，这样上面的层就可以简单地知道我们要删除哪个

查询操作：我们需要找到要进行查询的所有的区间，所以用两个数组记录【一个点及其子树完全被包含的点】和【子树不完全被包含的点】，为了方便查询，第一个数组里储存那个点的线段树的根节点，第二个数组里储存那个点的值，顺便再将k–，这样就不用考虑它自己了，在二分时就只需要考虑左子树大小就好了。查询时进行二分，l<r，由于线段树的两个端点和我们二分的边界完全一致，所以对于第一个数组，每次直接加上每颗线段树上的左儿子的size，而对于第二个数组，遍历一遍判断是否在区间内，加上就好了。计算完我们目前二分的权值内的点数后，如果大于我们要找的k个，说明答案在左边，r=mid，线段树上往左走，也就是第一个数组内地点全都变成它的左儿子。否则的话，说明在右边，l=mid+1，k-=点数，线段树的点也往右儿子走一下。当l==r时，就相当于找到了那个点，最后的l或者r就是答案。

#include<bits/stdc++.h>

#define maxn 70070
#define pb push_back
#define db double

using namespace std;

inline int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*y;
}

struct node{
    int l,r,sz;
}tree[10000010];

int n,m,Root,tot,ans,not_bal,fa;
int val[maxn],num[maxn],root[maxn],son[maxn][2];
vector<int>bin,reb,v1,v2;
db alpha=0.75;

inline void push_up(int now){
    int l=tree[now].l,r=tree[now].r;
    tree[now].sz=tree[l].sz+tree[r].sz;
}

inline bool balance(int now){
    return tree[root[now]].sz*1.0*alpha>max(tree[root[son[now][0]]].sz,tree[root[son[now][1]]].sz)*1.0;
}

void reuse(int &now){
    if(!now)return;
    bin.pb(now);
    reuse(tree[now].l);
    reuse(tree[now].r);
    tree[now].sz=0;
    now=0;
}

inline int newnode(){
    if(!bin.size())return ++tot;
    else{
        int ret=bin.back();
        bin.pop_back();
        return ret;
    }
}

void Insert(int &now,int l,int r,int k,int f){
    if(!now)now=newnode();
    if(l==r){
        tree[now].sz+=f;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid)Insert(tree[now].l,l,mid,k,f);
    else Insert(tree[now].r,mid+1,r,k,f);
    push_up(now);
    if(!tree[now].sz)reuse(now);
}

void build(int &now,int l,int r){
    if(l>r)return;
    if(l==r){
        now=num[l];
        Insert(root[now],0,70000,val[now],1);
        return;
    }
    int mid=(l+r)/2;
    now=num[mid];
    build(son[now][0],l,mid-1);
    build(son[now][1],mid+1,r);
    for(int i=l; i<=r; i++)Insert(root[now],0,70000,val[num[i]],1);
}

void dfs(int &now){
    if(!now)return;
    reuse(root[now]);
    dfs(son[now][0]);
    reb.pb(now);
    dfs(son[now][1]);
    now=0;
}

void rebuild(int &now){
    dfs(now);
    for(int i=1; i<=reb.size(); i++)num[i]=reb[i-1];
    build(now,1,reb.size());
    reb.clear();
}

void Ins(int &now,int x,int k){
    if(!now){
        now=++n;
        Insert(root[now],0,70000,k,1);
        val[now]=k;
        return;
    }
    Insert(root[now],0,70000,k,1);
    int sz=tree[root[son[now][0]]].sz;
    if(sz>=x)Ins(son[now][0],x,k);
    else Ins(son[now][1],x-sz-1,k);
    if(balance(now)){
        if(not_bal){
            if(son[now][0]==not_bal)rebuild(son[now][0]);
            else rebuild(son[now][1]);
            not_bal=0;
        }
    }
    else not_bal=now;
}

void query(int now,int l,int r){
    int mid=tree[root[son[now][0]]].sz+1,R=tree[root[now]].sz;
    if(l==1 && r==R){
        v1.pb(root[now]);
        return;
    }
    if(l<=mid && mid<=r)v2.pb(val[now]);
    if(r<mid)query(son[now][0],l,r);
    else if(l>mid)query(son[now][1],l-mid,r-mid);
    else{
        if(l<mid)query(son[now][0],l,mid-1);
        if(R>mid)query(son[now][1],1,r-mid);
    }
}

int solve(int L,int R,int k){
    v1.clear(),v2.clear();
    query(Root,L,R);k--;
    int l=0,r=70000,s1=v1.size(),s2=v2.size();
    while(l<r){
        int mid=(l+r)/2,sum=0;
        for(int i=0; i<s1; i++)sum+=tree[tree[v1[i]].l].sz;
        for(int i=0; i<s2; i++)if(l<=v2[i] && v2[i]<=mid)sum++;
        if(k<sum){
            for(int i=0; i<s1; i++)v1[i]=tree[v1[i]].l;
            r=mid;
        }
        else{
            for(int i=0; i<s1; i++)v1[i]=tree[v1[i]].r;
            l=mid+1,k-=sum;
        }
    }
    return l;
}

int modify(int now,int x,int k){
    Insert(root[now],0,70000,k,1);
    int del,mid=tree[root[son[now][0]]].sz+1;
    if(x==mid)del=val[now],val[now]=k;
    else if(x<mid)del=modify(son[now][0],x,k);
    else del=modify(son[now][1],x-mid,k);
    Insert(root[now],0,70000,del,-1);
    return del;
}

int main(){
    n=rd();
    for(int i=1; i<=n; i++)val[i]=rd();
    for(int i=1; i<=n; i++)num[i]=i;
    build(Root,1,n);
    m=rd();
    char op[2];
    int x,y,k;
    while(m--){
        scanf("%s",op);
        x=rd()^ans,y=rd()^ans;
        if(op[0]=='Q'){
            k=rd()^ans;
            ans=solve(x,y,k);
            printf("%d\n",ans);
        }
        if(op[0]=='M')modify(Root,x,y);
        if(op[0]=='I'){
            not_bal=0;
            Ins(Root,x-1,y);
            if(not_bal)rebuild(Root),not_bal=0;
        }
    }
    
    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

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

#include<bits/stdc++.h>

#define maxn 70070

#define pb push_back

#define db double

using namespace std;

inline int rd(){

int x=0,y=1;char c=getchar();

while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}

while(isdigit(c))x=x*10+c-'0',c=getchar();

return x*y;

}

struct node{

int l,r,sz;

}tree[10000010];

int n,m,Root,tot,ans,not_bal,fa;

int val[maxn],num[maxn],root[maxn],son[maxn][2];

vector<int>bin,reb,v1,v2;

db alpha=0.75;

inline void push_up(int now){

int l=tree[now].l,r=tree[now].r;

tree[now].sz=tree[l].sz+tree[r].sz;

}

inline bool balance(int now){

return tree[root[now]].sz*1.0*alpha>max(tree[root[son[now][0]]].sz,tree[root[son[now][1]]].sz)*1.0;

}

void reuse(int &now){

if(!now)return;

bin.pb(now);

reuse(tree[now].l);

reuse(tree[now].r);

tree[now].sz=0;

now=0;

}

inline int newnode(){

if(!bin.size())return ++tot;

else{

int ret=bin.back();

bin.pop_back();

return ret;

}

void Insert(int &now,int l,int r,int k,int f){

if(!now)now=newnode();

if(l==r){

tree[now].sz+=f;

return;

}

int mid=(l+r)/2;

if(k<=mid)Insert(tree[now].l,l,mid,k,f);

else Insert(tree[now].r,mid+1,r,k,f);

push_up(now);

if(!tree[now].sz)reuse(now);

}

void build(int &now,int l,int r){

if(l>r)return;

if(l==r){

now=num[l];

Insert(root[now],0,70000,val[now],1);

return;

}

int mid=(l+r)/2;

now=num[mid];

build(son[now][0],l,mid-1);

build(son[now][1],mid+1,r);

for(int i=l; i<=r; i++)Insert(root[now],0,70000,val[num[i]],1);

}

void dfs(int &now){

if(!now)return;

reuse(root[now]);

dfs(son[now][0]);

reb.pb(now);

dfs(son[now][1]);

now=0;

}

void rebuild(int &now){

dfs(now);

for(int i=1; i<=reb.size(); i++)num[i]=reb[i-1];

build(now,1,reb.size());

reb.clear();

}

void Ins(int &now,int x,int k){

if(!now){

now=++n;

Insert(root[now],0,70000,k,1);

val[now]=k;

return;

}

Insert(root[now],0,70000,k,1);

int sz=tree[root[son[now][0]]].sz;

if(sz>=x)Ins(son[now][0],x,k);

else Ins(son[now][1],x-sz-1,k);

if(balance(now)){

if(not_bal){

if(son[now][0]==not_bal)rebuild(son[now][0]);

else rebuild(son[now][1]);

not_bal=0;

}

else not_bal=now;

}

void query(int now,int l,int r){

int mid=tree[root[son[now][0]]].sz+1,R=tree[root[now]].sz;

if(l==1 && r==R){

v1.pb(root[now]);

return;

}

if(l<=mid && mid<=r)v2.pb(val[now]);

if(r<mid)query(son[now][0],l,r);

else if(l>mid)query(son[now][1],l-mid,r-mid);

else{

if(l<mid)query(son[now][0],l,mid-1);

if(R>mid)query(son[now][1],1,r-mid);

}

int solve(int L,int R,int k){

v1.clear(),v2.clear();

query(Root,L,R);k--;

int l=0,r=70000,s1=v1.size(),s2=v2.size();

while(l<r){

int mid=(l+r)/2,sum=0;

for(int i=0; i<s1; i++)sum+=tree[tree[v1[i]].l].sz;

for(int i=0; i<s2; i++)if(l<=v2[i] && v2[i]<=mid)sum++;

if(k<sum){

for(int i=0; i<s1; i++)v1[i]=tree[v1[i]].l;

r=mid;

}

else{

for(int i=0; i<s1; i++)v1[i]=tree[v1[i]].r;

l=mid+1,k-=sum;

}

return l;

}

int modify(int now,int x,int k){

Insert(root[now],0,70000,k,1);

int del,mid=tree[root[son[now][0]]].sz+1;

if(x==mid)del=val[now],val[now]=k;

else if(x<mid)del=modify(son[now][0],x,k);

else del=modify(son[now][1],x-mid,k);

Insert(root[now],0,70000,del,-1);

return del;

}

int main(){

n=rd();

for(int i=1; i<=n; i++)val[i]=rd();

for(int i=1; i<=n; i++)num[i]=i;

build(Root,1,n);

m=rd();

char op[2];

int x,y,k;

while(m--){

scanf("%s",op);

x=rd()^ans,y=rd()^ans;

if(op[0]=='Q'){

k=rd()^ans;

ans=solve(x,y,k);

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

}

if(op[0]=='M')modify(Root,x,y);

if(op[0]=='I'){

not_bal=0;

Ins(Root,x-1,y);

if(not_bal)rebuild(Root),not_bal=0;

}

return 0;

}

everlasting

bzoj 3065: 带插入区间K小值树套树

发表评论取消回复

发表评论 取消回复

发表评论取消回复