某岛

… : "…アッカリ~ン . .. . " .. .
August 27, 2011

SPOJ 9392. Play With Sequence

(由于被 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 操作将某个区间的所有树伸展到某个容易访问的子树位置。

那么,接下来?。。。、打标记?

如图所示。。(。。。)

这个操作会破坏键值。。。也是因为同样的原因,线段树 块状链表 都不奏效。。

。。。这是这个问题的难点所在。。。下面对 键值处在某个范围的数整题加上某个数 这个操作进行进一步的观察。。

可以得到下面两个性质。

  1. 选出的序列,在操作的前后相对顺序不发生改变。
  2. 在任意时刻,如果两个数额键值相同,那么今后,它们会一直作为一个整体存在。

….

为了防止有人用第二个性质乱搞。。题目 Ai 值的范围要尽可能的大。。

第一个性质。。提示我们用 块状结构 来解决掉这个问题。。。

标程使用的是 伸展森林 … 字面上的意思,也就是维护一组伸展树,每次对每棵伸展树伸展出选定的区间,然后打上标记分离出来(喀嚓!)。。

等到伸展树的棵树达到 某个值 (一般设定为 sqrt(n) 然后考虑到 常数,再减小一点。。不判断块树而是每隔一段时间重构一次。。大概用一个对数函数。。。)
的时候。。推掉重练。。(这里注意一个地方。实际中重构的话用 std::sort 比用堆然后分块合并要快。。)

这里的标记只要记录在根节点即可,不需要下放。。
(一个容易出错的地方是,虽然我保证中间的数据也不会爆 int32,但是在处理 delta 的时候可能会爆。。所以如果想保持主要的结构都使用 int32 的话这里要特判一下。。)

一个严重的问题就此产生了:

似乎一眼看上去,splay 的颗树会呈指数爆炸?!。。。

嗯嗯。。这个问题。。我还。。不知道怎么证明。(什么!)
。。但是看上去似乎(对于随机生成的数据)这种情况不会出现 。。

下面我试图说一点我的想法。。

定义
/theta = sqrt Sigma i, j sqr(Ai – Aj)
为一个数集的 离散程度。(注意不能直接使用方差。。吧。。)

(于是,重新考察前面的性质2,虽然说要中间恰好相等可能不太会出现。
但是有迹象表明,操作过后数列可能在某几个位置集中。。而这就相当于降低了 N 的规模)。。

对于某一次操作,会发生下面两种事情之一

  1. 数列的离散程度下降,同时,块数增多。
  2. 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/

http://acm.hit.edu.cn/judge/show.php?Proid=3054
块状结构秒杀一切! by WJMZBMR