题解：P2286 宠物收养场
xxseven
·
·
题解
这道题我是拿权值树状数组搭配离散化 O(n \log n) 水过的，码量很小并且只用一棵树。这篇题解里就会讲解这种做法。
前言：
并非所有需要平衡树的题目都能用权值树状数组代替。
受限于树状数组的性质，如果需要处理本题这样值域较大的数据，需要先进行离散化，因此必须离线。如果题目强制要求在线，那么权值树状数组就只能处理值域较小的数据了。
解法：
以下记树状数组维护的桶为 g,树状数组为 t。
分析题意，发现这道题要实现这么几个操作：插入，删除，求前驱，求后继。
权值树状数组上的插入和删除都很简单，插入即 g_i \gets g_i+1，删除即g_i \gets g_i-1。
那么，问题的关键在于在 O(\log n) 的复杂度内求出前驱和后继。
记 krank(k) 为当前树状数组中第 k 小的数，sum(k) 为当前树状数组中权值不大于 k 的数的数量，那么：
$k$ 的后继可以表示为 $krank(sum(k)+1)$。
现在，我们就把求前驱和后继的问题转化为了求一个权值树状数组上第 $k$ 小的问题。
对于这个问题，可以利用树状数组的性质倍增解决。
对于一个树状数组上的位置 $x$ ,如果加上一个小于 $\operatorname{lowbit}(x)$ 的 $2^i$ ，那么 $sum(x)$ 增加的值正好就是跳过的一片区域的总权值。
例如：$sum(6)-sum(4)=g_5+g_6=t_6$。
因此考虑倍增，从 $0$ 开始依次尝试让 $x$ 往后跳 $2^{\log n},2^{\log n-1},2^{\log n-2},...,2^0$，每次跳跃都将一个数加上树状数组对应位置的权值，根据当前数的大小来判断是否能执行本次跳跃。
给出倍增求 $krank$ 的方法如下，其中 $T= \log_2 n$：
```cpp
int krank(int k){
int pos=0,val=0;
for(int i=T,x,y;i>=0;--i){
x=pos+(1<<i);
if(x>bn) continue;
y=val+t[x];
if(y<k) pos=x,val=y;
}
return b[pos+1];
}
```
此外，对于当前树状数组中存储的是宠物还是领养者，可以使用正负数来做处理，这样可以只使用一个树状数组就实现按照题意的模拟。
代码和注释如下：
```cpp
#include<bits/stdc++.h>
#define ID(y) lower_bound(b+1,b+bn+1,y)-b
#define h(x) ((x==1)?-1:1) //用h(x)转换类型，宠物记作1，领养者记作-1
#define int long long
using namespace std;
const int N=8e4+5,inf=1e12;
int t[N],a[N],b[N],bn,T;
int n,cnt,ans;
struct node{
int op,v;
}f[N];
int lowbit(int x){
return x&(-x);
}
void add(int pos,int x){
while(pos<=bn){
t[pos]+=x;
pos+=lowbit(pos);
}
}
int sum(int pos){
int res=0;
while(pos){
res+=t[pos];
pos-=lowbit(pos);
}
return res;
}
int krank(int k){
if(k<1) return -inf;
if(k>abs(cnt)) return inf; //特判不存在前驱或后继的情况
int pos=0,val=0;
for(int i=T,x,y;i>=0;--i){
x=pos+(1<<i);
if(x>bn) continue;
y=val+t[x];
if(y<k) pos=x,val=y;
}
return b[pos+1];
}
signed main(){
cin>>n;
for(int op,v,i=1;i<=n;++i){
cin>>op>>v;
f[i].op=op; f[i].v=v;
a[++cnt]=v; b[cnt]=v;
}
sort(b+1,b+n+1);
bn=unique(b+1,b+n+1)-b-1; T=log2(bn); cnt=0;
for(int i=1,x,y,A,B;i<=n;++i){
x=f[i].op; y=f[i].v;
if(h(x)*cnt<0){ //根据乘法的性质，两者之积为负数即代表加入元素与树中元素不同类
A=krank(sum(ID(y)-1)); B=krank(sum(ID(y))+1);
if(y-A<=B-y) add(ID(A),-1),ans+=(y-A);
else add(ID(B),-1),ans+=(B-y);
}
else add(ID(y),1);
cnt+=h(x); //利用cnt的大小和正负存储当前树状数组中元素的类型和个数
}
cout<<ans%1000000;
return 0;
}
```
希望这篇题解能够帮到你！