menu ZigZagK的博客
account_circle

正在努力加载中QAQ

数据结构水题选讲(By AwD)部分题解
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内,所以可以把值域也分块,这样移动指针就不需要带 $l...
[离线+扫描线+LCT]BZOJ4573(Zjoi2016)【大森林】题解
题目概述有 $n$ 棵树和 $m$ 个操作,操作有:1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $x$ 树中 $A$ 到 $B$ 的...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[思维+LCT]TopCoder【TreeColoring】题解
题目概述有 $n$ 个点的带边权树和 $m$ 次操作,每次操作:1.将一个点变成黑色。2.求 $x$ 到所有黑色点的距离。解题报告好像可以大力点分树……我没有想过。考虑我们要求的是 $\sum ...
apps TopCoder
local_offer 查看标签
comment 0 条评论
阅读全文
[LCT+泰勒展开]LOJ2289(THUWC 2017)【在美妙的数学王国中畅游】题解
题目概述有 $n$ 个点,每个点是一个函数:$sin(ax+b),e^{ax+b},ax+b$ 。有 $4$ 种操作:1.连接 $x,y$ 。2.断开 $x,y$ 。3.修改 $x$ 点函数。4...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[LCT+构造]BZOJ3091【城市旅行】题解
题目概述维护森林,每次询问一条路径 $(X,Y)$ 上任意选出两个点 $(x,y)$ 的路径权值和的期望。解题报告刚开始竟然极其斯波的想成了路径权值和的 $size$ 倍……把一条路径排成序列,...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[LCT维护最大生成树+二分图判定]BZOJ4025【二分图】题解
题目概述有 $n$ 个点 $m$ 条边,每条边有个出现时间 $s$ 和消失时间 $t$ ,问每个时刻是不是二分图。解题报告法老给我们上课用的PPT表示:把边加到线段树里然后线段树二分用LCT判奇...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[分治+LCT+二分图判定]Codeforces19E【Fairy】题解
题目概述有 $n$ 个点 $m$ 条边,问有多少边删除了之后让原图是二分图。解题报告远古CF题。删除一条边可以考虑分治,然后用LCT判断有没有奇环就行了。这是斯波做法,时间复杂度 $O(nlog...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up