题目链接

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

思路：

官方题解：

题目链接

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

思路：

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]).

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

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

思路：离线处理+线段树的做法不多说了：

 1/* ***********************************************
 2Author :111qqz
 3Created Time :Fri 16 Sep 2016 11:34:32 PM CST
 4File Name :code/spoj/dquery.cpp
 5************************************************ */
 6#include <cstdio>
 7#include …

题目链接

题意：题意是由伪代码给出的。。手算模拟了一下(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]

Description

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

题目链接

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

思路：考虑一段区间，分成左右两个子区间，这段区间的最大子段有三种情况：只在左区间中，只在右区间中，既在左区间中又在右区间中。前两种很好维护，对于后一种，我们新增加线段树的两个域，mxl,mxr，分别表示一个区间中包含左端点在的最大字段和（也就是最大前缀和），和一个区间中包含右端点在的最大子段和（也就是最大后缀和），然后对于最大子段既在左区间又在右区间的情况，只需要合并【左区间的最大后缀和 】和【右区间的最大前缀和】就好。

题目链接

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

思路：首先去学了一下康托展开和逆展开。。。其实就是对于这种排列之类的问题。。。的一个比较省空间的hash函数。。。？

题目链接

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

思路：lazy标记。lazy[i]记录以i节点为根节点的子树对应的区间中被翻转的次数，初始为0.然后查询的时候，根据被翻转次数的奇偶性确定答案。

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

思路：由于先前被打败的骑士直接就退场了。。。所以如果不做判断。。那么之后胜利的骑士会干扰之前的结果。。。