x题目链接 题意：给出两个数组，每个数组n个数，分别为a和b,给出m个操作，操作有两种类型，第一种是给出x,y,k,表示从a数组的x坐标开始复制k个数到b数组的y到y+k-1。 第二种操作是给出x，询问当前b[x]是多少。 对于每个第二种操作，输出结果。 思路：第一次写lazy标记的线段树。 今天突然就顿悟了。。。其实lazy标记的思想大概就是。。 对于某段区间的更新，如果没有查询到这段区间中任何一个数的时候。。。那么这个更新其实是无所谓的。。。 （让我想到了那个脑洞，就是整个世界都是一段程序，为了让你不察觉异常并且耗费尽量少的资源，所有场景只有在有人观测的时候才会被加载，不观测就用很少的资源随便处理一下233） 所以lazy标记， …

题目链接 题意：给出n个数，m个查询，每组查询一个区间[l,r]，问[l,r]中会被吃掉多少个（区间[l,r]中的数只有当其是其他所有数的因数时才不会被吃掉,顺便问一句。。a divide b 是 a除b,也就是b除以a,b/a的意思嘛23333） 思路：我们知道，不会被吃掉的数其实就是区间[l,r]中所有数的gcd,求gcd可以很容易用线段树办到。。。关键是还要统计该区间中等于gcd的数有多少个。 并不会做。 大概有两种做法。。。？ 一种是基哥@clq11111说的，将询问离线，然后从小到大排序插入，询问区间中等于x转化成询问区间中小于等于x的，和询问区间中小于等于x-1的，做差即为所求。 第二种办法是题解的讨论区部分的： 想了 …

题目链接 题意：给出n个数，求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。 思路：对于这种要求三个数满足条件的题目，老司机的经验是考虑中间那个数，这道题也不例外。 我们枚举j，通过求两次逆序对求出对于每个a[j]，满足a[i]>a[j]的i的个数，以及满足a[j]>a[k]的个数。 两个个数的乘积就是j作为中间数满足的三元组的个数，这样把所有的j累加就是答案。 其他的就是，要离散化，以及最后答案可能会爆long long? 1A，好爽啊哈哈哈。 /* *********************************************** Author :111qqz …

题目链接 题意：定义_f_(l, r, x)为区间[l,r]中x出现的次数。现在要求calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that_f_(1, i, a__i) > f(j, n, a__j). 思路：可以通过o(n)预处理出f(1,i,a[i])和f[j,n,a[j]]，其实预处理的过程就是离散化的过程呢。。。 分别得到 1 1 2 3 2 3 4 4 3 3 2 2 1 1 所以答案其实就是第一组数在第二组数中找逆序数的过程。。。 我们不妨倒序处理。 需要注意的是，线段树维护的区间是0..mx，我整体增加了1. 线段树求 …

题目链接 题意：给出n和m,初始给出1<<n个数，先相邻的两个数进行或操作（a[1]^a[2],a[3]^a[4]...），得到的新数列再相邻的两个数进行异或操作。 最后得到一个数，即为答案。现在给出m个操作，每个操作两个数p,b，表示令a[p]=b,每次变化后输出最终的结果。 思路：线段树。这道题让我学到了，线段树的数组tree[i]存储的信息可能不唯一，可以不同层存储的是不同的信息。 比如这道题中，距离叶子节点距离为奇数的点存储的是或操作的结果，距离叶子节点距离为偶数的点存储的是异或操作的结果。 还需要注意的是，build和update操作都是从顶向下，最后一个操作是异或还是或取决于n的奇偶性，记得判断。 /* …

题目链接 题意： 在二维坐标平面内进行_n_ (1 ≤ _n_ ≤ 2·105) 次操作。一共有三种类型操作。 1.add x,y 将点(x,y)加进坐标系。 2.remove x,y 将点(x,y)移除. 3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有多个输出x最小的。还是有多个输出y最小的。 x,y均为非负数。以上操作均合法。 思路：没有思路。。。不会啊。。。以为要二维线段树什么的。。。。总之是不会做。。。 大概从中午开始看题解。。。8个小时。。。。终于完全搞懂了orz 很巧妙得把二维问题转化成了一维问题。。。 我来说一下大概做法，具体的细节见代码注释： 在x轴方向维护一课线段树，线段 …

poj 2828 题目链接 题意：n个人，每个人有一个rp值（用来区分不同的人），还有一个pos[i]，表示当第i个人来排队的时候插入到第pos[i]个人的后面（也就是排在位置pos[i]+1) 现在问最后的序列，从1到n输出n个人的rp值 思路：第二道线段树，并不会做，看了题解。 比较关键的一点是：按照顺序的话，当后来的一个人插入到前面，那么之前很多人排好的位置将发生改变，这个代价是巨大的。 由于越后来的人越容易确定位置，因此正确的做法是倒序处理。 对于第i个人，我们把他放在从前往后数的第i个空的位置即可。 接下来需要做的就是线段树处理，线段树存储的信息是某一个区间中空位置的个数。 感觉是一道很好的题目，对于新手来说并不是很容易， …

hdu 1754 题目链接 题意：单点更新，区间查询最大值。 思路：线段树。 一开始借鉴了clj的pointer写法。。wjmzbmr's code 直接MLE。。。看来也许只能在cf上用。。。 下面是MLE的代码： /* *********************************************** Author :111qqz Created Time :2016年08月18日 星期四 18时40分24秒 File Name :code/hdu/1754.cpp ************************************************ */ #include <cstdio> …

嘛，终于下定决心搞定线段树了。 之前几次都是被lazy标记卡住，这次大概不会了吧2333 放一些学习资料，最后比较zkw线段树和普通线段树的区别。 codeforces上非递归线段树讲解 （其实就是zkw吧） 线段树进阶（各种花式技巧） 找到了一篇非常赞的tutorial（含lazy标记） 链接

http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：一个尺寸为wh的方格。要按顺序放放n个尺寸为1wi的纸条。问每一个纸条回被放在哪里。如果有多个，放在最上面（编号小） 思路：把没横行能放的最大长度看做一个序列建树。由于h比n大很多。。多出来的没用。。直接取较小值就行。 /* *********************************************** Author :111qqz Created Time :2015年12月17日 星期四 15时04分52秒 File Name :code/hdu/2785.cpp …