0%

浅谈整体二分

Dynamic Rankings来引入该算法(BZOJ 1901,但是个权限题)

题意:

给一个长度为$n$的序列,要你支持两种操作:

  1. 查询区间k-th
  2. 单点修改

不妨先考虑该问题的弱化版-只有查询区间k-th操作

别跟我说主席树主席树空间为$\mathcal O(nlogn)$ ,不够优秀。

对于单个的“查询区间k-th”操作,我们可以二分求解: 假设正在考虑$[l,r]$ ,二分的值为$mid$。统计$x\le mid$ 的$x$数量$cnt$,若$cnt\le k$,则答案在$[l,mid]$中,否则等价于在$[mid+1,r]$中查$(k-cnt)$ -th 。暴力统计需要$\mathcal O(n)$时间,二分$\mathcal O(\log n)$次,处理$m$次询问的时间复杂度$\mathcal O(m\times n\log n)$,不太行。

于是可以使用整体二分:将所有询问一起二分。

假设正在考虑$[l,r]$ ,二分的值为$mid$。

对于每个询问$(l_i,r_i,k_i)$,我们需要回答有多少$x\le mid,l_i\le x\le r_i$.这很容易用树状数组解决:考虑序列中的每个数$x_i$,如果$x_i\le mid$,则在树状数组中$i$位置+1,查询时直接查询$[l_i,r_i]$的区间和即可。

与对一个询问$(l_i,r_i,k_i)$二分类似,我们得到了$x\le mid,l_i\le x\le r_i$ 的$x$数量$cnt$,若$cnt\le k_i$,则这个询问的答案在$[l,mid]$中,否则等价于在$[mid+1,r]$中查$(k-cnt)$ -th 。

将询问分成这两组,递归执行上述过程即可。类似的,对于序列中的数$x_i$,若$x_i \le mid$,则对$[mid+1,r]$的贡献已经计算完,但可能仍对$[l,mid]$有一些贡献,应该和$cnt\le k_i$的询问一起处理;否则应该和$cnt>k_i$的询问一起处理。注意边界,即询问序列为空,和$l=r$的情况(可见代码)

离散化后,需要二分$\mathcal O(\log n)$次,每次的代价是$\mathcal O((n+m)\times \log n)$(无论如何划分,序列+询问总长$=n+m$,总时间复杂度$\mathcal O((n+m)\times \log^2 n)$

为了简化代码,实现时做了一些微小的改动,但与上述内容大同小异。

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

#define MAXN 400011
struct one
{
ll dex,x,y,k;//dex=0表示加入一个数,此时x表示位置,y表示值;dex>0表示询问的编号,x表示l_i,y表示l_i,k表示k_i
}a[MAXN],la[MAXN],ra[MAXN];
ll ans[MAXN];
ll len;
struct BIT{....}t;//树状数组,略
void solve(ll l,ll r,ll begin,ll end)//答案在[l,r]中,操作序列为[begin,end](这里把原序列和询问合并为一个序列,简化了代码)
{
if(begin>end)return;//两个边界
if(l==r)
{
for(ll i=begin;i<=end;++i)ans[a[i].dex]=l;
return;
}
ll mid=(l+r)>>1;
ll itl=0,itr=0;
for(ll i=begin;i<=end;++i)
if(!a[i].dex)//插入一个数
{
if(a[i].y<=mid)la[++itl]=a[i],t.modify(a[i].x,1);//不超过mid,加入左半段并在树状数组中修改
else ra[++itr]=a[i];
}
else
{
ll cnt=t.Qsum(a[i].y)-t.Qsum(a[i].x-1);//区间和
if(cnt>=a[i].k)la[++itl]=a[i];//左半段
else a[i].k-=cnt,ra[++itr]=a[i];//右半段
}
for(ll i=begin;i<=end;++i)
if(!a[i].dex&&a[i].y<=mid)t.modify(a[i].x,-1);//撤销操作
for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];//复制回原序列
for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);//递归求解
}
//以上为整体二分部分,以下为main&离散化
ll fx[MAXN],nn;
ll place(ll val)//找离散化后的位置
{
return std::lower_bound(fx+1,fx+nn+1,val)-fx;
}
int main()
{
ll n=read(),m=read();;
len=n+m;//操作序列总长
for(ll i=1;i<=n;++i)
{
ll val=read();
a[i].dex=0,a[i].x=i,a[i].y=val;
fx[i]=val;
}
std::sort(fx+1,fx+n+1);
nn=std::unique(fx+1,fx+n+1)-fx-1;
for(ll i=1;i<=n;++i)a[i].y=place(a[i].y);
for(ll i=1;i<=m;++i)
{
ll l=read(),r=read(),k=read();
a[n+i].dex=i,a[n+i].x=l,a[n+i].y=r,a[n+i].k=k;//询问
}
solve(1,nn,1,len);//求解
for(ll i=1;i<=m;++i)printf("%lld\n",fx[ans[i]]);
return 0;
}

接下来考虑如何单点修改

假设原位置上的数为$arr_i$,要将其改为$x$,等价于删掉$arr_i,$再加入$x$.删除操作与加入操作的唯一不同就是,在树状数组中单点加时,应该是加-1(加入操作是加1)。其他完全与无修改相同,(但此时加入的数总量为$\mathcal O(n+m)$级别,也就是树状数组要开这么大,所以$\mathcal O(\log n)->\mathcal O(\log (n+m))$)时间复杂度为$O((n+m)\log n\times \log(n+m))$,实测比树套树快5倍左右,并且空间仅为$\mathcal O(n+m)$

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
#define MAXN 500011
struct one
{
ll dex,x,y,k;//dex=-1表示删除,dex=0表示加入,dex>0表示查询
}a[MAXN],la[MAXN],ra[MAXN];
ll ans[MAXN],len;
struct BIT{...}t;
void solve(ll l,ll r,ll begin,ll end)
{
if(begin>end)return;
if(l==r)
{
for(ll i=begin;i<=end;++i)
if(a[i].dex>0)ans[a[i].dex]=l;
return;
}
ll mid=(l+r)>>1,itl=0,itr=0;
for(ll i=begin;i<=end;++i)
{
if(a[i].dex<=0)//删除或加入
{
if(a[i].y<=mid)t.modify(a[i].x,a[i].dex==0?1:-1),la[++itl]=a[i];//在树状数组上删除/加入
else ra[++itr]=a[i];
}
else
{
ll cnt=t.Qsum(a[i].y)-t.Qsum(a[i].x-1);
if(cnt>=a[i].k)la[++itl]=a[i];
else a[i].k-=cnt,ra[++itr]=a[i];
}
}
for(ll i=begin;i<=end;++i)
if(a[i].dex<=0)
{
if(a[i].y<=mid)t.modify(a[i].x,a[i].dex==0?-1:1);//还原树状数组
}
for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);
}

例题:流星 Meteors

首先,为了判断NIE,可以在最后$(k+1)$建一个覆盖所有点inf次的陨石雨,若某个国家的答案为$k+1$就是NIE了。

仍然用整体二分的套路,假设答案在$[l,r]$中,二分的值为$mid$,则考虑$[l,mid]$中的所有陨石雨:容易发现,陨石雨其实就是一个或两个区间加的操作.同时我们需要得到每个位置的陨石数量。也就是区间修改,单点查询,用树状数组维护差分序列即可维护。

扫描每个询问$i$,计算它的每个位置的和$cnt$,与$need_i$比较,若$cnt<need_i$,则应缩小右边界,放入左半段;否则放入右半段并还需要$need_i-cnt$数量的陨石,递归做即可。

时间复杂度$\mathcal O(m\log m\log k)$

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
#define MAXN 300011
struct one
{
ll l,r,val;
}stone[MAXN];//陨石雨的左右边界和陨石数量
std::vector<ll>g[MAXN];//每个国家的基地
ll need[MAXN],ans[MAXN],a[MAXN],la[MAXN],ra[MAXN];//需要的陨石数量
ll n,m;
struct BIT{....}t;//区间修改,单点查询的树状数组

void solve(ll l,ll r,ll begin,ll end)
{
if(begin>end)return;
if(l==r)
{
for(ll i=begin;i<=end;++i)
ans[a[i]]=l;
return;
}
ll mid=(l+r)>>1;
for(ll i=l;i<=mid;++i)
{
ll val=stone[i].val;
if(stone[i].l<=stone[i].r)t.modify(stone[i].l,val),t.modify(stone[i].r+1,-val);//区间加
else t.modify(stone[i].l,val),t.modify(1,val),t.modify(stone[i].r+1,-val);
}
ll itl=0,itr=0;
for(ll i=begin;i<=end;++i)
{
ll cnt=0;
for(std::vector<ll>::iterator it=g[a[i]].begin();it!=g[a[i]].end();++it)
{
cnt+=t.Qsum(*it);//每一个基地的陨石和
if(cnt>=need[a[i]])break;//不加这句话在loj上会wa两个点,因为可能爆long long
}
if(cnt<need[a[i]])need[a[i]]-=cnt,ra[++itr]=a[i];//右半段
else la[++itl]=a[i];//左半段
}
for(ll i=l;i<=mid;++i)
{
ll val=stone[i].val;
if(stone[i].l<=stone[i].r)t.modify(stone[i].l,-val),t.modify(stone[i].r+1,val);//撤销操作
else t.modify(stone[i].l,-val),t.modify(1,-val),t.modify(stone[i].r+1,val);
}
for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);//递归求解
}
int main()
{
n=read(),m=read();
for(ll i=1;i<=m;++i)g[read()].push_back(i);
for(ll i=1;i<=n;++i)need[i]=read(),a[i]=i;
ll k=read();
for(ll i=1;i<=k;++i)stone[i].l=read(),stone[i].r=read(),stone[i].val=read();
stone[k+1].l=1,stone[k+1].r=m,stone[k+1].val=INF;
solve(1,k+1,1,n);
for(ll i=1;i<=n;++i)
if(ans[i]>k)puts("NIE");
else printf("%lld\n",ans[i]);
return 0;
}