スタンプラリー 3

题目

题目(ja)

题目大概意思就是,沿着湖边有 nn 个邮票展台,JOI君可以顺时针或者逆时针移动,每移动一个单位长度需要 11 秒,邮票展台在 TiT_i 时间后会被移除,问JOI君最多可以收集多少个邮票。

阅读更多

ymoi集训-树状数组

树状数组能解决什么问题

树状数组能解决的问题,线段树都能解决。

那么为什么我们需要树状数组呢?

因为树状数组代码段,常数低,空间更小。

SJBSJB今天问我corn6的B题(一道线段树+二分题)是怎么写出来5.1KiB的代码的。

阅读更多

ymoi集训-堆和可并堆

一个二叉树结构,可以实现O(logn)O(\log n)维护最值。C++ STLpriority_queue实现了大根堆。

阅读更多

Tarjan算法的相关应用

强连通分量

定义略。

用Tarjan算法来求解强连通分量,在此之前,先明确这两个定义:

  • 返祖边:由一个点指向其祖先的边。

  • 横插边: 由一个节点指向非祖先节点的边。(只有有向图会出现)

这两种边都是dfs树的非树边。

定义这两个数组:

  • dfndfn: dfs序。

  • lowlow: 不经横插边所能到达的点中最小的dfndfn

阅读更多

次小生成树

我们都会用クラスカル算法求最小生成树,但是次小生成树该怎么求呢?

首先,显而易见的是,次小生成树和最小生成树肯定只有一组边不同。

这样,对于一条不属于最小生成树的边uvu\rightarrow v,从最小生成树里去掉从uuvv路径上边权最大的边,然后连上uvu\rightarrow v,就是次小生成树。

但是严格次小生成树呢?

但是严格次小生成树呢?

好像要用树剖解决?

但是现在我看到树剖就想吐呢

那就不研究了吧,先把学校课预习预习再说吧。

【洛谷1505】旅游

基本上是一道树剖模板题。但是WA\color{red}WA了一上午才终于AC\color{green}{AC}

原题

这道题是边权,不过因为这是一棵树,可以把边权赋予这条边上深度更大的节点,就变成了树剖模板题。

但是这道题的push down操作是真的麻烦。

单点更新修改值,区间更新取相反数,区间查询,维护一个懒惰标记tagN表示取相反数。

阅读更多

ymoi集训-矩阵乘法

基本概念

一个n×mn \times m的矩阵可以被看做一个nnmm列的数阵,一般用一个大写字母表示:

A=[114514],B=[10982167]A=\begin{bmatrix}1&1&4\\ 5&1&4\end{bmatrix}, B=\begin{bmatrix}1&0\\ 9&8\\ 2&1\\ 6&7\end{bmatrix}

矩阵之间可以进行加减乘除运算,下面研究矩阵的乘法运算。

阅读更多

ymoi集训-树链剖分

树链剖分解决什么问题

先看这样的一个问题:

给出一棵nn个结点, 每个结点有点权, 要求支持:

1 u v x 将树上uvu\rightarrow v这条链的所有结点点权增加xx
2 u xuu的子树的所有结点的点权增加xx
3 u v 询问uvu\rightarrow v这条链的所有结点点权和
4 u 询问uu的子树的所有结点的点权和

n,q1×105n,q\leq 1\times 10^5

这个问题看起来很像线段树的题,不过这是在树上操作,所以我们要用树链剖分。

阅读更多

一些有趣的线段树push-ups

1

题目

nn个数a1na_{1\cdots n}排成一列,支持两种操作:
1 x y kaxya_{x\cdots y}加上kk
2 x y 查询i=xyai2\sum_{i=x}^{y}a_i^2

n,q1×105n, q\leq1\times10^5

操作

维护区间和,区间平方和。

如果把axya_{x\cdots y}中的每一个数加上kk的话,sum(x,y)=sum(x,y)+k×(yx+1)sum(x,y)'=sum(x,y)+k\times(y-x+1)sum2(x,y)=sum2(x,y)+2sum(x,y)+(yx+1)k2sum^2(x,y)'=sum^2(x,y)+2sum(x,y)'+(y-x+1)k^2

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×