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的个数…

题目链接

题意:

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

Description

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

题目链接

题意：有２种货币，分别为C和D.给出n种资源的代价和美丽度，每种资源只能用其中一种资源购买。现在拥有货币C的数量是c,拥有货币D的数量是d.然后恰好买２个资源，问最大美丽度，不能的话输出０．

题目链接

题意：给出n个数,q个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+7的答案是多少。

思路：这道题需要一点欧拉函数的知识。

phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。

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

题目链接

题意：

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]怎么就挨着了。。。

http://www.lydsy.com/JudgeOnline/problem.php?id=3289

题意：中文题目，简单来说就是求某一区间内的逆序对数。

思路：逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。

http://codeforces.com/problemset/problem/552/A 题意：一个100*100的网格。然后给n个矩形。每个格子中填上包含这个格子的矩形的个数。最后问所有格子的和。 思路：树状数组搞得…然而..直接求所有矩形面积的和就可以啊喂。。o(n)。。。111qqz你个炒鸡大菜鸡。

题目链接

题意：

这题是问一个长度为n的循环数组中，逆序对最少的个数。。。

我们可以先用树状数组求出初始的数列的逆序对。。。

然后其他的可以通过递推得到。。。。

比较水．

唯一一点需要注意的是…

可能有重复元素…

因为我的思路是用两棵一维树状数组搞..

每个点标记为1

然后看矩形的两个方向中是否至少有一个方向上和等于长度…

比赛的时候没过．还以为是树状数组写残了． 但实际上是有自己不知道的东西． 这种博弈叫　nim游戏 所以这是一个二维的nim游戏． **nim游戏的性质是xor 和为0必败，否则必胜． xor和也有前缀和性质，所以可以用树状数组维护．

题目链接

喵呜，离散树状数组。

这道题由于相同的值加和的时候只算一次，所以比较伤脑筋==

怎么办呢？

我们发现对于一个值，由于相同的只算一次，所以在任意时间内，这个值只需要出现一次。

三维树状数组

容斥那里注意一下。

多组数据因为忘记清空c数组而wa了1次，细心！

  1/*************************************************************************
  2	> File Name: code/hdu/3584.cpp
  3	> Author: 111qqz
  4	> Email: rkz2013@126.com 
  5	> Created Time: 2015年08月07日 星期五 14时01分53秒
  6 …

1

和上一道类似，也是更新区间，查询单点。
用到了容斥原理。

  1/*************************************************************************
  2	> File Name: code/poj/2155.cpp
  3	> Author: 111qqz
  4	> Email: rkz2013@126.com 
  5	> Created Time: 2015年08月07日 星期五 00时42分38秒
  6 …

这道题和之前做的树状数组略有不同。

以前的都是更新单点，查询区间，这次反了过来。

做法差不多。

如果更新区间【x,y】增加１

那么只要 update (x,1),update (y+1,-1)

问单点的时候，sum(i)就是i点的值，而不是1..i的和。

• Inversions

**Time Limit:**250MS **Memory Limit:**4096KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

180. Inversions

time limit per test: 0.25 sec.
memory limit per test: 4096 KB

input: standard
output: standard

There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find …

这道题可以总结的地方不少。

１：对于一组乱序数列，每次只能交换相邻元素，达到有序交换的次数就是原数列中你逆序对的个数。

　　cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。

poj 2481 题目链接

题意：给定n个区间，问对于每个区间，有多少个区间真包含该区间（真包含的意思是说，两个区间不能完全重合）

思路：

下面是一年前用树状数组过掉的时候写的题解：  和 star那道题差不多。

需要注意的是star那道题读入的时候已经排好了序，而这道题没有排序

阅读更多

poj 2352题目链接

题意：给出n个星星的位置，一个星星的level定义为其左下角（不严格）星星的数量。

要求统计0到n-1 level的星星各有多少个。