题意 有一群从 至 编号的防御塔，每个防御塔会有一个护盾，防御力是 。每一次，敌人会从 到 的他进行 的打击。这时候会将 若 小于等于0，就是这次护盾破了，之后收到的伤害会加倍，在此之前，受到的伤害是一倍。 你需要支持单点查询这个点收到的伤害。并支持区间打击。 树状数组-离线 考虑对于打击差分，由编号求解，对于时间建立树状数组。将打击和询问对于编号排序，我们每次只要处理出来一个编号的点所有的答案即可。 就是说，每次的打击如果是 到 的 ，此时时刻是 ，那么，就在 的树状数组上记一下，在做到编号是 的时候加 ，在做到 的时候减 。 比如下边这个样例： 5 8 1 2 3 4 5 A 1 3 2 ...

前置知识 大概学过重链剖分吧。 重链剖分是重儿子，即 sz 最大的儿子，这个剖分是指长儿子，即 dep 最大的儿子。 这样子可以把树剖成一条一条链。比如下面这个图绿色的部分就是长链。    一个节点到它所在的长链的链底部的路径，为从这个节点到它子树每个子树所有节点的路径中，最长的一条。 一个节点到根的路径，最多经过 个虚边（这个我不太会算，大概就是这么构造一个树，每个从任何一个节点出发，每个结点到叶子节点的距离都是一样的同时在一个非叶子节点的儿子中，只有一个儿子结点可以有多个儿子，且如果这个结点的父亲结点有且仅有他一个儿子，那么这个结点也有且仅有一个儿子。就是一棵删减的完全二叉树。  应用例子...

CF1290E Solution 前言 这道题你需要的前置知识  树状数组 吉司机线段树的基本操作  正文 题意翻译：给你一个 至 的排列，每次找出其中不大于 的数字，相对位置不变成为一个新的序列，在这个新的序列上建一棵大根笛卡尔树，求这个笛卡尔树的每个结点为根的子树的 size 之和 暴力思想 每次 建笛卡尔树，然后 的 dfs 即可。总复杂度  不难发现一个事情，在我们建这个笛卡尔树的时候，这个序列是 至 的一个排列。其中每个结点的子树他们的编号必定是一个连续的区间，这是因为笛卡尔树满足二叉排序树的性质。 我们记 为以编号为 的结点的子树里的结点的最大编号，同样我们可以定义 。那么每个子树...

原题目太复杂了。 放个链接 通俗的说一下题目  句子 = 名词短语(+动词短语+名词短语+动词短语+...) 动词短语 = (辅词+辅词+辅词+...+)动词 名词短语 = (辅词+辅词+辅词+...+)名词  给你一个文章，问怎么分可以把句子数量最少的情况下，单词数量也最少。 询问这个两者的次数，保证存在一种合法的划分方式。单词长度不超过 20  ， 解题思路 一看就是个 dp。考虑令 为做到 位置之后结尾的次的情况。 显然我们如果不考虑辅词的话，只需要两种情况  0 表示以名词结束 1 表示以动词结束  很明显我们的一个状态是 pair 的。 但是这样子明显无法判断辅词的时候，考虑设记四种...

题目分析 有一个树，有 个结点，然后每个结点 ，上有个权值 ，开始的时候点都是白色的. 你可以选结点，这个结点可以使在它和根结点的链子上 到 的点都染成黑色 ，问你如何选择最少的点，可以让这个树都变黑。（没错这是我看错的题目，但是没有影响，而且还简单了。 思路与想法 这不就随便搞嘛。一看不是贪心就是dp。尝试着描述了一下状态，发现不好描述也不好转移，那么就搞一下贪心。 不妨在 Dfs 的过程中计算答案。有个很明显的 做法。  找到未被覆盖的节点组成的树的一个叶子节点 在它和它已经被覆盖的子树中找到一个点，使得其向上能覆盖到的 及 的祖先们尽可能多 如此反复，知道没有 可以取  这个过程可以用 ...

序   #define 嵬 为   怕自己忘记，写完这个 blog 就写作业，一群闲的蛋疼带科学家研究出的一个解决全局最小割的算法。   正文   算法思想：贪心   解决范畴： 对于一个无向图，每个边有割去的代价，问怎样割边能使这个图变为两个不连通的子图。   例题：hdu6801, poj2914   这个东西的名字叫做：全局最小割   咋做？反正我不理解，上课时 nk2005 也没有给证明，就发了个文章，让自己看，这哪会呀...   先给一个好实现的方法——利用网络瘤来解决    枚举源点和汇点  利用你会的各种网络瘤算法来搞出这个题比如说 ISAP, Dinic, ek, HLPP（不...

填坑   珂朵莉树学习笔记   前言   我就是喜欢这种暴力的数据结构，打着就一个字，爽！   话说，滕老师告诉我别拿平衡树水线段树了...这是人话吗。   通过 这个题 我 get 到了珂朵莉树的基本操作，实在是佩服数据结构大师 lxl   PS: 珂朵莉树为啥叫作树，因为set内部是红黑树...   思想   就是一个暴力的思想，因为随机数据下assign会有四分之一，所以时间复杂度几乎是 \(O(m \log n)\) 的， 在std::set里存节点，每个节点就是一个区间，这个区间里的值都一样.话说看到 CF896C 的记录中 Falldream 用线段树搞出来了 %%%   正文  ...

树链剖分学习笔记 序 听 Singercoder 说树链剖分是码农题，然后我否认（雾）。夜已深，屏幕微凉，数据结构，他说：“A了我，快！”，莫名激动。  我有一壶酒，足以慰风尘，还是，我心中好不了的伤疤。  正文 预备知识：  LCA 的思想 vector 或 链式前向星的熟练使用 线段树（线段树1 dfs 序  模板题目：P3384 要求给你一颗树，有以下几个操作  操作 1： 格式： \(1 x y z\) 表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。 操作 2： 格式： \(2 x y\) 表示求树从 x 到 y 结点最短路径上所有节点的值之和。 操作 3： 格式： \...

带花树算法 序 AC 300祭 正文 主要思想是开花和并查集维护-.- 我们先模拟算法执行的过程 好吧，我并不是绘画流程图的样子。那就老老实实画图吧。 首先，对于每一个点点 bfs。 假设我们有一个图。  我们要在这个图上做一般图匹配。先从一节点开始，他找了二结点，嗯，没有匹配，我们就要路径取反，之后在搞  之后尝试寻找三节点的匹配，然后他找到了一结点，一结点的对应节点的颜色标记为 1 ，并入队。开始寻找2结点，发现他有颜色，且为一，得知是一个奇环，所以我们要先找到树根，然后树根应该是 3 对于 2 1 3 进行开花。此时找到的根应该是 3 我们缩环 2 3 1，二的前驱被标记为 3， 而fa...

浅谈FFT 多项式的表示 首先学习两种多项式的表达法  系数表达法 点值表达法  系数表达法 比如一个 \(n\) 次多项式 \(A(x)\) 他有 \(n + 1\) 项 于是 设每一项的系数为 \(a_i\) 则有 \(A(x) = \sum _{i = 0}^ n a_i x^ i\) 利用这种方法计算多项式乘法复杂度为 \(O(n^2)\) 即利用（第一个多项式中每个系数都需要与第二个多项式的每个系数相乘） 用这种方法，计算 \(A(x_0)\) 的值是非常好用的，我们使用霍纳法则即可。 点值表达法 我们知道如果给出 \(n + 1\) 个互不相同的点，他们确定一个 \(n\) 次多项...

序 乓乓球 话说天津的玩梗真的是... 正文 做这个题，其实暴力一分也得不了....因为我的 \(O(nlogn)\) 不开 O2 最快的点也才跑了200+ms...然后大概就是这么想，我们在暴力的基础上优化一下。反正这样子应该可以简化反正就4个字符... 就是说，我们预处理出每个（子串）东西的 LCP，然后搞一搞吧。但是我知道的求 LCP 的快速方法只有后缀数组的 height，然后自然的联想到了 RMQ， 也就是说我们查询 suf(x), suf(y) 的 LCP 可以通过找一个 \(\min_{x < i \le y} (height[i])\) 对吧，这是显然的。因为字典序的性质...

序 我觉得我现在还可以 安利一下 rsx's blog 正文 本文权当作学习二分图匹配的一些笔记，个人风格极为严重，请勿深究语文 匈牙利 本文不介绍算法的步骤，因为可以 google（逃，写的都是一些自己的总结 匈牙利的算法主要功能是可以做二分图的最大匹配。它是一种交替的找增广路的算法，其本质就是逆流修改（Singercoder 说的） 其核心的就是 re 这个数组不会回溯 （当然每次要清） 为什么呢，其实我觉得和当前当前弧优化有点联系。你想想，他要是回溯的话，都不是多项式算法了（笑）。但是其算法正确性也是有的。re 表示的是这个结点是否寻找过增广路。 理论上最坏时间复杂度会到 \(O(VE)...

#include <cstdio> int x, y, a, b; void exgcd(int a, int b){ if(b == 0) { x = 1, y = 0; return ; } exgcd(b, a % b); int xx = x, yy = y; x = yy; y = xx - (a / b) * yy; return ; } int main() { freopen("test.in", "r", stdin); scanf("%d%d", &a , &b); exgcd(a, b...

序 闲来无事，打场CF,本人蒟蒻，考场A了前三道，第四有解答 正文 T1 Non-zero 是道水题。。。。 给你一个序列a。要求你输出最少的操作次数使这个序列的累和与累乘都不为0； 一次操作指给\(a_i\)+1. 我们的想法是先给每个零的+1，检查此时和是否为0，若为0，+1，否则直接输出答案 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int Maxn=101; int t,n,s,a[Maxn],sum; int main() ...