https://vjudge.net/problem/47450/origin 题意： 有一个含有n个数的序列，m个询问。问 [l, r] 区间内与所有数都互质的数有几个？ 思路： 想到了预处理每个数最左最右的，最远的互质的数的范围。。 之后对于询问区间[l,r]，我们要知道 对于 i>=L && i <= R 并且 a[i].l<=L，a[i].r>=R的i的个数... 没有想到怎么维护,gg 转载一段题解： 先算出每个数的有效范围，l[i]，r[i]代表与第i个数一直互质到的最左端和最右端。这个处理方法是，预处理出一张因子表。然后对每个输入的数，判断其因子出现的最接近它的位置。从左到右扫一 …

题目链接 题意: If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add 1 问每个point的level是多少。 思路： cdq分治，先去重并统计相同的点的数量，需要注意要记录原id对应到了哪个新id /* *********************************************** Author :111qqz Created Time :2017年10月10日 星期二 19时53分38秒 File Name :5618.cpp …

Description 有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。 Input 第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。 以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性 Output 包含N …

题目链接 题意：有２种货币，分别为C和D.给出n种资源的代价和美丽度，每种资源只能用其中一种资源购买。现在拥有货币C的数量是c,拥有货币D的数量是d.然后恰好买２个资源，问最大美丽度，不能的话输出０． 思路：首先显然三种情况。。。CC，CD,DD. CD直接扫一遍。。重点是CC和DD 一开始思路错掉了。。全程写two pointer wa4...一直调。。 最后恍然大悟。。发现two pointer非常错啊。。。 其实正解也很简单？ 先去跑步了orz 只要想办法维护每个代价的最大美丽度就好了(更准确得说，是维护小于等于某代价的最大美丽度) 直接BIT搞。维护一个前缀max...好像很稳啊？ 不过我竟然对于BIT能维护前缀max吃了一 …

题目链接 题意：给出n个数,q个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+7的答案是多少。 思路：这道题需要一点欧拉函数的知识。 phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。 To calculate the answer on every query let's use the formula , where _p_1, p_2, ..., p__k — all prime numbers which divided_n. 如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。 考虑两个数a,b的欧拉函数。 一开始考虑也许有什么性质。。。查了下欧拉函数的wiki 欧拉函数_维基百科 欧拉函数 …

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

题目链接 题意： 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, …

http://www.lydsy.com/JudgeOnline/problem.php?id=3289 题意：中文题目，简单来说就是求某一区间内的逆序对数。 思路：逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。 还有这题没给数据范围但是需要离散化。。。不然会re... /* *********************************************** Author :111qqz Created Time :2016年02月17日 星期三 20时18分51秒 File Name :code/bzoj/3289.cpp …

http://codeforces.com/problemset/problem/552/A 题意：一个100*100的网格。然后给n个矩形。每个格子中填上包含这个格子的矩形的个数。最后问所有格子的和。 思路：树状数组搞得...然而..直接求所有矩形面积的和就可以啊喂。。o(n)。。。111qqz你个炒鸡大菜鸡。 /* *********************************************** Author :111qqz Created Time :2015年12月14日 星期一 14时01分14秒 File Name :code/cf/problem/552A.cpp …

题目链接 题意： 这题是问一个长度为n的循环数组中，逆序对最少的个数。。。 我们可以先用树状数组求出初始的数列的逆序对。。。 然后其他的可以通过递推得到。。。。 当a[i]从处于位置1而被放到最后的时候。。。 cnt = cnt -a[i]+n-a[i]+1; 然后取所有cnt的最大值就行。 /************************************************************************* > File Name: code/hud/1394.cpp > Author: 111qqz > Email: rkz2013@126.com > Created …