0%

浅谈线段树分治

浅谈线段树分治

众所周知区间加,区间乘等操作可以利用线段树在单次操作$\mathcal O(\log n)$时间复杂度内完成。
对于更复杂的对区间的操作,同样可以利用线段树每次访问$\mathcal O(\log n)$个节点的性质,把标记打在这$\mathcal O(\log n)$个节点上,最后从根开始dfs,将信息下推至叶子节点,以此更快速的解决。

在此介绍两个例题:

CF 981E

题意:

给一个长度为$n$ 的序列(初始全为0)和$q$条操作(以$(l,r,x)$表示将$[l,r]$中的每个数都加上$x$.
对于$1\le k\le n$,求哪些$k$满足选出若干条操作后序列最大值为$k$.(对于一个$k$,每条操作至多用一次)

$1\le n,q\le 10^4$

解:首先,可行的$k$集合等于每个位置可达的值的集合 的并集.故求出每个位置可达的值集合即可.
对于每个位置$i$维护一个bitset,记为s,设现在考虑的$(l,r,x)$满足$l\le i\le r$,那么$(l,r,x)$对s的贡献就是:s|=(s<<x)

于是暴力做法就显然了:对于$[l,r]$中的每个元素,都做一次s|=(s<<x)即可.时间复杂度上界$\mathcal O(nq\times \frac{n}{w})$,显然不行.

接下来就是套路:用线段树分治,把$(l,r,x)$的影响打到线段树的$\mathcal O(\log n)$个节点上.(注意节点上用vector维护增加的值即可,不用维护bitset徒增时间复杂度)最后从根dfs一下,把信息下推至叶子节点即可.叶子节点的bitset or起来的结果就是答案.

时间复杂度$\mathcal O(q\log n+\frac{n^2}{w})$

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
/**********/
#define MAXN 10011
ll n,q;
std::bitset<MAXN>ans;
struct Segment_Tree
{
std::vector<ll>t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
void modify(un ql,un qr,ll k,un l=1,un r=n,un num=1)
{
if(ql<=l&&r<=qr)
{
rt.push_back(k);return;
}
un mid=(l+r)>>1;
if(ql<=mid)modify(ql,qr,k,l,mid,num<<1);
if(qr>mid)modify(ql,qr,k,mid+1,r,num<<1|1);
}
void dfs(std::bitset<MAXN>pre,un l=1,un r=n,un num=1)
{
std::bitset<MAXN>cur=pre;//复制父节点的信息
for(auto x:rt)cur|=(cur<<x);
un mid=(l+r)>>1;
if(l==r){ans|=cur;return;}
dfs(cur,l,mid,num<<1),dfs(cur,mid+1,r,num<<1|1);
}
}sgt;
std::bitset<MAXN>s;
int main()
{
n=read(),q=read();
while(q--)
{
ll l=read(),r=read(),k=read();
sgt.modify(l,r,k);
}
s[0]=1;
sgt.dfs(s);
ll cnt=0;
for(ll i=1;i<=n;++i)
if(ans[i])++cnt;
printf("%lld\n",cnt);
for(ll i=1;i<=n;++i)
if(ans[i])printf("%lld ",i);
return 0;
}

LOJ #121. 「离线可过」动态图连通性

题意:维护一个无向简单图,支持连边,删边,查询两点是否联通。

$n\le 5000,m\le 5\times 10^5$($m$是操作次数)

解:首先,无论是LCT,ETT甚至top tree都无法直接维护图,我们需要通过一些操作转变成维护树,才能做。

同样考虑暴力。维护一个长为$m$的序列,每个位置维护一个并查集,并离线统计每条边$(u,v)$的存在区间$[s,t]$。将$[s,t]$中的每个位置上$(u,v)$合并。查询直接在并查集上查即可。

接下来同样套路:利用线段树分治,将$[s,t]+=(u,v)$的操作打到线段树的$\mathcal O(\log n)$个节点上。最后从根开始dfs恢复信息,但是这里复制的代价是每次$\mathcal O(n)$,总时间复杂度会达到$\mathcal O(nm)$,无法接受,不能直接复制。

一个显然的想法是,维护一个LCT,到达一个节点时算一下他的影响,然后处理儿子,之后把现在这个节点的操作撤销。这样的时间复杂度是$\mathcal O(m\log m+m\log n)$,按道理可以通过,但我被卡常了。提交记录

在LOJ群请教了神仙之后我知道了有一个奇妙的数据结构:可撤销并查集。不用路径压缩,合并的时候用栈存一下操作,这样就能支持回退最后一步的操作,恰好满足需要。为了保证时间复杂度,需要使用按秩合并。这样的时间复杂度就是$\mathcal O(m\log m+m\log n)$,常数约为LCT做法的时间复杂度的1/8,可以通过了.提交记录