大概算是一道模板题吧？ 就是细节有点多 罗列一下：  如果习惯从1开始搞树的编号的话，处理输入进来的那个依赖关系在加边的时候两个都要+1，体现在代码就是i要从2枚举到n，然后输入进来的那个数要+1 这道题的线段树的打法也有所不同，因为只有两种状态，也就是已安装和未安装，我这里是用1和0来表示的，所以lazy标记就不能打成0了，我的代码中是用-1来表示的，注意要判这个东西（当然你也可以用1和2表示这两种状态） 线段树的修改也要改一下，+=得改成=（显然？）  这些细节都处理好后就是一个树剖模板了    #include <cstdio> #include <cstring&gt...

Description   有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个   操作，分为三种：   操作 1 ：把某个节点 x 的点权增加 a 。   操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。   操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。   Input   第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1    行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中   第一个数表示该操作的种类...

题面 Description    现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。  Input    第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。...

一.Trie的概念 Trie又称字典树，前缀树（事实上前缀树这个名字就很好的解释了Trie的储存方式） 来一张图理解一下Trie的储存方式：(图片来自百度百科)  由这张图我们也可以知道Trie的特点：  Trie的根节点是空的 除根节点外，每个节点储存一个单词/字母 也就是说，从根节点到每个单词节点的路径上的所有字母连接而成的字符串就是该节点对应的字符串 每个非叶子结点一般都会被多次使用，以节省遍历时的时间效率 另外，每个节点下面的数字是他们的编号，这个具体在下面再展开  所以读者们不难看出， Trie是典型的用空间来换时间的做法 二.Trie的操作 Trie的常用操作：插入，查询，删除 （...

如果你已经确保自己的hash技巧已经入门，那么请左转这篇博文 首先介绍一下hash？ 事实上是一种叫做蛤丝的病毒 以下讲到的hash都是OI中最常用到的hash方法：进制哈希 做法： 首先设一个进制数base，并设一个模数mod 而哈希其实就是把一个数转化为一个值，这个值是base进制的，储存在哈希表中，注意一下在存入的时候取模一下即可 比如说现在有一个字符串orzc 枚举这个字符串的每一位，与base相乘得到ans，然后mod一下，就得到orzc的哈希值 但是哈希有一个很大的弊端： 哈希冲突 什么是哈希冲突呢？ 就比如说orzc的哈希值是233，而orzhjw的哈希值也是233 那么我们在查...

传送门 Description    有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。  Input    第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。100%的数据2<=a,b<=1000,n<=a,n<=b,n<=1000  Output    仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。  Sample Input  5 4 2 1 2 5 6 0 17 16 0...

传送门 Description  最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。 通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（数据保证对于每个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买ASi股，一次卖出至多只能卖出BSi股。 另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔W天，也就是说如果在第i天发生了交易，那么从第...

传送门 Description   现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，   而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：     左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路    1:(x,y)<==>(x+1,y)    2:(x,y)<==>(x,y+1)    3:(x,y)<==>(x+1,y+1)    道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，...

传送门 题目： Description  小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。 小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。  Input  第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。接下来K行，每行第一个数为Ti，表示第i...