zcmimi's blog

categories/刷题记录/共659篇文章

avatar
zc
2020-04-25 16:51:00
查看原题

点击跳转

枚举右端点r,当前颜色x

lst_x为颜色x上一次出现的位置

假设我们已经得知了f(l,r-1),l\in [1,r-1]

那么f(l,r),l\in [lst_x+1,r]=f(l,r-1)+1

也就是说我们把[lst_x+1,r]区间+1就可以了

于是这题就变成了线段树(或树状数组)维护区间平方和

avatar
zc
2020-04-24 22:28:00
查看原题

点击跳转

avatar
zc
2020-04-23 14:02:00
查看原题

点击跳转

线段树分治+LCT

一个非常暴力的思路

FBI WARNING: 极有可能因为常数巨大而超时

把询问(修改)时间看成序列,每条边在这个序列上的一段区间出现

avatar
zc
2020-04-20 17:17:00
查看原题

点击跳转

要转化为加边,之后用并查集维护是否连通就可以了(带权维护连通块大小,为n的时候说明全部连通)

每条边都在特定的时间段中出现

由于加边完还要删掉这里使用按秩合并

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

点击跳转

定义

二分图又称作二部图,是图论中的一种特殊模型。

G=(V,E)是一个无向图,

如果顶点V可分割为两个互不相交的子集(A,B),

并且图中的每条边i\leftrightarrow j所关联的两个顶点ij分别属于这两个不同的顶点集(i \in A,j \in B),

则称图G为一个二分图。

简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

判断

区别二分图,关键是看点集是否能分成两个独立的点集。

无向图G为二分图的充分必要条件是: G至少有两个顶点,且其所有回路的长度均为偶数。

证明:

必要性:

G=<V,E>为一个简单无向图,G为二分图,那么可以将V分为V_1,V_2

CG中长度为l的圈,C=(v_1,v_2,...v_{l-1},v_l,v_1)

那么v_1\in V_1,v_2\in V_2,v_3\in V_1 ,\cdots,v_l \in V_2

也就是:

v_1,v_3,v_5,\cdots v_l-1 \in V_1 \\ v_2,v_4,v_6,\cdots v_l \in V_2

所以l必定为偶数

充分性:

设无向图G中每个圈的长度都是偶数,并且假定G为连通图

定义V的两个子集V_1,V_2:

任取v\in V,

V_1=\left\{v|dist(v_i,v) \mod 2 = 0\right\}

V_2=\left\{v|dist(v_i,v) \mod 2 = 1\right\}

V_1的节点间无边连接,

假若不然,设有边v_i\leftrightarrow v_j\in Ev_i,v_j\in V_1,那么vv_i以及vv_j的长> 度都是偶数,

那么vv_iv_jv这个圈的长度为奇数,与给定条件矛盾,所以边v_i\leftrightarrow v_j不存在

同理可证V_2的节点间无边连接

回归正题,我们要判断是否是二分图,只需要判断图里是否存在奇环就可以了

解法一

link-cut tree

考虑到每条边最后都是要删掉的,那么当构成环时,我们就可以将该环中最早要被删掉的边给删去,因为这样一来不会影响连通性,二来又可以化环为链。

添加一条边的时候,若两端未连通,直接连边即可

若两端已经连通,这时一定会形成一个环,为了维护LCT,连接两端时,我们需要把环上消失时刻最早的边给删去,如果是奇环则把这条边加入集合

删边时如果是LCT上的边则断开,在集合中则将其从集合中删除

查询时若集合中没有边,则为二分图

avatar
zc
2020-04-16 19:54:00
查看原题

点击跳转

可以看成思维偏序问题

先按第一维优先,相同则继续比较其他维排序(保证之后插入的点不会被之前插入的点的范围覆盖,防止统计的时候漏掉),

f_i=\max{f_j + 1}

剩下三维可以用KDT求出最大的f_j

有两种写法:

  1. 带重构KDT

  2. 先构建完整的KDT,然后把插入当作激活节点

avatar
zc
2020-04-16 18:02:00
查看原题

点击跳转

首先: 构建KDT

对每个点分别进行查询,也就是搜索

直接对KDT进行遍历每次搜索的复杂度是O(n)的,显然TLE

这时我们需要估价函数,在这里也就是:

估算出查询点到子树对应的长方形中的点的"最近距离"

若"最近距离"已经超过了当前答案,就跳过当前子树.

搜索时比较左右子树的"最近距离",先搜索"最近距离"小的

avatar
zc
2020-04-15 14:58:00
查看原题

点击跳转

avatar
zc
2020-04-15 13:42:00
查看原题

点击跳转

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

点击跳转

14/66
Search
search