难得有聊得来的妹子邀请我出去玩。。。。。 我竟然。。。。。。。。 我。。。。。 。。。。。 。。。。。 。。。。。 我好菜啊。。。。。。。

[题目链接](http://codeforces.com/problemset/problem/356/A) 题意：现在有N个骑士进行M轮PK...现在告诉这M轮是谁站在台上...其将l~r所存在的骑士都打败..而若一个骑士被打败..就出局了..也就是不存在了...请输出每个骑士是被哪个骑士打败的(最后的胜利者输出0)...保证有解.. 思路：由于先前被打败的骑士直接就退场了。。。所以如果不做判断。。那么之后胜利的骑士会干扰之前的结果。。。 可以在pushdown的时候加判断。。。 不过我觉得比较好的做法是。。。倒序处理。。。。 倒序处理。。。后处理的直接覆盖先处理的结果。。。因为后处理的在之前。。优先级更高。。。被覆盖掉的骑士其实 …

x题目链接 题意：给出两个数组，每个数组n个数，分别为a和b,给出m个操作，操作有两种类型，第一种是给出x,y,k,表示从a数组的x坐标开始复制k个数到b数组的y到y+k-1。 第二种操作是给出x，询问当前b[x]是多少。 对于每个第二种操作，输出结果。 思路：第一次写lazy标记的线段树。 今天突然就顿悟了。。。其实lazy标记的思想大概就是。。 对于某段区间的更新，如果没有查询到这段区间中任何一个数的时候。。。那么这个更新其实是无所谓的。。。 （让我想到了那个脑洞，就是整个世界都是一段程序，为了让你不察觉异常并且耗费尽量少的资源，所有场景只有在有人观测的时候才会被加载，不观测就用很少的资源随便处理一下233） 所以lazy标记， …

题目链接 题意：给出n个数，m个查询，每组查询一个区间[l,r]，问[l,r]中会被吃掉多少个（区间[l,r]中的数只有当其是其他所有数的因数时才不会被吃掉,顺便问一句。。a divide b 是 a除b,也就是b除以a,b/a的意思嘛23333） 思路：我们知道，不会被吃掉的数其实就是区间[l,r]中所有数的gcd,求gcd可以很容易用线段树办到。。。关键是还要统计该区间中等于gcd的数有多少个。 并不会做。 大概有两种做法。。。？ 一种是基哥@clq11111说的，将询问离线，然后从小到大排序插入，询问区间中等于x转化成询问区间中小于等于x的，和询问区间中小于等于x-1的，做差即为所求。 第二种办法是题解的讨论区部分的： 想了 …

题目链接 题意：给出n个数，求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。 思路：对于这种要求三个数满足条件的题目，老司机的经验是考虑中间那个数，这道题也不例外。 我们枚举j，通过求两次逆序对求出对于每个a[j]，满足a[i]>a[j]的i的个数，以及满足a[j]>a[k]的个数。 两个个数的乘积就是j作为中间数满足的三元组的个数，这样把所有的j累加就是答案。 其他的就是，要离散化，以及最后答案可能会爆long long? 1A，好爽啊哈哈哈。 /* *********************************************** Author :111qqz …

题目链接 题意：定义_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). 思路：可以通过o(n)预处理出f(1,i,a[i])和f[j,n,a[j]]，其实预处理的过程就是离散化的过程呢。。。 分别得到 1 1 2 3 2 3 4 4 3 3 2 2 1 1 所以答案其实就是第一组数在第二组数中找逆序数的过程。。。 我们不妨倒序处理。 需要注意的是，线段树维护的区间是0..mx，我整体增加了1. 线段树求 …

题目链接 题意：给出n和m,初始给出1<<n个数，先相邻的两个数进行或操作（a[1]^a[2],a[3]^a[4]...），得到的新数列再相邻的两个数进行异或操作。 最后得到一个数，即为答案。现在给出m个操作，每个操作两个数p,b，表示令a[p]=b,每次变化后输出最终的结果。 思路：线段树。这道题让我学到了，线段树的数组tree[i]存储的信息可能不唯一，可以不同层存储的是不同的信息。 比如这道题中，距离叶子节点距离为奇数的点存储的是或操作的结果，距离叶子节点距离为偶数的点存储的是异或操作的结果。 还需要注意的是，build和update操作都是从顶向下，最后一个操作是异或还是或取决于n的奇偶性，记得判断。 /* …

题目链接 题意： 在二维坐标平面内进行_n_ (1 ≤ _n_ ≤ 2·105) 次操作。一共有三种类型操作。 1.add x,y 将点(x,y)加进坐标系。 2.remove x,y 将点(x,y)移除. 3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有多个输出x最小的。还是有多个输出y最小的。 x,y均为非负数。以上操作均合法。 思路：没有思路。。。不会啊。。。以为要二维线段树什么的。。。。总之是不会做。。。 大概从中午开始看题解。。。8个小时。。。。终于完全搞懂了orz 很巧妙得把二维问题转化成了一维问题。。。 我来说一下大概做法，具体的细节见代码注释： 在x轴方向维护一课线段树，线段 …

poj 2828 题目链接 题意：n个人，每个人有一个rp值（用来区分不同的人），还有一个pos[i]，表示当第i个人来排队的时候插入到第pos[i]个人的后面（也就是排在位置pos[i]+1) 现在问最后的序列，从1到n输出n个人的rp值 思路：第二道线段树，并不会做，看了题解。 比较关键的一点是：按照顺序的话，当后来的一个人插入到前面，那么之前很多人排好的位置将发生改变，这个代价是巨大的。 由于越后来的人越容易确定位置，因此正确的做法是倒序处理。 对于第i个人，我们把他放在从前往后数的第i个空的位置即可。 接下来需要做的就是线段树处理，线段树存储的信息是某一个区间中空位置的个数。 感觉是一道很好的题目，对于新手来说并不是很容易， …

题目链接 题意：找两个不相交点集使得对于每一条边至少有一个顶点在点集中 思路：判断能否构成二分图。染色即可。 需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333. /* *********************************************** Author :111qqz Created Time :2016年09月03日 星期六 01时04分40秒 File Name :code/hdu/687A.cpp ************************************************ */ #include <cstdio> #include …