【单点更新】

第一题 hdu 1166 敌兵布阵 

点击打开链接hdu 1166

思路: 线段树单点更新

分析:

1 题目给定n个兵营的人数，现在有三种操作

 (1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
 (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
 (3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;

2 最简单的线段树单点更新的题目

点击查看代码

第二题 hdu 1754 I Hate It

点击打开链接hdu 1754

思路: 线段树+单点更新

分析:

1 线段树的水题

点击查看代码

第三题 hdu 1394 Minimum Inversion Number

点击打开hdu 1394

思路: 线段树+单点更新

分析:

1 题目要求的是n个数的n个序列中找到的最小逆序数对

2 首先我们都知道所谓的逆序数对就是给一个序列，如果前面的数比当前的数大，那么这两个数就是逆序数对。比如4 1 3 2中逆序数有 4 1, 4 3, 4 2, 3 2

3 那么我们可以很快的利用线段树求出起始数组的逆序数对，那么我们接下来考虑把第一个数换到最后一个位置的情况

   假设现在起始的序列的逆序数对有sum，那么第一个数num[1]换到最后一个位置的后果就是使得所有比num[i]小的数度不能和num[i]构成逆序数了，那么直接减少的个数就是n-1-num[i]，但是那么比num[i]大的数可以和num[i]构成逆序数，因此增加了n-num[i]个。因此换完之后的序列的逆序数对为sum-(n-1-num[i])+n-num[i];

4 因此我们只要去做n次的比较，求出的最小值即为ans

点击查看代码

第四题 hdu 2795 Billboard

点击打开hdu 2795

思路: 线段树+单点更新

分析:

1 题目的意思是给定一个h*w的广告牌h为高，w为宽，现在有n个高为1宽为wi的小广告要放上去，原则是最先放最上面和最左边的位置

2 题目的h和w的最大值为10^9，但是n最大为200000。所以我们可以知道最多用掉的广告牌就是x = min(n , h)，而这个值就是200000，所以我们可以把每一行作为一个点来利用线段树，线段树的区间[i , j]存储的是第i行到第j行的最大的剩余空间，那么我们只要每一次去查找整个区间[1 , x] ，然后我们要优先的考虑左子树，这样就能够满足要求的条件了

点击查看代码

第五题 poj 2481 Cows

点击打开链接poj2481

思路：线段树+单点更新
分析：
1 题目给定n头牛所在的区间，然后问每头牛都有几头牛比它强壮
2 根据题目如果牛i的区间是[Si , Ei]，牛j的区间是[Sj , Ej]那么牛i要比牛j强壮的话那么就有Si <= Sj && Ei >= Ej && Si-Ei != Sj-Ej;
3 那么根据上面的条件，我们应该要先对n头牛的区间排序”按照S从小到大，相同S按照E从大到小排序“，然后就可以利用线段树求了。
4 有一个地方需要注意的是当排完序后相邻的两个相等，那么只须更新不用求和。
点击查看代码

第六题 poj 2828 Buy Tickets

点击打开poj 2828

思路: 树状数组/线段树单点更新

分析:

1 题目给定n个人的位置pos和id，要我们求出最后n个人的位置

2 我们先来考虑朴素的算法，假设现在进来一个人那么我们把它放到pos的位置，那么pos之后的所有的人都要向后移动一位，那么n个人的话最坏的情况是O(n^2)，很显然时间效率上面是不行的

3 由于正向的插入不行，那么我们考虑反向插入的情况（就像逆向的并查集），那么我们可以马上知道第n个人的位置，那么第n-1个人的位置是基于第n个人的。假设第i个人的要插入pos的位置，那么这个时候我们只要把第i个放到第pos个空的位置即可（可以自己手动模拟一遍），那么我们维护空位置可以利用树状数组和线段树来维护

点击查看代码

第七题 codeforces 19D Points

点击打开cf 19D

思路: 线段树+单点更新

分析:

1 题目的意思是给定一些点和n个操作，这些点都是在原点(0 , 0)的右边，现在给定三种操作

   add x y 是把(x , y)这个点加入

   remove x y 是把(x , y)这个点删除

   find x y 是查找(x , y)点的右边的点满足x' > x && y' > y 并且有x'和y‘尽量的小

2 题目给定的数据是n是2*10^5，但是点的最大值为10^9，所以我们应该要进行点的离散化。但是我们只要对x进行离散化即可

3 我们利用set来保存每一个x对应的y的集合，然后我们利用线段树来维护一个x区间的最大的y。

   为什么要用线段树呢？因为我们知道我们只要只要当前区间的最大值就能够判断是否有没有存在这样的点，然后我们利用二分逼近的思想去求出这个x。只要我们求出了x，那么我们就可以利用之前的set来找比y大的y'，这一步可以利用set的内置的lower_bound

4 有一点很重要的就是，由于set和map的存储结构不是线性的，因此它们内置了lower_bound和upper_bound，所以我们利用内置，如果使用通用的时间效率及其底下

点击打开查看代码

第八题 poj 2886 Who Gets the Most Candies?

点击打开poj 2886

思路: 求因子数+单点更新

分析:

1 题目的意思是有n个人构成一个环，刚开始是第k个人先出来。每个人有一个名字和数值A，如果A为正数，那么下一个出去的人是他左边的第A个人，如果是负数那么出去的将是右边的第A个人

2 这么我们要注意一下，因为n个人是围城一圈，那么左边就是顺时针方向，右边就是逆时针方向

3 那么我们就可以来推没一次出去的人的在剩下中是第几个。

   假设当前是第k个人出去，并且这个人的值为A，并且剩下有sum个人

   A > 0 , 因为这个人出去了，那么后面的人的编号会先减一，那么下一个出去的人就是剩下中的 (k+A-1)%sum，因为我们知道%sum的结果是0～sum-1，但是我们要得到1～sum的结果，因此我们可以这样 ((k+A-1)%sum-1+sum)%sum+1。怎么理解呢，比如x%3，那么结果就是0～2，为了得到结果为1～3，那么我们可以这样(x-1+3)%3+1，括号里面加3怕负数的情况

   A < 0 , 因为这个人出去，对前面的人是没有影响的，因此编号就是 ((k+A)%sum+sum-1+sum)%sum+1，根据上面的解释以及怕出现负数的情况，我们多加了sum来抵消

4 我们现在求出了每一次出去的人是剩下人中的第几个，但是我们怎么去求出具体的是哪一个人呢？

    这个时候我们就可以利用线段树来维护，线段树的区间维护的是当前这个区间还有多少个孩子，那么我们只要查找前面求出的第几个孩子就可以得到编号

点击打开查看代码

【成段更新】

【区间合并】

【扫描线】