zcmimi's blog

arrow_back离线共18篇文章

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

avatar
zc
2020-06-04 19:43:00
查看原题

点击跳转

先了解[WC2011]最大XOR和路径的做法

线段树分治+并查集+线性基

加边删边可以用按秩合并的并查集解决,遇到环就插入线性基

由于并查集无法删除元素,删边可以用线段树分治处理(转化为每条边在一个时间段存在)

avatar
zc
2020-04-05 22:51:00
查看原题

点击跳转

\sum_{i=l}^r deep[LCA(i,z)]

首先,可以把询问拆成两个部分相减\sum_{i=1}^r deep[LCA(i,z)]-\sum_{i=1}^{l-1} deep[LCA(i,z)]

考虑一种暴力解法: 把1-r到根的路径全部+1,再查询z到根的路径和就是答案

可以发现问题的答案是可以叠加求出的

容易想到排序后离线处理

用树剖或LCT求解都可以

这里采用树剖+树状数组

avatar
zc
2020-03-24 09:05:00
查看原题

点击跳转

离线解法: cdq分治

将问题转化为三维偏序

我们先找出对答案有贡献的点(i,j)满足的条件:

time_i<time_j

val_i<val_j,pos_i>pos_jval_i>val_j,pos_i<pos_j

avatar
zc
2020-03-21 23:31:00
查看原题

点击跳转

允许离线处理

可以看成三维偏序(坐标和时间)

考虑如果要求的点都在当前点的左上方

那么也就是要求x_j\le x_i,y_j\le y_i,time_j\le time_i

x_i+y_i-\max(x_j+y_j)

坐标再旋转并处理三次就可以了

avatar
zc
2020-02-02 17:36:00
查看原题

点击跳转

AC自动机建完fail树之后子树的siz就是里面相同字符串的个数

每个询问可以拆成r的前缀和-l的前缀和

然后离线处理后用树状数组维护就可以了

主席树在线也可以

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

自己写了个莫队,结果51nod跑的太慢,然后TLE(MLE)

题解妙极了:

离线之后,从左向右扫一遍,让每个值存储“当前已扫过的部分中,右边第一个与自己相等的点到自己的距离”,然后如果当前扫到的点是询问的右端点的话,就回答这个询问。

这里面有个很巧妙的地方就是在询问的时候按r的大小从左往右询问,每次更新的时候更新的是和这个点最近的左边的点。因为只有更新到第r个点时才能能查询 l - r 的区间例如:1 2 3 4 1 只有在 r 等于 5 时才能询问 L - 5的区间,此时更新第一个1的值为4,如果L > 1的话区间并未更新所以查询线段树中L- 5的最小值还是INF

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

离线处理,倒着添加

2/2
Search
search