题目链接: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就是答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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; } |