题目链接

喵呜，离散树状数组。

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

怎么办呢？

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

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

三维树状数组

容斥那里注意一下。

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

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

1

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

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

 1 …

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

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

做法差不多。

如果更新区间【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 …