1230: [Usaco2008 Nov]lites 开关灯 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 1676 Solved: 874 [Submit][Status][Discuss]
Description # Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候， 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关； 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= M <= 100,000)条指令， 每个指令都是两个整数中的一个(0 <= 指令号 <= 1). 第1种指令(用0表示)包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 它们表示起始开关和终止开关. 奶牛们只需要把从S_i到E_i之间的按钮都按一次， 就可以完成这个指令. 第2种指令(用1表示)同样包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 不过这种指令是询问从S_i到E_i之间的灯有多少是亮着的. 帮助FJ确保他的奶牛们可以得到正确的答案.
hdu3642题目链接
题意：给出若干个（1000）长方体，求至少交三次的空间的体积。
尺寸为[x1,x2],[y1,y2],[z1,z2]，其中x，y的坐标的绝对值不超过1E6，Z的坐标的绝对值不超过1E9。
题目链接
题意： # 求矩形周长并。
思路： # 线段树+扫描线。
题目链接
题意： # 求n（1000）个矩形的面积交，也就是至少有2个矩形覆盖的区域的面积。
思路： # 和矩形面积并_hdu1542解题报告 类似
hdu1542题目链接
题意： # 求n(100)个矩形的面积并。
思路： # 扫描线+线段树
zoj3606题目链接
题意：有个小女孩卖火柴，有n个人会来买，分别在时间t[i]，以价格p[i]，买的火柴个数为1+(k-1)%3，其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴，小女孩就会睡着。小女孩睡着后如果有人来买火柴，那小女孩就会醒过来，但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。
题目链接
题意：n（1E5）个操作，分为三种，add x表示将x加到集合中（保证集合中之前没有x)，del x表示从集合中删掉x（保证集合中一定有x）,sum表示求集合中所有元素按从小到大排列后，所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9
1012: [JSOI2008]最大数maxnumber # Time Limit: 3 Sec Memory Limit: 162 MB Submit: 9717 Solved: 4244 [Submit][Status][Discuss]
Description # 现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L 个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加 上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取 模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个 数。
e：题意：那个数，定义hill为一段连续的区间，满足该区间为严格单峰。现在有若干操作，每个操作是对某段区间的数同时增加一个数，问每次操作后，所有的hill中，宽度最大的（区间长度最大）的是多少。
题目链接
题意：
地主小花有n座山，这些山在地主家门前排成一条直线。这些山一开始均有相同的高度。 每一天，小花都会要求ZJiaQ开挖机把几座山挖掉一定高度，或者给一些山堆上一些高度。并且要求报告ZJiaQ报告现在有多少座山属于“高山脉” 当一排山的高度相等，并且比这排山左边和右边的山要高时，这排山被称为高山脉。 当然，最左边和最右边的山不可能是“高山脉”的一部分 思路：线段树，要维护的域蛮多的。
题目链接
题意：长度为n的序列，单点更新，或者询问某一个区间中最长连续严格递增序列的长度是多少。（此处的连续为位置连续，并非数值连续，也就是3,5,7,9，这样的就是满足题意的长度为4的序列）
题目链接
题意：给出n(n<=200000)个数，问所有区间[l,r]中mex的和。 （一个区间mex的定义为，这个区间中没有出现的最小的非负数）
思路：我们观察到mex(1,i)随着i增大，是不减的。(单调是线段树查询区间的时候非常好用的东西，这也是此题的突破口)
题目链接
题意：给一个仅由小写字母组成的字符串，然后m个操作，每个操作一个区间，要求把区间中排列成字典序最小的回文串，如果不能形成回文串，就忽略该操作。
思路：和上一道线段树优化计数排序的题目很像，几乎是一样的。
题目链接
题意：给出一个字符串，仅由小写字母组成。现在给出q个操作，每个操作l,r,k三个参数，k=1表示把区间[l,r]变为升序排列，k=0表示把区间[l,r]变为降序排列。
题目链接
题意：给出一串只由数字'4’和'7’组成的串。两种操作，一种是询问整个串中最长非下降子序列的长度，另一种给出区间[l,r]，将区间中的每个数反转，反转的定义为，4变成7,7变成4.
题目链接
题意：一个循环数列，两种操作，一种是把某段区间中加上v，另一种是询问某区间的最小值。对于每个询问，输出答案。
思路：区间更新+区间询问的模板题….
注意体会pushdown以及update的时候。。。
题目链接 题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5 个数（a[i] ai≤1E4)，给出 m组查询（m<=1E5），每组两个数 x,y 问 f(x,y) 是多少。
参考题解：茶姐的回答（下标好像搞错了，领会意思即可
官方题解
以及前置技能点是：斜率优化+线段树
题目链接 题意：给出一个由‘(’和‘）’组成的字符串。。。然后给出若干查询。。。每个查询一个区间，问区间中能匹配的括号数。。。
思路：考虑某一个区间中的括号匹配。。。其实是一个不断寻找’()‘然后删去的过程。。。
poj 2886 题目链接
题意：n 个人围成一圈，每个人身上有一个数，可正可负。从第 k 个人开始出圈，如果第 k 个人身上的数是 X，X>0，就左边第 x 个没有出圈的人出圈，否则右边第 -X 个人出圈。第 k 个人出圈得到的糖果数目为 f(k)，f(x) 表示 x 的因子个数。现在问谁能拿到最多的糖果，并且拿到了多少糖果。
题目链接
题意：n 只青蛙，第 i 只位于 x[i]，舌头长度为 t[i]。m 只蚊子，第 i 只蚊子所在位置为 p[i]，蚊子的大小为 b[i]。
蚊子按照出现顺序输入。
一只青蛙能吃到蚊子当且仅当蚊子和青蛙在同一个位置，或者蚊子在青蛙右边并且与青蛙的距离小于等于该青蛙舌头的长度。
