（由于被 fgd BS 了英文。。我把题目背景都删了。。）
Brief description :
You are given a sequence A[1], A[2],…, A[N]. On this sequence you have to apply M operations: Add all the elements whose value are in range [l, r] by d or, ask for a query how many element are in range [l, r].
( 1≤ N ≤ 250,000, M ≤ 50,000), |A[i]| ≤ 1,000,000,000 .)
Analysis :
哎。。我现在已经觉得这个题出的真是失败啊。。
（嘛。。题目出成这样我也没有什么可辩解的了。。
。。开始觉得这是数据结构 S 级神题的。。）
原题是在 那个操作 的基础上维护第 K 大的数。。。内测得时候几乎无人做。。因此简化成了统计某个区间内数的多少。。。求第 K 大的话在这个基础上进行二分即可，因为没有直接的办法。。
那么，对于值域在某个区间内的数进行操作，首先想到的是 伸展树，她的一个神技是两次 Splay 操作将某个区间的所有树伸展到某个容易访问的子树位置。
那么，接下来？。。。、打标记？
如图所示。。（。。。）
这个操作会破坏键值。。。也是因为同样的原因，线段树 块状链表 都不奏效。。
。。。这是这个问题的难点所在。。。下面对 键值处在某个范围的数整题加上某个数 这个操作进行进一步的观察。。
可以得到下面两个性质。
- 选出的序列，在操作的前后相对顺序不发生改变。
- 在任意时刻，如果两个数额键值相同，那么今后，它们会一直作为一个整体存在。
….
为了防止有人用第二个性质乱搞。。题目 Ai 值的范围要尽可能的大。。
第一个性质。。提示我们用 块状结构 来解决掉这个问题。。。
标程使用的是 伸展森林 … 字面上的意思，也就是维护一组伸展树，每次对每棵伸展树伸展出选定的区间，然后打上标记分离出来（喀嚓！）。。
等到伸展树的棵树达到 某个值 （一般设定为 sqrt(n) 然后考虑到 常数，再减小一点。。不判断块树而是每隔一段时间重构一次。。大概用一个对数函数。。。）
的时候。。推掉重练。。（这里注意一个地方。实际中重构的话用 std::sort 比用堆然后分块合并要快。。）
这里的标记只要记录在根节点即可，不需要下放。。
（一个容易出错的地方是，虽然我保证中间的数据也不会爆 int32，但是在处理 delta 的时候可能会爆。。所以如果想保持主要的结构都使用 int32 的话这里要特判一下。。）
一个严重的问题就此产生了：
似乎一眼看上去，splay 的颗树会呈指数爆炸？！。。。
嗯嗯。。这个问题。。我还。。不知道怎么证明。（什么！）
。。但是看上去似乎（对于随机生成的数据）这种情况不会出现 。。
下面我试图说一点我的想法。。
定义
/theta = sqrt Sigma i, j sqr(Ai – Aj)
为一个数集的 离散程度。（注意不能直接使用方差。。吧。。）
（于是，重新考察前面的性质2，虽然说要中间恰好相等可能不太会出现。
但是有迹象表明，操作过后数列可能在某几个位置集中。。而这就相当于降低了 N 的规模）。。
对于某一次操作，会发生下面两种事情之一
- 数列的离散程度下降，同时，块数增多。
- Nothing happend (什么都没有发生)。。
…
好吧。。大概就是这样了。。。
（我以后会继续考虑这个问题的。。如果有么进展的话会及时更新。。）
我看到赛后很多同学提交了 线段树 的方法。。。本质上都差不多吧。。
复杂度的话。。是
P = sqrt(n)
O( (M / log P) N log P) = O(NM)..
P 是块数上限。。 M / log P 是重构频率。。（= =。。。。）
随着 M 的增大逐渐向 O(nlogn) 收敛（因为根据 观察 后期块数很少再增加。。）
（然后还会 很慢很慢 的 向 O(1) 收敛 。。考虑所有数的值都一样的时候。。大概随机情况下要进行一个天文数字次才可能发生吧。哎。。要会一点概率论就好了啊。。。。。）
我把 SPOJ 的时限设定的很。。。喜欢测时间的同学请移步。。
下面给出标程② 。。。
方法是。。。先对整个数列排一次序。。然后使用下面这个东西保存分块。。。
可以支持原地的二分查找。。
struct Link{
int a, b, d;
Link(){}
Link(int _a, int _b, int _d):a(_a), b(_b), d(_d){};
void Split();
int Stat();
} L[N]; int sz;
其中 a, b 表示这个分块的区间，左闭右开 [ )。。
。。。
然后就可以维护了。。
这个方法常数很小。。。（不过分裂的时候似乎会 3 分。！！。）
。这个 方法在 SPOJ 可以跑 14.54 s。。。
/* .................................................................................................................................. */
const int N = 250010, M = 1010, C = 1000000000;
int A[N]; char cmd; int cnt;
int n, m, a, b, l, r, d; int *_a, *_b;
struct Link{
int a, b, d;
Link(){}
Link(int _a, int _b, int _d):a(_a), b(_b), d(_d){};
void Split();
int Stat();
} L[N]; int sz;
#define FIX(x) int(x < -C ? -C : x > C ? C : x)
#define GPS _a = lower_bound(A + a, A + b, FIX((LL)::l - d)), _b = upper_bound(A + a, A + b, FIX((LL)::r - d))
void Link::Split(){
GPS, ::a = _a - A, ::b = _b - A;
if (::a == ::b || b < ::a || ::b < a) return;
int aa = max(::a, a), bb = min(::b, b);
if (a < aa) L[sz++] = Link(a, aa, d);
if (bb < b) L[sz++] = Link(bb, b, d);
a = aa, b = bb, d += ::d;
}
int Link::Stat(){
GPS; return _b - _a;
}
void Rebuild(){
REP(i, sz) FOR(j, L[i].a, L[i].b) A[j] += L[i].d;
sort(A, A+n), L[0] = Link(0, n, 0), sz = 1;
}
/*
void Patch(){
REP(i, sz){
FOR(j, L[i].a, L[i].b)
cout << A[j] + L[i].d << " ";
}
cout << endl;
}*/
int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
RD(n, m); REP(i, n) RD(A[i]); sort(A, A+n);
L[0] = Link(0, n, 0), sz = 1;
int P = sqrt(n) / 11;
char cmd; REP(j, m){
scanf(" %c", &cmd);
if (cmd == 'C'){
RD(l, r, d); REP_C(i, sz) L[i].Split();
if (sz > P) Rebuild();
//Patch();
}
else {
RD(l, r); cnt = 0; REP(i, sz) cnt += L[i].Stat();
OT(cnt);
}
}
}
。如何构造一个数据可以杀掉所有 std 呢。。
（、这个问题留给读者思考。。）
External link :
https://www.spoj.pl/problems/PS11A/
https://vjudge.net/problem/HDU-3971
http://acm.hit.edu.cn/judge/show.php?Proid=3054
块状结构秒杀一切！ by WJMZBMR
