题目链接 题意： how many pairs of integers l and r are there, such that 1 ≤ l < r ≤ n and sequence b = _a_1_a_2... a__l__a__r__a__r + 1... a__n has no more than k inversions. 我花了两个小时才看懂题。。。。一直没懂b数列中a[l]和a[r]怎么就挨着了。。。 其实意思是。。。只保留a数列中1..l和r..n的。。。构成b数列。。。然后b数列的逆序对数小于等于k.问这样的l,r的对数。 思路：尺取+树状数组。 枚举l,每次找到最小的满足题意的r，对答案的贡献是n-r+1, …

题目链接 题意：给出两个排列，定义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 …

题目链接 题意：求n！在k进制表示下有多少位。 思路：答案为[ log(1)+log(2)+...+log(N) ]+1 其中log的底数都是K 由于有多组数据，预处理一个log的前缀和。 /* *********************************************** Author :111qqz Created Time :Tue 13 Sep 2016 05:13:15 PM CST File Name :code/loj/1045.cpp ************************************************ */ #include <cstdio> #include …

感觉就是为了记录排列。。。重复之类的。。。用到的一个hash函数。。。？ 维基百科 讲解

[题目链接](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. 线段树求 …