tags:

• 数据结构
• codeforces
• 算法竞赛
• acm
• ACM

题目链接

喵呜，离散树状数组。

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

怎么办呢？

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

tags:

• codeforces
• acm
• ACM

tags:

• codeforces
• acm
• ACM

tags:

• codeforces
• acm
• ACM

tags:

• 数据结构
• acm
• codeforces
• 算法竞赛
• ACM

树状数组，更新区间，查询单点，区别是加了一个a%k==0的条件限制…. 我们观察到k很小，于是按照k分类…. 每一类再按照余数分类，一共55棵树（1+2+3+…+10）

三维树状数组

容斥那里注意一下。

多组数据因为忘记清空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 …

tags:

• 数据结构
• codeforces
• 算法竞赛
• acm
• ACM

tags:

• codeforces
• acm
• ACM

tags:

• codeforces
• acm
• ACM

依然对算法，对acm充满热情。

只是比赛，组队赛。

心里满满的都是阴影，再也没有什么热情与感动。

连起队名这种事情我都不愿意想了。

起得再棒有什么用。

给出一个图书馆人员进出情况，问图书馆满足题意的最小容量是多少。

注意在初始之前图书馆里面可能就有人了，也就是说不是所有进入图书馆的人都会被给出。

我的做法是先统计出图书馆里面初始的人数，开一个布尔数组，初始全为false,如果一个人标记为 false  而且从 图书馆里出来了，就说明这个人初始是在图书馆里的。

给一个有序序列，问对于没一个数，和它相差最少和最多的数的位置。

 1/*************************************************************************
 2	> File Name: code/cf/#314/A.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com 
 5	> Created Time: 2015年08月06日 星期四 00时01分51秒
 6 …

dfs 1A

 1/*************************************************************************
 2	> File Name: code/whust/#9/K.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com 
 5	> Created Time: 2015年08月05日 星期三 15时02分30秒
 6 ************************************************************************/
 7
 8 …

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

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

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

tags:

• 数据结构
• codeforces
• 算法竞赛
• acm
• ACM

poj 2481 题目链接

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

思路：

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

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

阅读更多

poj 2352题目链接

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

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