题目链接 题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换n次以后得到的数列中，逆序对的数。 思路： 官方题解： At first find the position of each element which is used in swap (using map). Now let's find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They …

题目链接 题意：圆上，询问任意一段弧中，任意两点的距离+两点的权值和的最大值。 思路： 1.环先拆成串，复制1..n到后面，变成1..2n。 化简公式： 2 * h[u] + 2 * h[v] + dist(u, v) = 2 * h[v] + d[1] + d[2] + ... + d[v-1] + 2 * h[u] - (d[1] + d[2] + ... + d[u-1]). 设A[v] = 2 * h[v] + d[1] + d[2] + ... + d[v-1], B[u] = 2 * h[u] - (d[1] + d[2] + ... + d[u-1]). Another important thing is that …

题目链接 题意：有n个数，每次可以删除掉数值相同并且所在位置成等差数列（只删2个数或者只删1个数应该也是可以的），删掉这些数以后可以将剩下的数重新以任意顺序排列，称为一次操作。现在给出m个询问，每个询问一个区间[l,r]，问删光区间[l,r]中的数最少需要的操作次数。 思路/题解：由于第一次操作之后可以重排，那么把相同的数放在一起得到一个位置的公差为1的等差数列，之后的答案显然是元素个数。所以需要判断初始的时候，是否能一次删光某个数值的数，也就是需要判断初始时刻是否有某个数出现的所有位置组成一个等差数列。 (去icpc-camp的论坛问了一波。。。链接在这里) 之前刚刚学了判断一个区间中不同的数有多少个的姿势。。。 所以问题就在于如 …

题目链接 题意：给出n个数，然后m个询问，每个询问一个区间[l,r],问该区间中不同的数有多少个。 思路：离线处理+线段树的做法不多说了： /* *********************************************** Author :111qqz Created Time :Fri 16 Sep 2016 11:34:32 PM CST File Name :code/spoj/dquery.cpp ************************************************ */ #include <cstdio> #include <cstring> …

题目链接 题意：题意是由伪代码给出的。。手算模拟了一下(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 s={8,5}和s={5,7}是有解的。 因为对于前者8+3>=10并且5+5>=10,对于后者5+5>=10,7+3>=10,因此答案为2 思路： 最重要的一部是，我们先将b排序，然后维护一个函数f[i],在排序后的b中找到一个最小的j， …

1756: Vijos1083 小白逛公园 Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1078 Solved: 353 [Submit][Status][Discuss] Description 小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。 一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于 …

题目链接 题意：给出n个数,m个修改，每次修改后询问整个区间的最大连续子段。 思路：考虑一段区间，分成左右两个子区间，这段区间的最大子段有三种情况：只在左区间中，只在右区间中，既在左区间中又在右区间中。前两种很好维护，对于后一种，我们新增加线段树的两个域，mxl,mxr，分别表示一个区间中包含左端点在的最大字段和（也就是最大前缀和），和一个区间中包含右端点在的最大子段和（也就是最大后缀和），然后对于最大子段既在左区间又在右区间的情况，只需要合并【左区间的最大后缀和 】和【右区间的最大前缀和】就好。 关于一个区间最大前缀和的维护，取该区间的左区间的最大前缀和和【该区间的左区间和】+【该区间的右区间的最大前缀和】的最大值。 最大后缀和同 …

题目链接 题意：给出两个排列，定义ord(p)为排列p的顺序（字典顺从小到大），定义perm(x)为顺序为x的排列，现在要求 1 ≤ n ≤ 200 000 思路：首先去学了一下康托展开和逆展开。。。其实就是对于这种排列之类的问题。。。的一个比较省空间的hash函数。。。？ 康托展开资料 然后由于n非常大。。康托展开中要查找当前位置后面有多少个比当前位置小的。。。 然而这复杂是n2。。。肯定gg。。。 因此里面那层我们用一课线段树维护。。。复杂度nlgn 在康托逆展开的过程中。。。我们要查询之前没有出现过的第k个元素。。。。 因为n很大这里也需要线段树来维护。。。 所以再建一棵线段树。。。某位置表示初始时刻是否为空，初始都为1，表 …

题目链接 题意：给出一个长度为n的数列，每个位置是0或者1，给出q个操作，操作有两种类型，分别是将一段区间中反转，和询问当前某位置是0还是1 思路：lazy标记。lazy[i]记录以i节点为根节点的子树对应的区间中被翻转的次数，初始为0.然后查询的时候，根据被翻转次数的奇偶性确定答案。 wa了好多发。。。比较致命的是。。PushDown函数忘记改了。。。还按照染色的方法直接赋值的。。。然而这里是统计次数。。。所以是累加。。。。 /* *********************************************** Author :111qqz Created Time :Wed 14 Sep 2016 12:59:07 …

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