一蓑烟雨任平生

树形转线性，然后用树状数组维护就行，单点更新，区间查询，但是辣鸡POJ卡vector窝日，所以用链式前向星存就行 #include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long l

B题：卿学姐与基本法 题意：给一段区间，长度为1e8，Q次操作（Q）， 操作有两种，一种是将某个区间进行染色，另一种是查询某个区间未被染色的长度   离散化+线段树求区间染色 呃，离散化很简单咯，我的做法就是sort+unique+lower_bound搞定，聊天中柱爷突然说了一句，其实unique可以没有，想了想，真的诶，如果不要求编号必须连续的话，是可以没有unique的，但是习惯有

A题 题意：有一个数列，长度为10^5，初始全为0 要求支持两种操作：单点更新和区间查询最大值 操作次数10^5， 另：答案可能会爆int，所以用long long存   唔，线段树裸题，存的是最大值，所以更新时的push_up是： tr[id].mx=max(tr[lid].mx,tr[rid].mx); 然后就可以了，   坑点就是爆int，咦，对，还有就是更新的时候是加上

概率dp，推一个概率公式就行。i==2时那里写错了一个+-号，wa了两发 代码： #include #include #include #include #include #include #include using namespace std; #define maxn 1005 double dp[maxn][maxn]; int w, b; int main()

妈个鸡，要不是队友提醒，我能把题面上的那封情书读完，读了一半多了都 然后题意就是，在一个平面直角坐标系上，有一些点，每个点有一个权值，用一个矩形框去框住他们，问怎么才能使框住的所有点的权值和最大，边界上的点不算。 边界上的点 不算，我之前只做到过一次边界上的点算的啊，怎么办，把长和宽都各自-1就好啦。处理之后，设长为w，宽为h。 大概就是，把一个点沿一个方向，假如说是x轴，沿x轴向正方向延长

有一个W*H的矩阵 ，里面有n个家具，相互之间互不重叠。现在有一个1*M的家具，想问有多少种放法（横放，竖放都可以） 对于每个矩形（家具），我们把它横向向x轴正方向延长M-1个单位，然后，所有剩下的没有被覆盖的点就对应一个可以放新家具的位置，有多少个点就有多少种横放的放法。所以问题就变成了，总面积-矩形面积并的问题了。对于竖放，就是纵向延长M-1个单位。 所以重点就是求矩形面积并，就是扫描线的

先复习一遍线段树。。。。 代码： #include #include #define maxn 100015 #define lid (id<<1) #define rid ((id<<1)|1) #define LL long long long long a[maxn]; struct segtree { int l, r; long long sum, lazy; }tr

马上要写一道线段树+扫描线的题，先把很早之前写过的一道复习一下。 代码： #include #include #include #include #include #include using namespace std; struct edge_mode { int y, l, r, val; void edge_make(int y,int l,int r,int

秋实大哥有一些菜，每个菜有标号CID，也会来一些客人，每个客人也有标号PID。 对于每个客人， PID^CID （此处为异或）值越大，他越喜欢。 输入：第一行是一个n(1 接下来m行，有两种，一， 0 c：表示新研制出来一道标号为c的菜。二，1 p：表示来了一个标号为p的客人，请输出他最喜欢的菜。 字典树来做，用字典树按01分叉，从第20位开始分一直到第0位，然后将这个数保存进来，

有N个独立的点，标号为1，2，3，…N。现在要把他们连接起来，每次选取x和y两个点，x是它所处集合的中心，y不一定是它所处集合的中心，然后在xy间连一条长度为|x-y|mod1000的边。然后把这两个集合合并起来，新集合的中心是原y所处的集合的中心。有两种操作，I x y表示选取x和y合并。E x表示查询x到它所处集合中心的距离。O表示结束。 并查集的套路，但是在查询的时候，路径压缩的时候，更新点到集合中心的距离即可。

并查集+离线处理 代码： #include #include #include #include #include #include using namespace std; #define maxm 100002 #define maxn 20002 #define maxq 5002 int set[maxn]; int size[maxn];//结点数 struct

链接： http://www.acm.uestc.edu.cn/#/problem/show/1061 题意：就是有一排士兵，在某个时刻，某个士兵可能会死，序列就会从这里断开，在某个时刻，某个士兵可能会被复活，然后查询任意时刻，这个士兵所在的序列长度。 解：说实话，我对这个题有恐惧感，因为看他们讨论时感觉好怕怕的样子，然后自己写了一发，最暴力的方法，然后改了一个傻逼笔误，就过了，跑的时间也

题目链接：http://www.acm.uestc.edu.cn/#/status/list?problemId=203 题目大意：有一个岛屿是n*m的长方形的，每个格子的高度会给定，然后这个地方的水位会逐年上涨，在第i年时水位是i。就是说，所有高度 现在给出n和m（1 解：啊，看的别人的题解都说，这种连通块的题，一看就用并查集搞，不过想想，Kruskal就是用并查集搞的，貌似是这个道理（雾

秋实大哥与妹纸 致中和，天地位焉，万物育焉。秋实大哥是一个追求中庸的人。 虽然秋实大哥的仰慕者众多，但秋实大哥不喜欢极端的妹纸。所以他想从所有仰慕自己的妹纸中挑选出一个符合中庸之道的。 每一个妹纸对秋实大哥的仰慕程度可以用一个整数ai来表示，秋实大哥想要找出这些数的中位数。 计算有限个数的数据的中位数的方法是 把所有的同类数据按照大小的顺序

秋实大哥搞算数 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) 秋实大哥大学物理挂科了，于是在下学期的前两周的某一天要悲剧的补考。为了不给学校的挖掘机大楼做贡献，秋实大哥决定在假期里努力复习。当然，良好的计算能力也是非常必要的，毕竟是涉及计算自己做多少分的题能够通过考试的

C题：卿学姐与诡异村庄 就是有N个人，每个人会指控另一个人为好人或者坏人，然后如果这个人是好人，那他说的就是真的，如果他是坏人，那他说的就是假的，然后问是否存在一种合法情况 N   一开始听说是并查集，但是没有完整的思路，总想的是，分假设某个人为好人和坏人两种情况，然后顺着链往下走，走到非法情况就停止，但总觉得漏洞百出。 讲题了之后才明白正确做法，很优美，也很简单， 就是并查集，把A分

D题：卿学姐与魔法 就是有两个长度为N的序列A和B，N， 然后输出A[i]+B[j]（i可以等于j）组成的N*N个数中最小的N个   可以用小根堆，也可以不用堆。 用堆的做法，把A数组升序排序，B可排可不排，然后可以得到N个序列 A[0]+B[0],A[1]+B[0],A[2]+B[0]....A[N-1]+B[0] A[0]+B[1],A[1]+B[1],A[2]+B[1]....

R - Japan 坐标有n个城市，右边有m个城市，城市都是按序号排序的，然后有K条连线，然后问连线的交点有多少个 也是类似于逆序数，不过跟E题不同的是不用考虑在左端点或者右端点的交点，只考虑交在中间的，也不用离散化 首先我们把每条线段按左端点升序排序，左端点相同按右端点升序排序 然后因为我们只数交点在中间的，所以我们首先找到同一个左端点的序号范围，假设当前为[i,j)，序号编号是从0开始

Q - 昊昊爱运动 II 题意，区间长度N，N为1e5，运动种数为M，M Q次操作，Q，每次可以把一个区间的运动都换成x，或者查询一个区间的运动种数   在放宽了时限和内存之后，bitset就直接搞过去了   之前因为卡的太紧，我就用两个long long模拟的bitset，另外线段树也没有存左右端点，是在更新和查询的过程中用形参来保存的   具体做法就是每个节点存一个bits

P - 浑身难受 maya，camp上搬来的神题，作为一名智障 一共二十四种情况，然后每种倒序一下可以得到另外一种，所以可以简化成12种，然后我这个智障就写了十二种， 首先分为3类， 1，  1和4不相连，就n^2枚举2和3的位置，然后1和4的所在的区间用按值树状数组维护，1那里就是查询区间有多少比个比2小的值，4那里就是查询有多少个比3大的值（总点数减去的就是啦），然后乘一下就可以

O - 卿学姐种美丽的花 给一个区间，等差数列更新，单点查询 我们可以开一个线段树记录这个点被更新的次数，然后因为是区间更新，所以我们需要一个lazy，lazy表示这个区间的被更新的数列的首项是多少，还有一个cnt，表示公差，因为两个数列加和到一起时，公差也会相加，所以就是这样了，然后lazy下放的时候，也是计算下两个子区间的首端点的位置是多少，相当于把这个数列分为两个子数列 然后我们就

N - 秋实大哥搞算数 给一个表达式，无括号，保证合法，long long以内，整数运算，求值 栈 表达式求值的经典问题， 首先设置一个开始和结束符号#，他们的优先级是最低的，然后开两个栈，运算符栈和运算数栈，如果当前要放的运算符优先级高的话，就放进去，然后继续模拟，如果当前要放的运算符优先级低的话，就取出栈顶的运算符，和运算数栈顶的两个数，进行运算，然后继续检查，直到栈空或者栈顶运算符

M - 卿学姐失恋了Ⅱ 给你一个合法的汉诺塔状态，问你能否在M秒之内把他们都放到一根柱子上，圆盘总数是20 首先我们可以知道，我们最后要放到的那根柱子一定是0号盘子，就是最大的盘子，所在的柱子，为什么这样呢，因为不这样的话，我们就要移动0号盘子，我们想移动0号盘子，那么其他所有的盘子都必须移到某一根柱子上，这时我们可以把0号盘子移到另一根柱子上，然后再把其他所有的盘子移到0号盘子所在的柱子

L - 郭大侠与苦恼 题目简单，就是给你一棵树，然后问异或值为0的简单路径有多少条 好难，好麻烦，想了好久才想明白 按dfs的顺序来map+启发式合并， 后来想找个题的大概框架和树形01背包相似，都是用dfs来实现的，只不过树形01背包dfs后的过程是背包的合并，这个是map的合并，还是启发式合并（就是把size小的合并到size大的上）， 然后我们这里维护的是pre[u]，就是从根

K - 郭大侠与甲铁城 有一个区间，长度1e5，每个点有一种颜色，颜色属于[1,1000]，离线询问某个区间的颜色种树，询问次数也少1e5 我的做法是离线树状数组 首先把区间保存下来，按右端点升序排序，然后我们建树状数组，同时也开一个last数组记录所有颜色的最后的出现位置，初始为0，即没有出现， 然后我们对于每个r，就从1（或上次更新到的位置）更新到这个r，然后我们更新时，对于这个点

J - 郭大侠与Rabi-Ribi 就是有N只兔子，每只兔子会存在a[i]秒，价值为v[i]，然后每秒只能取一只兔子，问能取的兔子总价值的最大值是多少 用一个堆/优先队列维护就好了 首先我们先把兔子按存在时间升序排序，然后第一秒的时候，我们取第一只兔子，并放进堆中，堆是小根堆，按兔子的价值排序的，堆顶为价值最小的兔子 然后我们就一秒一秒的取，如果下一只兔子的存在时间>=当前时间，那就直

I - 郭大侠与线上游戏 就是给你一个队列，支持队尾插入和队头弹出，或者询问当前队列里的数的中位数 别人跟我讲stl黑科技能过，然后我就套pb_ds，就过了 这个pb_ds只在linux下可以，但是评测姬一般都是linux下的，所以都能用，本地用就用mingw，然后我用的是Tree-Like Container，可以查询区间第k大，然后k就取中位数就好了   如果不用这个黑科技的

H - 郭大侠与英雄学院 就是给你一个n*m的矩阵，然后叫你缩小这个矩阵，而且每行每列的数之间的大小关系不变，而且全为正数。 开始时想了好久也没想出来 先讨论没有重复点的情况，就是先把所有点按值升序排序，然后依次往新矩阵里放，放时的新的值为max(它所在行的最大值，它所在列的最大值)+1。然后这么放就行 但是有重复点，就比较麻烦了，而且只有同行同列的重复点才会产生影响，就是他们在新矩阵

F - 郭大侠与“有何贵干？” 就是给一个三维空间，和N个长方体，问覆盖K次的体积 x和y都是1e9，但是z是[1,3]，所以可以把这个分为两个二维平面，求被覆盖K次的面积，最后加一下就行 然后就转换成了二维平面求覆盖k次的面积，k属于[1,10]，然后就是，先离散化，然后线段树+扫描线 具体做法，就是，线段树节点开一个sum[12]的数组，然后i时，sum[i]表示覆盖i次的面积，当

E题：卿学姐与城堡的墙 有N条直线，以y=kx+b的形式给出，问有多少种方式任取两个直线，使这两个直线的交点在x=u和x=v之间 对于两个直线a和b，怎么判断他们的交点在x=u和x=v之间呢 假如直线a在x=u时的纵坐标为yau，在x=v时的纵坐标为yav，直线b在x=u时的纵坐标为ybu，在x=v时的纵坐标为ybv。假设yau在ybu的下面，但是yav却在ybv的上面，那中间就是一定有交点

G - 郭大侠与阴阳家 给n个二维平面上的点，n属于[1,2000]，x和y是[1,1000000000]，唔，这题好像没用什么数据结构，可以用map，但是感觉强行map，不map感觉完全没问题   坑点有两个，重点，共线，重点简单，把所有点sort一遍，然后unique一发就可以， 共线，就需要先建立向量然后再处理了， 首先，能 组成平行四边形的条件是这两条向量平行且模长相等，所以

本文部分代码及思路来源于：http://www.cnblogs.com/Xiper/p/4470202.html 秋实大哥与小朋友 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) 秋实大哥以周济天下，锄强扶弱为己任，他常对天长叹：安得广厦千万间，大庇天下寒士