[综合] POJ2299 Ultra-QuickSort(树状数组求逆序数+离散化）

题意： 给一个n个整数组成的序列，每次只能交换相邻的两个元素，问你最少要进行多少次交换才能使得整个整数序列上升有序。 题解： 冒泡排序的交换次数等于数组中所有数的逆序数之和。逆序数可以用树状数组求出。具体操作： 构建范围为1-n的树状数组，每次出现一次，该位置就加1，所以对于每个j，树状数组得到的前...

[综合] POJ 2352 Stars(树状数组，查数)

题意： 二维平面给定n个点(任意两个点不重合)的坐标，然后要你输出每个点的“等级“。每个点的等级是它的左下放的点个数(包括正下放和正左方的点)。最后输出每个等级的点的个数。 题解： 任意两个点不会重叠，且给出点的顺序是：按Y坐标上升的顺序来给出，如果Y相同就按X上升的顺序给出。 给出的顺序是完美的，...

[综合] POJ 2481 Cows(树状数组，查数)

题意： 有n头牛，每头牛对应一个区间[Si，Ei]，如果牛j的区间是牛i的区间的真子集(即Si<=SjandEj<=EiandEi-Si>Ej-Sj)，那么就说牛i比牛j强壮。要你依次输出比第i头牛强壮的牛数目。 题解： 将所有的牛的E区间按从大到小排序，如果E相同则S小的排在前...

[综合] POJ 3067 Japan(树状数组，逆序数变形)

题意： 水平方向有2n个城市点，他们分别按顺序分布在平行的两条直线上，编号都是从1到n。然后现在在上直线与下直线的两个城市点之间建公路，一共建k条公路。问你这k条公路一共有多少个交点(保证最多只有两条公路会交于同一点)？ 题解： 注意题目中两边的岛是这么分布的: 1234 1234 且一个点最多只有...

[综合] HDU 3450 Counting Sequences(树状数组，离散化，中等题)

题意： 给定一数列，问最多存在多少完美子序列。完美子序列定义如下： 原序列一共有2的n次方个子序列，这些子序列满足这样的关系：子序列元素个数至少2个，且任意相邻的两个元素之差不超过d。 题解： 每次新来一个元素x，都要去前面扫描有y个大于等于x-d且小于等于x+d的元素，然后以他们为结尾的完美序列...

[综合] HDU 2838 Cow Sorting(树状数组应用)

题意： 不翻译了~ Sherlock'sN(1≤N≤100,000)cowsarelineduptobemilkedintheevening.Eachcowhasaunique"grumpiness"levelintherange1...100,000.Sincegrumpycowsaremorel...

[综合] POJ 2182 Lost Cows(树状数组，暴力模拟)

题意： 一数列1-n，顺序为乱序，然后从第二个开始，给出每个元素前面有多少个比该元素小的。求原始数列。 题解： 手动模拟一下怎么还原数列： 从后往前找，弄个标记数组，找就行了，直接暴力。 然而碰到“前面有少个比他小”这样的字眼，树状数组很快的进行求解。在从后往前的过程中，vis数组存放的已经出现的...

[综合] POJ 1990 MooFest(树状数组 标记计数应用)

题意： 有N头牛，每个有两个属性：距离和权值，任意两个都可以交流，两头牛交流的花费是其中权值较大的权值。问所有的牛可以两两交流，共需要花费多少权值。 题解： 按照V从小到大排序，当前处理的就是最大的。然后怎么去找在他之前的牛的d和在它之后的d呢？在它前面的d总和可以用树状数组标记法去求，在它之后的...

[综合] HDU 1556 Color the ball(树状数组，区间更新+，单点查询)

题意： 问题等价于：一个大小为N的数组，初始全为0，然后每次区间+1，求最后单点的值。 题解： 线段树可以很好的解决这种区间更新的问题，但是这里用实现较简单的树状数组实现。 举个栗子： [3,5]区间+1,执行add(3,1),这时候sum(1)=0,sum(2)=0,sum(3)=1,sum(4...

[综合] HDU 3874 Necklace(树状数组+离线hash)

题意： 一个由n个整数组成的数列，求区间[L,R]上的和，其中相同的元素只能算一次。 题解： 对于原数组，hash记录每个元素出现的位置。然后把所有元素只添加一次进树状数组。离线初始数组和要查询的所有区间。把所有的区间按照L从小到大排序。 对于第一个区间，假设L=1，那么直接就sum(R)就是第一...

[综合] RMQ学习

RMQ(RangeMinimumQuery)问题 有关RMQ的详细介绍可见刘汝佳《算法竞赛入门经典训练指南》P197页 RMQ问题可以解决对于一个整数数组(当然也可以是其他可比较大小的元素类型)的任意区间[L,R]查询最值时，以O(1)时间复杂度回答询问。其实它就是一种数据压缩的思想。 RMQ能在经...

[综合] POJ 3264 Balanced Lineup（RMQ入门模板题）

题意： 求区间最大值与区间最小值，输出两者之差 题解： 前面用线段树写过，不过裸的区间最小值与最大值问题，RMQ问题中ST算法可以很好的实现，并且效率很高！ #include<cstdio> #include<iostream> #include<algorithm&...

[综合] POJ 3368 Frequent Values(RMQ，需要转换)

题意： 给一非递减数组，求区间[L,R]中出现次数最多的值所出现的次数。 蓝书P198有详细分析。 题解： 游程编码：（a,b）表示有b个连续的a。 比如-1,1,1,2,2,2,4可以这样表示： (-1,1),(1,2),(2,3),(4,1)。需要用一些的数组记录！具体看代码注释。 然后求一个...

[综合] HDU 3193 Find the hotel(RMQ，需要转换，巧妙二维变一维)

题意： 给定n个旅馆的p和d两个属性，然后输出所有的目的旅馆。如果对于所有的旅馆i来说，没有其他任何一个旅馆的px和dx值同时小于pi和di。那么旅馆i可以算作一个是“目的旅馆”。 题解： 这个题和蓝书P228相似，但是好难用画图法转化，转化了半天也没转化对。 这里的解法是将二维转化为一维，定义数...

[综合] POJ 1785 Binary Search Heap Construction(RMQ递归写笛卡尔树)

题意： 每个节点有两个信息：string值和r优先级。要求构建一个Treap并且任意节点的string和r都是唯一的。最后按要求输出该Treap的序列。 题解： 直接写蓝书的Treap会超时，有种笛卡尔树的Treap可以写。（暂时还没看） 这里用RMQ递归写。 #include<iostre...

[综合] ZOJ2112 Dynamic Rankings(动态主席树）

题意： 在静态主席树的基础上，增加修改。 题解： ===在写 #include<bits/stdc++.h>usingnamespacestd;constintmaxn=60009; inta[maxn],sor[maxn]; inttree1[maxn],tree2[maxn],lso...

[综合] D-query SPOJ - DQUERY (主席树 or 树状数组，hash）

题意： 给定一数组，查找区间上不同的数种类有多少。 题解： 好多把这道题看做模板题，但和曾经写过的一道树状数组题很像。这里提供两种解法： 主席树解法是记录重复的次数，然后最后总的去减。 #include<bits/stdc++.h>usingnamespacestd;constintma...

[综合] HDU 3183 A Magic Lamp（贪心 or 转为RMQ）

题意： 给出一个n位数，删除m位，使得剩下的数最小 题解： 老师上课讲贪心的时候，说过删1位的情况。贪心策略如下： 对于n位数构成的数删m位，每次总这样删除a[i]：它是第一个满足a[i]>a[i+1]的，如果不存在就删除a[n]。比如176832，删7。假设删其他的这个7在那里碍事都不会使...

[综合] 覆盖的面积 HDU - 1255 （线段树）

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积. Input输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表...

[综合] Oulipo POJ - 3461 (KMP模板)

题意: 给你一个T串和P串,问你P串在T串中出现了多少次. 分析: 直接套用KMP模板即可.注意失配指针最后一个'\0'也有定义. #include<cstdio> #include<iostream> #include<cstring>usingnamespa...