信息学竞赛中的离散化应用

信息学竞赛中的离散化应用离散化在竞赛中如果数据值的范围很淡，但是稀疏分布。可以考虑将这有限个稀疏分散的数据映射到一个相对小的数据范围内，以此提高算法的时空效率。这就是离散化处理。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：原数据：1,999,100000,15；处理后：1,3,4,2；原数据：{100,200}，{20,50000}，{1,400}；处理后：{3,4}，{2,6}，{1,5}。离散化是程序设计中一个常用的技巧，可以有效的降低时间复杂度。其基本思想就是：在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。例如，在建造线段树空间不够的情况下，可以考虑离散化。离散化模板假定有一个无限长的数轴，数轴上每个坐标上的数都是0。首先进行n（1<=n<=10^5）次操作，每次操作将某一位置x（-10^9<=x<=10^9)上的数加c。接下来，进行m(1<=m<=10^5)次询问，每个询问包含两个整数l和r。求出在区间[l,r]之间所有数的和。输入第一行包含两个整数n和m。接下来n行，每行包含两个整数x和c。再接下来m行，每行包含两个整数l和r。输出共m行，每行输出一个询问中所求的区间内数字和。输入样例：输出样例：33812036575134678这是一道典型的单点修改，区间查询的题目。执行n次在某位置x上的加上c，并且还询问m次给定区间的和这种问题。这种问题的解题利器就是前缀和。此题的问题在于修改位置。题目给出的修改位置x的数据范围，-10^9<=x<=10^9。无论是否能够开这么大的数组，这个范围的前缀和，预处理的时间复杂度也是10^9量级，是竞赛中无法接受的。而实际需要处理的数据量n,m都是10^5量级,相对10^9来说很小。只需要聚焦处理这10^5量级的数据即可。这就是离散化的基础。首先可以明确，在这题中离散化的对象是数轴的坐标。所以对于输入的位置x和对应的数值c，只需要把数轴下标放到数组f[n]中即可，这里的f[n]为离散化后的重映射数组。实操中，可以用结构体之类的方法创建一个二元组用于存储坐标x和对应的数值c。同理，按输入顺序向f[n]插入所有出现过的数轴坐标，形成f[n]数组。图中出现Lx、Rx，表示第x个区间的左边界和右边界。离散化的第一步完成后，可以看到这个离散化后的新数组有多个相同且无序的值。所以第二步就是对f[n]排序、去重，形成新序列。新序列中所有离散点对“紧挨”在一起了。但这个“紧挨”在一起的数组只是下标，不是实际的值。所以还要创建一个大小跟离散化后的数组f[n]一样大的数组S[n]用来存放未离散化前的下标值。最后可以通过一个find()函数，找出原下标经过离散化后的新坐标，并赋值。STL函数实现离散化lower_bound()函数的功能是在有序地数列中查找某个元素的相对位置，这个位置正好是做离散化时元素初值对应的新值。lower_bound()返回值是一个迭代器,返回指向大于等于key的第一个值的位置。lower_bound()的对象是有序数组或容器。上程序返回5。将key换成10，所有val都小于key,返回last的位置。输出8。没有-a，则输出返回的指针位置。unique()函数处理去重问题，即把相同的数据离散化为一个数据。unique()包含于<algorithm>头文件中,功能是将数组中相邻的重复元素去除。然而其本质是将重复的元素移动到数组的末尾，最后再将迭代器指向第一个重复元素的下标。例题：火烧赤壁曹操平定北方以后，公元208年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。隆冬的十一月，天气突然回暖，刮起了东南风。没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！题目给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。输入第一行一个整数，表示起火的信息条数n。接下来n行，每行两个整数a,b，表示一个着火位置的起点和终点（注意：左闭右开）。输出一行一个整数表示答案。数据规模与约定：对于全部的测试点，保证1≤n≤2*10^4，−2^31≤a≤b<2^31，且答案小于2^31。此题为典型的区间修改、区间查询板子题。可能唯一的问题就是区间过大，即a,b的值为2^31。这个数据范围直接开树状数组或线段树都不好处理。可以首先考虑小数据量。如果[ai,bi)中ai,bi的值很小，可以考虑用一个数组表示数轴。数组元素fi表示数轴上一个长度为1的区间是否被染色。例如fi=0表示区间[i，i+1]未被染色，反之被染色。接着暴力枚举每个区间，执行操作即可。但是若ai,bi很大则需要考虑离散化操作。离散化可以在保持原数值之间相对大小关系不变的情况下，将其映射为正整数，即对每个可能用到的数值分配一个编号，用编号来代替数值进行操作。这样可以将无用数值去除，只保留关键数值，达到压缩时间复杂度的目的。本题数据量过大，无法用一个f数组表示这个数轴，且模拟过程时间复杂度过大。但数轴上两个相邻端点，不一定是同一区域的端点，之间的所有点都可以一视同仁地视为同时被染色，或同时不被染色。代码略。有兴趣的朋友可以在网站留言区讨论代码，谢谢。例题：程序自动分析在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x1,x2,x3,⋯代表程序中出现的变量，给定n个形如xi=xj或xi!=xj的变量相等/不等的约束条件。请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2,x2=x3,x3=x4,x4!=x1，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。现在给出一些约束满足问题，请分别对它们进行判定。输入的第一行包含一个正整数t，表示需要判定的问题个数。注意这些问题之间是相互独立的。对于每个问题，包含若干行：第一行包含一个正整数n，表示该问题中需要被满足的约束条件个数。接下来n行，每行包括三个整数i,j,e，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj。若e=0，则该约束条件为xi!=xj。输出包括t行。输出文件的第k行输出一个字符串YES或者NO（字母全部大写），YES表示输入中的第k个问题判定为可以被满足，NO表示不可被满足。数据范围：1<=n<=10^5;1<=i,j<=10^9。此题变量之间的关系只有等于和不等于，且等于关系之间不会冲突，不等于关系之间也不会冲突。所以仅考虑等于关系和不等于关系之间的冲突。因此，此题可以用染色法或并查集预处理相等关系，求出所有相等关系连通块，再检查所有不等关系，判断冲突即可。题目的关键在于10^9的数据量无法作暴力处理，考虑到总共有10^5个关系，每个关系涉及两个变量，故只有2*10^5个变量，其余变量可以忽略，所以考虑离散化解决。收集所有变量标号，排序去重，导入c[]数组。用下标i代替标号c[i]。这样可以使得数量所见到2n以内，问题可解。代码略。有兴趣的朋友可以在网站留言区讨论代码，谢谢。例题:过度种植在一个笛卡尔平面坐标系里（则X轴向右是正方向，Y轴向上是正方向），有N(1<=N<=1000)个矩形，第i个矩形的左上角坐标是(x1,y1),右下角坐标是（x2,y2）。问这N个矩形所覆盖的面积是多少？注意：被重复覆盖的区域的面积只算一次。输入第一行整数N(1<=N<=10001),接下来有N行，每行描述一个矩形的信息，分别是矩形的x1、y1、x2、y2。其中-10^8<=x1,y1,x