hdu1542题目链接 题意： 求n(100)个矩形的面积并。 思路： 扫描线+线段树 题目是2000年中欧区域赛的题目，虽然年代久远，但是有好几个点还是很值得学习的。 首先是离散化的适用范围: 之前比较常用的是将比较大的整数值离散化，常常是因为数值太大无法作为下标。 那么其实，浮点数有的时候也需要进行离散化，比如作为数组的下标，比如用来枚举。 做法上是和将较大的整数值离散化没有区别，因为遇到的题目不多，所以特意记录一下。 第二点是扫描线的思想： 其实扫描线的思想很早就接触过，noip2011的时候，tyvj上有一道类似的题目，不过是一唯的，当时印象深刻的是@Ocean 兄的那个比喻： 一段公路上右很多区间要收不同的费用，区间的开始 …

题目链接 题意：n（1E5）个操作，分为三种，add x表示将x加到集合中（保证集合中之前没有x)，del x表示从集合中删掉x(保证集合中一定右x),sum表示求集合中所有元素按从小到大排列后，所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9 思路：很容易想到的是，由于插入和删除元素造成的位置改变是剧烈的，因此要分别维护i%5==k,k属于0..4的元素的和。 这道题的核心点在于，由于只有1E5个操作，我们可以将元素离散化，这样做的目的是，将每个数和位置一一对应，每个位置用1或者0，表示该位置对应的元素是否在集合中。 考虑线段树，维护6个域，1个是区间中，在集合中的元素个数，剩下5个域，分别表示以该区间的端 …

题目链接 题意：给出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 …

题目链接 题意： 在二维坐标平面内进行_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轴方向维护一课线段树，线段 …

cf682B题目链接 题意：给出n个数。。每个数可以任意减小到一个正整数。。。问进行恰当的操作后。。。最小的没有出现的正整数的最大可能取值。。 思路：傻逼题。。。直接离散化。。。。注意不能超过初始。。。 /* *********************************************** Author :111qqz Created Time :2016年07月18日 星期一 12时43分41秒 File Name :code/2016whus/B.cpp ************************************************ */ #include <cstdio> …

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid;=8&page;=show_problem&problem;=56 题意：给出一个长度为n的序列（无重复元素），询问经过多少次flip(i)操作，使得序列升序排列。定义flip(i)为将1到n-i+1的元素反转... 思路：先离散化，然后注意读入.... /* *********************************************** Author :111qqz Created Time :2016年01月25日 星期一 10时42分46秒 File …

http://codeforces.com/contest/29/problem/C 题意：给出n个边的关系，保证可以构成一条链。正向或者反向输出这个链。 思路：由于下标很大(1E9)，而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs... /* *********************************************** Author :111qqz Created Time :2015年12月30日 星期三 19时55分15秒 File Name …

Inversions **Time Limit:**250MS **Memory Limit:**4096KB 64bit IO Format:%I64d & %I64u Submit Status Description 180. Inversions time limit per test: 0.25 sec. memory limit per test: 4096 KB input: standard output: standard There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find …

这道题可以总结的地方不少。 １：对于一组乱序数列，每次只能交换相邻元素，达到有序交换的次数就是原数列中你逆序对的个数。 　cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。 ２：原始数组a[i]和树状数组的t[i]的对应问题（？？？存在疑问。。。应该只是这道题，而不是一般规律！） 　这道题n是５０００００，如果直接开数组是可以开得下的，不需要离散化。**但是树状数组的下标对应的是原始数组的值！**也就是t[i]的下表最大可能为９９９，９９９，９９９　！　显然存不下，需要离散化。 **３：学习了离散化的又一种写法。 ** …

wa了两次，原因是在同一个点可能有多个基地。。。 所以用set 是错误的，应该用multiset 然后因为这道题看到了map+set实现离散化的另外一种写法 我的代码： /************************************************************************* > File Name: code/hdoj/4022.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月01日 星期六 04时37分20 …