线段树

题目链接 题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换 n 次以后得到的数列中，逆序对的个数。

题目链接 题意：圆上，询问任意一段弧中，任意两点的距离+两点的权值和的最大值。

题目链接 题意：有 n 个数，每次可以删除掉数值相同并且所在位置成等差数列（只删 2 个数或者只删 1 个数应该也是可以的），删掉这些数以后可以将剩下的数重新以任意顺序排列，称为一次操作。现在给出 m 个询问，每个询问一个区间 [l,r]，问删光区间 [l,r] 中的数最少需要的操作次数。

题目链接 题意：给出 n 个数，然后 m 个询问，每个询问一个区间 [l,r]，问该区间中不同的数有多少个。

题目链接 题意：题意是由伪代码给出的，手算模拟了一下（noip 初赛即视感），题意大概是说，给出两个数组 a 和 b，a 数组长度为 n，b 数组长度为 len，然后从 a 中截取连续的 len 个元素，称为数组 s，如果存在一种方法使得 s 中元素和 b 中的元素一一对应且每组和都大于等于 h，则称这个 s 是合法的。现在问 a 中有多少个合法的 s。 具体来说，对于样例 5 2 10 5 3 1 8 5 5 7

1756: Vijos1083 小白逛公园 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1078 Solved: 353 [Submit][Status][Discuss]

题目链接 题意：给出n个数，m个修改，每次修改后询问整个区间的最大连续子段。

题目链接 题意：给出两个排列，定义 ord(p) 为排列 p 的顺序（字典序从小到大），定义 perm(x) 为顺序为 x 的排列，现在要求 1 ≤ n ≤ 200 000

题目链接 题意：给出一个长度为n的数列，每个位置是0或者1，给出q个操作，操作有两种类型，分别是将一段区间中反转，和询问当前某位置是0还是1

题目链接 题意：现在有N个骑士进行M轮PK…现在告诉这M轮是谁站在台上…其将l~r所存在的骑士都打败..而若一个骑士被打败..就出局了..也就是不存在了…请输出每个骑士是被哪个骑士打败的(最后的胜利者输出0)…保证有解..

题目链接 题意：给出两个数组，每个数组 n 个数，分别为 a 和 b，给出 m 个操作，操作有两种类型，第一种是给出 x,y,k，表示从 a 数组的 x 坐标开始复制 k 个数到 b 数组的 y 到 y+k-1。

题目链接 题意：给出n个数，m个查询，每组查询一个区间[l,r]，问[l,r]中会被吃掉多少个（区间[l,r]中的数只有当其是其他所有数的因数时才不会被吃掉，顺便问一句。。a divide b 是 a除b，也就是b除以a,b/a的意思嘛23333）

题目链接 题意：给出n个数，求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。

题目链接 题意：定义_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).

题目链接 题意：给出n和m，初始给出1«n个数，先相邻的两个数进行或操作（a[1]^a[2],a[3]^a[4]…），得到的新数列再相邻的两个数进行异或操作。

题目链接 题意： 在二维坐标平面内进行 n (1 ≤ n ≤ 2·10^5) 次操作。一共有三种类型操作。

poj 2828 题目链接 题意：n个人，每个人有一个rp值（用来区分不同的人），还有一个pos[i]，表示当第i个人来排队的时候插入到第pos[i]个人的后面（也就是排在位置pos[i]+1)

hdu 1754 题目链接 题意：单点更新，区间查询最大值。 思路：线段树。

嘛，终于下定决心搞定线段树了。 之前几次都是被lazy标记卡住，这次大概不会了吧2333

http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：一个尺寸为wh的方格。要按顺序放放n个尺寸为1wi的纸条。问每一个纸条回被放在哪里。如果有多个，放在最上面（编号小） 思路：把没横行能放的最大长度看做一个序列建树。由于h比n大很多。。多出来的没用。。直接取较小值就行。