题目链接 题意：给出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，分别表示一个区间中包含左端点在的最大字段和（也就是最大前缀和），和一个区间中包含右端点在的最大子段和（也就是最大后缀和），然后对于最大子段既在左区间又在右区间的情况，只需要合并【左区间的最大后缀和 】和【右区间的最大前缀和】就好。 关于一个区间最大前缀和的维护，取该区间的左区间的最大前缀和和【该区间的左区间和】+【该区间的右区间的最大前缀和】的最大值。 最大后缀和同 …

题目链接 题意： 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函数。。。？ 维基百科 讲解

被ex吐槽说。。。常年穿运动服。。。没有想看的欲望。。。。 已经是第二次被吐槽不会穿衣了Orz.... 不禁陷入沉思。。。。？ 所以大概要花些时间学习一下基本的穿衣技巧......？ 而且。。。。之前觉得。。。。没有遇到合适的妹子。。。。。 现在觉得。。。。。如果不自己创造一些机会的话。。。。就永远不会有合适的。。。。？ 不过。。。。。。我在这方面毫无信心和经验orz.... 哎。。。怎么突然想起这些事。。。明天hk网赛，rp++