小G的ACM之路

题意： 给出一棵树，有两种操作： 询问[u,v][u,v]的最大权值 然后更改第ii条边的权值为valval解析： 这是树链剖分的入门题，昨天调试了半天才做出这题，我还是太弱了。>但是还是弄懂了什么是树链剖分 树链剖分有先要进行两次dfs操作进行初始化。 第一个初始化操作，求得是每个节点的开头fa[u]，每个节点的深度deep[u]，以及每个节点的重儿子so

题意： 给出一个数组a，叫你每次询问如下等式的值。 f(l,r)=∑ri=l∑rj=igcd(ai,ai+1....aj)f(l,r)=\sum_{i=l}^{r}\sum_{j=i}^{r}gcd(a_i,a_{i+1}....a_{j})解析： 思考了很久终于理解了学长的思路 给你一个序列，这个序列的子序列gcd的个数不会超过logN个（N为每个数字，最大能取到的范围）

题意： 0 a b将区间[a,b]所有数全部变成0 1 a b将区间[a,b]所有数全部变成1 2 a b将区间[a,b]中所有数0 1互换，0变1，1变0 3 a b输出区间[a,b]中1的个数 4 a b输出区间[a,b]中最长连续1的个数解析： 涉及到线段树的多种操作。 mxL[0]表示左边最长连续0的个数 mxR[0]表示右边最长连续0的个数

题意： 有两种操作 Q a b 是询问区间[a,b][a,b]内最大的LCIS（最长连续上升子序列） U a b是更新节点a的值为b解析： 这题和 UESTC 360 Another LCIS 很像，具体的做法可以参考我的前面一篇博客mymy codecode#include <cstdio>#include <cstring>#include <algorithm>#

题意： 有两种操作： 1. 成段增加一个值。 2. 询问从l到r这段区间内的最长连续递增子序列（LCIS）。解析： 这道题真的是WA到手软了。 看了别人的题解才AC的。 如果某一段的值成段地增加一个量，那么该区间内的数的相对大小是不变的，因此递增子序列的长度是不会改变的。 那么对于结果有影响的信息与值： 1. 每个子区间中的最值 2. 有可

题意： 给你一个数组，初始值为零，有四种操作 （1）”1 x y c”,代表 把区间 [x,y] 上的值全部加c （2）”2 x y c”,代表 把区间 [x,y] 上的值全部乘以c （3）”3 x y c” 代表 把区间 [x,y]上的值全部赋值为c （4）”4 x y p” 代表 求区间 [x,y] 上值的p次方和1<=p<=3解析：我们可以把区间内的数字看做 ax

题意： 给一个整数序列，多达10万个。问：有多少个区间满足“区间最大元素与最小元素之差不超过k“解析： 如果用穷举法，有O(n2)O(n^2)复杂度，这肯定是不可取的。 所以可以用ST算法先预处理每个区间最大和最小值，O(nlog(n))O(nlog(n))。 注意一个区间固定起点，延长终点，那么这个区间的最大值和最小值的差肯定是单调递增的。 所以这题用双指针的方法，枚举

题意： 有n块板砖从天而降，底下有了m块木板来挡，每块板砖长度为1单位。 现在题目给出连续板砖的范围还有木板的范围与高度，问最后每块木板上有几块板砖。解析： 这题想了挺久的最后终于搞定了。 线段树的区间更新问题。 由于lil_i和rir_i比较大(0<=li<ri<=30000000)(0 <= l_i < r_i <= 30000000)，首先考虑到的是对左右边界进行离

题意： 对于长度为250000的区间，给了你四种操作： 操作A，从st到ed这段区间内的数，分别加上1,2,…,st-ed+1。 操作B，从st到ed这段区间内的数，分别加上，st-ed+1,st-ed,…,1。 操作C，将st到ed这段区间内的数赋值成x。 操作S，查询st到ed的这段区间内的数的总和。解析： 因为操作A和操作B都是操作的实际上都是等差数列，所以可

题意： 有两种操作： 1. 插入一个线段 2. 删除一个已存在的线段 每次插入后输出当前插入的线段能完整覆盖存在的几条线段。解析： 线段树上面维护的是两个值，左端点的和，右端点的和 每次插入一条区间[L, R]就， 先询问 [0, R] 的右端点个数 lsum 再询问[L, INF]的左端点的个数 rsum tot表示：当前线段还有几条

题意： 给定n长的序列。 操作1：修改某个点的值。 操作2：求区间[l,r] 内 下标奇偶交错的 子序列的最大和。 何为 下标奇偶交错： 序列: 2 1 5 6 询问区间[1,4] 则[1,4]内的所有下奇偶交错的子序列为 {2},{1},{5},{6} {2,1} {1,5} {5,6} {2,6} {2,1,5} {1,5,6} {2,5

题意： 给你N个矩形，每个矩形给出左下角坐标，右上角坐标，有M个询问，每个询问给出一个时间t，问(0,0)，(t,t)的范围内矩形的面积和（重叠的也算）。解析： 真的是细节非常难处理的题目，从有思路到AC，整整敲了一天。 由于矩形之间是相互独立的，而且tit_i又不大，可以把思路转化为每个矩形对时间的贡献是多少。 如果是一个矩形，可以转化成一个正方形，外加一个矩形的情况。

题意： 给你一个序列，找两个长度为 k 且没有重合区间的数使得其和最大解析： 线段树，就是把起点为 i 长度为 k 的和预处理出来，再枚举a，与a线段不重合的，后面的部分用线段树来找最大位置，总复杂度O(nlog(n))O(nlog(n))。mymy codecode#include <cstdio>#include <cstring>#include <algorithm>#de

题意： 定义一个NicoNico-number，如果x是NicoNico-number，那么所有小于x的且与x互质的整数是一个等差数列，初始给出n个数字的数组，三种操作： 1 l r 问在[l,r]内有多少个NicoNico-number数 2 l r v 对于[l,r]内的数全部对v取余 3 k x 将第k个数换为x 对每一次询问做出输出。解析（转）：

题意： 有T组测试数据，每组数据的N表示有N个城市，接下来的N行里每行给出每个城市的坐标(0<=x,y<=1000000)(0<=x,y<=1000000)。 然后有M(1<M<200000)(1<M<200000)个操作，操作有两类： （1）”road A B”，表示将城市A和城市B通过一条道路连接，如果A和B原来属于不同的城市群，经过这个操作，A和B就在一个城市群里了，保证每条道

题意： 在二维平面上，给你每个建筑的左右坐标以及高度，问你建筑外部轮廓的转折点。解析： 这题可以用线段树的区间更新来做，线段树的每个节点，用于维护X轴区间最高的点，而不是X点上最高的点。 由于数据范围比较大[−1e9,1e9][-1e9,1e9]，可以先将X轴坐标，离散化。然后每次更新的区间是[L,R−1][L, R-1]，这样就可以把坐标的更新，更新到区间上。 至于最后如何，

题意： 给定一个长度为n的字符串，有q次操作，每次操作将一个区间内的字符按升序或降序排列，输出q次操作后的字符串，串中只包含小写英文字母.解析： 考虑到字符集大小只有26，联想到计数排序，对一个区间做一次排序相当于对区间内每一种字符分别统计一遍个数后，再按照字符的顺序（升序或降序）依次重新填进区间内，可以用26棵权值线段树分别维护每一种字符的位置，复杂度O(26nlog2(n)+52qlo

题意： 给定一个容器，里面存放各种数值，规定三个操作，一个是在容器中增加一个数值，一个是在容器中删掉一个数值，一个是询问容器中比a大的数中第k大的数，将其输出。如果在删除过程中没有这个数，则输出”No Elment!”,如果容器中没有比a大的第k个数，则输出”Not Find!”.解析： 线段树的单点更新可以解决这题，就是在查找的比a大的第k个元素的时候，要注意先找到a元素的位置，可以用线

题意： 题意：给出10000个模式串和一个长度为100000的匹配串，有两种操作： 1.查询匹配串的子串[L,R]是否存在于模式串中 2.修改匹配串某个位置的字符解析： 将一个字符串看成是一个P进制的数字，那么可以知道每一个字符串都可以被唯一表示(P>256P> 256，并不考虑高精度)。可是由于字符串的长度比较大，那么我们无法保存如此大的数字。于是使用Hash mod2^64

题意： 给了三种操作 1. add（x,y）将这个点加入二维坐标系 2. remove（x,y）将这个点从二维坐标系移除。 3. find（x,y）就是找到在（x,y）右上方的第一个点，先满足最左边第一个点，如果最左有多个点，那么满足最下面第一个点。思路： 我们可以建立n个set以x为横坐标，那么我们这个题就转化为找一个最小的x是否存在满足条件，那么x一旦被找到，那么纵坐

题意： 中文题意不解释了。解析： 用树链剖分求解该题。 在线性序列用线段树里面怎么维护颜色段。其实很简单，每个线段树的节点位置记录三个值： lc：这段区间最左端的颜色；rc：这段区间最右端的颜色；sumv：这段区间里面的颜色数。 那么进行区间合并的时候，就可以： sumv[o]=sumv[ls]+sumv[rs]−(rc[ls]==lc[rs]);sumv

题意： 给一棵树，并给定各个点权的值，然后有3种操作： I C1 C2 K: 把C1与C2的路径上的所有点权值加上K D C1 C2 K：把C1与C2的路径上的所有点权值减去K Q C：查询节点编号为C的权值解析： 典型的树链剖分题目，先进行剖分，然后用线段树去维护即可。注意： HDU的OJ采用Windows系统，容易爆栈，所以在代码中加入汇编手动扩大内存。mym

题意： 是男人就下100层相信很多人都玩过，这题就是简单的模拟这个游戏。 有nn块木板，每块木板有4个属性，高h(h>0)，左边界，右边界，以及掉落在它上面，获得多少生命值，一个人从最高的木板开始往下跳，初始时生命值为100，问最后掉落到地面能获得的生命值最多为多少（如果途中生命值为≤0，那么这个人会死去），如果无法跳到地面，输出-1。解析： 既然只能垂直下落，而且是落在最近的板上，

题意： 有n个点，m条边，每个点都有权值。 然后开始删除点，删点规则是如果这个点连接其他点的数量小于2，那么这个点可以删除。 如果删除了某些点产生了其他可删除的点也将其删除。 直到删除到不能为止。问最后剩余的联通块中，点的数量是奇数的联通块中的点的权值和是多少。解析： 先算出所有点的度数，然后把这些度数存入线段树中，每次询问线段树找到等于最小的度数的节点，把和该最小度数的

题意： 有一条长度为L的街道，有N个操作，现在有两种操作： (1)”1 a”，表示有一辆长度为a的车开进来想找停车位； 停车位必须满足与它前面的车距离至少为b，与后面的车距离至少为f； 如果能找到这样的停车位，输出这辆车的起始位置（且这个位置最小），否则输出-1; (2)”2 a”，表示第a个事件里进来停车的那辆车开出去了; 解析： 这题和POJ 3677 Hot

题意： 模拟一个内存分配机制。 Reset：重置，释放所有空间 New x：申请内存为x的空间，输出左地址 Free x：释放地址x所在的内存块 Get x：查询第x个内存块，输出左地址解析： 可以用一个vector来记录所有的内存块的区间。 New x操作可以利用如同POJ3667POJ 3667中的query操作查找到最右边的位置。然后把找到的区间二分插入

题意： 给出一个字符串，长度为10^5，有m个操作m<=104m<= 10^4。 有两种操作： 1. 询问[l,r]区间的子串是否回文 2. 将第i个字符改为c。解析： 用字符串哈希+线段树来做这题，线段树用于查询区间的hash值。 建两棵线段树一棵维护从前向后的hash值，另外一棵维护从后向前的hash值。 那么我们判断是否回文串，就只要看正反区间的哈希值之

题意： 题目定义了3种操作 D代表破坏村庄， R代表修复最后被破坏的那个村庄， Q代表询问包括x在内的最大连续区间是多少思路： 和前面几道线段树的区间合并一样，在线段树的区间内，我们要用三个变量记录左边连续区间，右边连续区间和最大连续区间。 这题主要的难点是怎么查询。 我的查询函数是这么写的。int query(int o, int L, int R, in

题意： 给出一串数字，然后给出两种操作： 1. 1 L V 操作一：把下标为L的点的值替换为 V 2. 2 L R K 操作二：在[L,R][L, R]区间求第K大解析： 本模板转载自 http://blog.csdn.net/u012860063/article/details/47813079mymy codecode#include <cstdio>#inc

题意： 一家旅馆有N（1 ≤ N ≤ 50000）间房间，并且所有的房间都是连续排列在同一边，现在每个观光团需要入住房间，要求房间的编号为连续的r...r+Di−1r...r+D_i-1，并且r是最小的； 参观者同样可能退房，并且他们每次退房都是编号为Xi...Xi+Di−1X_i...X_i +D_i-1 (1≤Xi≤N−Di+1)(1 ≤X_i ≤N-D_i+1)的房间。 现在有

题意：给定一棵树，以及定义了3个操作1、把v点及其子树灌上水 2、把v点及v到根的路径去掉水 3、询问v点是否有水解析：先对这棵树做一遍dfs序，把树转成dfs_clock，这样每个点就可以对其子树进行区间更新。那么对于点v 出现的时间in[v]和消失的时间out[v] ，一定会把v子树下所有节点都夹在[in[v], out[v]]之中。对于操作1，就是把 [in[v], out[v]]改成1对

题意： 给你n个数，有m个查询，问区间[L,R]之间有多少个数与这个区间内的其他数都互质。解析： 很显然，[L,R][L,R]区间内的答案就是一个区间内的数的个数，减去与其他数不互质的数即可，即离当前数 aia_i 左边最近的不互质的数的位置（设为L[i]）和右边最近的不互质的数的位置（设为R[i]）有一个在区间[L,R][L,R]内。 那么问题就变成统计： (1) 区间[

题意： n个人接受邀请的条件是已经接受邀请的人数区间在l[i] , r[i] 问怎样设置邀请顺序能使得接受邀请的人数最多解析： 先对区间从小按照右边界从小到大排序，如果右边界相同，再按照左边界从小到大排序。因为右边界越小优先级越高，左边界同理。 如果用优先队列，是算出选择当前人选择哪个区间是最优的。 由于本人不会两个条件的优先队列，所以只能换了一种写法来写。 于是

题意： 刚刚开始的时候所有的片段上的颜色都是2。 在片段上着色，有两种操作，如下： 第一种：P a b c 把 a 片段至 b 片段的颜色都变为 c 。 第二种：Q a b 询问 a 片段至 b 片段有哪些颜色，把这些颜色按从小到大的编号输入，不要有重复。解析： 很简单的线段树区间合并问题。 对于1操作，可以利用线段树进行区间覆盖。 对于2操作，每查询到一个有

题意： 给你N个花瓶，花瓶的编号是从 0 到 N - 1，初始状态花瓶是空的，每个花瓶最多只能插一朵花。 然后有2个操作： 操作1 a b，往在a位置后面（包括a）插b朵花，输出插入的首位置和末位置。 操作2 a b，输出区间[a,b][a , b]范围内的花的数量，然后全部清空。解析： 很显然这是一道线段树的题目。区间更新，区间求和，这些基本的操作线段树都可以O(l

题目： 给出一个序列，mex{}表示集合中没有出现的最小的自然数。 然后求∑mex(i,j)\sum{mex (i , j)}。解析：思路转载自 cxlove 考虑左端点固定时的所有区间的mex值，这个序列是一个非递减序列，这点首先要明白。 初始时，先求出mex[j]表示mex(1, j)。（可以用map求出） 对于每一个左端点i，就是一个区间求和。（可以利用线段树维

题意： 给你N个数，有四种操作。 （1）”AND opn L R”，表示对区间[L，R]内的数全部与opn进行且(&)操作。 （2）”OR opn L R”，表示对区间[L，R]内的数全部与opn进行或(|)操作。 （3）”XOR opn L R”，表示对区间[L，R]内的数全部与opn进行异或(^)操作。 （4）”SUM opn L R”，求出区间[L，R]的数的和。

题意： 给出一颗树，每次对树进行两种操作。 第一种操作：给节点v及距离节点v，d个单位长度以内的节点加x 第二种操作：询问节点v当前的值。 注意：给出的树中，除了节点1以为，其他节点的度都不会超过2。解析： 有了上面这个条件后可以发现，这种树肯定是节点1拖着很多直链的。 看了网络上面的题解，理解了可以用两颗线段树来做这题。 一棵线段树来维护每层加了多少次，另

题意 我们要在地平线上依次建造 n 座建筑。建筑的修建按照从后往前的顺序，因此新建筑可能会挡住一部分老建筑。 修建完一座建筑之后，统计它在多长的部分是最高的，并八这个高度称为该建筑的“覆盖度”。现在要你求总的覆盖度。解析 注意是每修建完新的建筑之后就计算一次覆盖度。 所以可以转化为线段树的区间更新问题，线段树上面维护的是当前区间的最大值。并用一个懒惰标记来表示该区间的连续的

题意： 有一个h*w的公告牌，h是高度，w是宽度，一个单位高度1为一行，然后会有一些公告贴上去，公告是1*wi大小的长纸条，优先贴在最上面并且最左边的位置，如果没有空间贴得下，就输出-1，可以的话，就输出所贴的位置（第几行）。解析： 叶节点maxv[x]表示board的第x行还可以放置的长度，区间[a,b]表示第a行到b行中剩下空间最大的那一行是多少，如果要把长w的公告放入board时就是