题目地址：CodeChef：Elephant | CodeChef

题目描述

Pattaya 的大象跳舞表演非常有名。整个表演中，N 只大象站成一排跳舞。
经过多年的训练，大象们能够在表演时做很多迷人的舞蹈动作。表演由一系列的动作组成。在每个动作中，只有一只大象可能会移动到一个新的位置上。
大象表演的组织者想要拍摄一本包括全部动作的相册。在每个动作之后，他们要拍摄到所有的大象。
在表演中的任何时刻，多只大象可能站在同一个位置上。在这种情况下，在同一个位置上的大象会从前到后站成一排。
一架相机的拍摄宽度为 L（包括两个端点），即一架相机可以拍摄到位于连续的 L+1 个位置上的大象（有些位置可能没有大象）。因为舞台比较大，所以需要多架相机才能同时拍摄到所有的大象。
在这个题目中，你需要确定每一个动作之后，至少需要多少架相机才能同时拍摄到全部的大象。注意，所需相机的最小数目会随着动作的进行而增加、减少或者保持不变。

输入输出格式

输入格式：
第一行N、M、L。
下面N行表示大象的初始位置。
下面M行一行两个整数，第i只大象到了Pi位置。

输出格式：
每次动作后输出最少相机数。

输入输出样例

输入样例#1：

4 10 5
10
15
17
20
2 16
1 25
3 35
0 38
2 0

输出样例#1：

1
2
2
2
3

输入样例#2：

2 12321 3
2
123
1 76543
0 66321
0 78754

输出样例#2：

2
1
1

说明

1≤N≤150000

题解

如果不改变大象的位置，我们考虑怎么解决。我们从第一只大象开始，每次设置一只摄像机来覆盖L距离内的大象，然后往后找第一只没有被覆盖的大象，再设置相机。最后统计设置了多少相机即可。
现在我们需要改变大象的位置，又不能每一次全部扫一遍，自然需要一个快速统计答案的方法。首先我们考虑一种建图方法，先将所有可能出现大想的位置离散化出来，对于相邻位置连边。每增加一只大象，切断该点与后面的点的边，并且连边至超过L距离的第一个点。将有大象的点的点权设置为1，没有的为0，统计起点到终点的路径点权和即为答案。我们考虑可以用LCT来维护这个图，因为上面不可能有环，每次实际上维护的是一棵树。LCT的功能能够满足我们的需求。

代码

以下代码参考了这个Solution：Solution: 16828126 | CodeChef，感谢原作者kazuma。

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <vector>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1000005, INF = 1e9;

struct LCTNode {
    int ch[2], fa, val, sum;
    bool rev;
} lct[MAXN];

inline bool isleft(int p) {
    return lct[lct[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    register int fa = lct[p].fa;
    return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
}

inline void update(int p) {
    register int ls = lct[p].ch[0], rs = lct[p].ch[1];
    lct[p].sum = lct[p].val + lct[ls].sum + lct[rs].sum;
}

inline void reverse(int p) {
    std::swap(lct[p].ch[0], lct[p].ch[1]);
    lct[p].rev ^= 1;
}

inline void pushdown(int p) {
    register int ls = lct[p].ch[0], rs = lct[p].ch[1];
    if(lct[p].rev) {
        if(ls) reverse(ls);
        if(rs) reverse(rs);
        lct[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p;
        p = lct[p].fa;
    }
    pushdown(p);
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
    lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
    lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
    lct[p].ch[!t] = fa; lct[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(register int q = 0; p; q = p, p = lct[p].fa) {
        splay(p);
        lct[p].ch[1] = q;
        update(p);
    }
}

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

inline int findrt(int p) {
    access(p);
    splay(p);
    while(lct[p].ch[0]) p = lct[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

inline void link(int u, int v) {
    split(u, v);
    lct[u].fa = v;
}

inline void cut(int u, int v) {
    split(u, v);
    if(lct[v].ch[0] != u || lct[lct[v].ch[0]].ch[1]) return;
    lct[u].fa = lct[v].ch[0] = 0;
}

inline int query(int u, int v) {
    split(u, v);
    return lct[v].sum;
}

inline void modify(int u, int w) {
    access(u);
    splay(u);
    lct[u].val = w;
    update(u);
}

int n, l, m, p[MAXN], x[MAXN], y[MAXN], cnt[MAXN];
std::vector<int> vec;

int main() {
    n = readint(); l = readint(); m = readint();
    vec.push_back(-1);
    vec.push_back(2e9);
    for(int i = 1; i <= n; i++) {
        p[i] = readint();
        vec.push_back(p[i]);
        vec.push_back(p[i] + l + 1);
    }
    for(int i = 1; i <= m; i++) {
        x[i] = readint() + 1; y[i] = readint();
        vec.push_back(y[i]);
        vec.push_back(y[i] + l + 1);
    }
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    int siz = vec.size();
    for(int i = 2; i <= siz; i++) {
        link(i - 1, i);
    }
    for(int i = 1; i <= n; i++) {
        int u = std::lower_bound(vec.begin(), vec.end(), p[i]) - vec.begin(),
            v = std::lower_bound(vec.begin(), vec.end(), p[i] + l + 1) - vec.begin();
        if(!cnt[u]) {
            cut(u, u + 1);
            link(u, v);
            modify(u, 1);
        }
        cnt[u]++;
    }
    for(int i = 1; i <= m; i++) {
        int ou = std::lower_bound(vec.begin(), vec.end(), p[x[i]]) - vec.begin(),
            ov = std::lower_bound(vec.begin(), vec.end(), p[x[i]] + l + 1) - vec.begin(),
            u = std::lower_bound(vec.begin(), vec.end(), y[i]) - vec.begin(),
            v = std::lower_bound(vec.begin(), vec.end(), y[i] + l + 1) - vec.begin();
        cnt[ou]--;
        if(!cnt[ou]) {
            cut(ou, ov);
            link(ou, ou + 1);
            modify(ou, 0);
        }
        if(!cnt[u]) {
            cut(u, u + 1);
            link(u, v);
            modify(u, 1);
        }
        cnt[u]++;
        p[x[i]] = y[i];
        printf("%d\n", query(1, siz));
    }
    return 0;
}