hk_cnyali's Blog

hexo折叠文字/代码块的方法

挑了一些简单点的题乱做。。。

太菜了，想半天才想清楚

都是傻逼题

给出一个三角剖分的$n$边形

定义一次操作$(a, c)$：若存在$1\le a < b < c < d \le n$，满足$(a, b), (b, c), (c, d), (a, d), (a, c)$有边，则可以删掉边$(a, c)$，连上边$(b, d)$

定义目标状态为不能进行任何操作的多边形，问至少需要多少次操作才能到达目标状态，并求出方案数对$10^9 + 7$取模的值

另外，还有$m$次询问

每次给出一个合法的操作$(a, c)$，求在初始状态先操作$(a, c)$后得到的多边形的答案，询问之间互不影响

$n, m\le 10^5$

挂得好惨。

最近做的一点点CF上的题

并不全

一开始，你有序列$[1, n]$的一棵线段树，有$m$次操作/询问

• 1 l r：在操作队列里加上l, r这个操作。
• 2：询问当前操作队列，每个操作是否执行，总共$2^{k}$（$k$为操作数）种方案中， 线段树上tag为$1$ 的节点个数的总和。答案对$998244353$取模

在线段树上的一次操作$[l, r]$，就是把线段树上所有被$[l, r]$完全覆盖的极大区间的tag设为$1$

$n, m\le 10^5$