线段树--题解 P5688 【[CSP-SJX2019]散步】

· · 题解

看起来这题还是不太多人知道。。。那不妨在A掉一个月之后来写一篇题解。

这题写出来可以显著提升代码能力。

博客阅读效果更好。

1.基本思路

首先这题所有人是匀速的，并且一直一起运动。

所以可以想到，像小学奥数中多人行进多次折转的问题一样，我们只需要每次找到一个最先抵达终点的人就行了。

这道题当然没有这么简单；因为每个出口只能容纳一定量的人出去。

于是就在查询的时候带上了修改。

我们发现，如果一个出口满员了，只对其它的（两个方向）原本需要从这个出口出去的人造成影响，且两个方向上的人新的目的地是分别相同的。

2.实现的方法与数据结构

于是我们想到线段树上全局查询带上区间修改。

这里有必要先提出：如何保证所修改的一个或若干个区间呢？

可以首先把人以方向不同分离开来。

然后对于两边的人，按照绝对位置 b 排序即可。

然后我们考虑一下整个算法流程。

  1. 初始化每个人的目的地与距离。
  2. 根据距离最小建出线段树。
  3. 执行 n 步：
  4. 取出线段树顶部结点，将其贡献加入答案。
  5. 如果其目的地满员：
  6. 二分找出原本打算从这个出口出去的人的区间。（这里区间最多有 4 个，因为有两个方向，并且如果跨过 0 原点，又可能出现 2 个区间）
  7. 线段树上区间修改离目的地的距离和目的地。
  8. 如果出口已经被用尽，后面的人的贡献都为 0，直接退出循环。

这个表完整吗？明显是不够完整的。

比如说：如何找出一个出口用尽之后下一个能用的出口是哪一个？如何 O(n\log n) 初始化？线段树上是怎么工作的？

关于出口的关系，容易想到用一个双向链表维护还存在的出口之间的相邻关系。

可以上一段代码：

struct Chain
{
    int l[MAXN],r[MAXN];
    void init() {
        for(int i = 1;i <= m;i++) {
            l[i] = i - 1;
            r[i] = i + 1;
        }
        l[1] = m, r[m] = 1;
    }
    int pre(int x) {
        return l[x];
    }
    int nxt(int x) {
        return r[x];
    }
    void del(int x) {
        r[l[x]] = r[x];
        l[r[x]] = l[x];// 满员时删除
    }
};

关于初始化，可以直接对于每个人二分。

给出人的结构体：

struct Person
{
    int s,b,id,tar,dis;
    // 分别是方向，绝对位置，排序前的编号，目标和距离（当然是初始状态下的）
    Person() {}
    Person(int _s,int _b,int _id,int _tar,int _dis) :
        s(_s), b(_b), id(_id), tar(_tar), dis(_dis) {} 
    friend bool operator < (const Person &x,const Person &y) {
        if(x.s != y.s) return x.s < y.s;
        return x.b < y.b;
    }
    //第一次排序的方式：先按方向，再按绝对位置
};

注意：这不是线段树上结点的结构体。

并初始化的代码：

void init() {
    for(int i = 1;i <= n;i++) {
        if(!p[i].s) {// 顺时针
            int k = std::lower_bound(a + 1,a + 1 + m,p[i].b) - a - 1;
            if(k == m) p[i].tar = 1, p[i].dis = l - p[i].b;
            else p[i].tar = k + 1, p[i].dis = a[k + 1] - p[i].b; 
        } else {// 逆时针
            int k = std::upper_bound(a + 1,a + 1 + m,p[i].b) - a - 1;
            p[i].tar = k, p[i].dis = p[i].b - a[k];
        }
    }
    return;
}

注意 lower_bound 和 upper_bound 的运用及跨过 0 原点的特殊情况处理。

再给出主函数开头一段：


Person p[MAXN];
Chain c;
Segment_Tree t;

int main() {
    n = read(), m = read(), l = read();
    for(int i = 2;i <= m;i++) a[i] = read();
    for(int i = 1;i <= m;i++) lim[i] = read();
    for(int i = 1;i <= n;i++) {
        p[i].s = read(), p[i].b = read();
        p[i].id = i;
    }
    std::sort(p + 1, p + 1 + n);
    while(end <= n && !p[end].s) end++;
    init();
    t.build(1,1,n);
    c.init();

注意认清变量名。 end 记录了第一个顺时针的人的编号，是之后二分不可少的工具。

然后到了重点：线段树应该怎么工作呢？

3.线段树上处理

因为我们不仅要询问线段树上最小距离，还要知道最小距离的点的编号。

于是我们把线段树结点封装成结构体：

struct Segment_Tree
{
#define lc(k) k << 1
#define rc(k) k << 1 | 1
    struct node
    {
        int id,dis,tar;
        // 编号，距离，目标
        // 注意编号是排完序的编号，而不是一开始输入的编号。
        node() {}
        node(int _id,int _dis,int _tar) :
            id(_id), dis(_dis), tar(_tar) {}
        friend bool operator < (const node &x,const node &y) {
            if(x.dis != y.dis) return x.dis < y.dis;
            return ::p[x.id].id < ::p[y.id].id;
        }
        // 注意：不仅要按照距离排序，距离相等时还要考虑最原始的编号大小
    };

    node p[MAXN << 2];

线段树也封装结构体。

于是我们的 pushup 函数就可以直接取 \min 拷贝了。

    void pushup(int k) {
        p[k] = std::min(p[lc(k)],p[rc(k)]);
    }

关于建树，打标记，下传之类，都是在 tag 结构体的基础上运行的：

    struct tag
    {
        int dis, tar;
        tag() {}
        tag(int _dis,int _tar) :
            dis(_dis), tar(_tar) {}
    };

    tag t[MAXN << 2];

相信大家都会，不再赘述。

值得一提的是 upset,因为每个结点都只能取出一次，所以我们把取出的结点 dis 设为 INF,然后 pushup，想当于作了一次单点修改。

    void upset(int k,int l,int r,int x) {
        if(l == r) {
            p[k].dis = INF;
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(k);
        if(x <= mid) upset(lc(k),l,mid,x);
        else upset(rc(k),mid + 1,r,x);
        pushup(k);
    }

然后就差不多这样了。

4.修改

这里主要指查询之后的找出影响区间。

是本题中代码实现最为复杂，最容易出错的地方。

先上代码:

void Modify1(int l,int r,Segment_Tree::tag tag) {
    int k1 = std::upper_bound(p + 1,p + end,Person(0,l,0,0,0)) - p;
    int k2 = std::upper_bound(p + 1,p + end,Person(0,r,0,0,0)) - p - 1;
    if(l > r) {
        if(k1 < end) t.update(1,1,n,k1,end - 1,tag);
        if(k2 >= 1) t.update(1,1,n,1,k2,tag);
    } else if(k1 <= k2) t.update(1,1,n,k1,k2,tag);
}

void Modify2(int l,int r,Segment_Tree::tag tag) {
    int k1 = std::lower_bound(p + end,p + 1 + n,Person(1,l,0,0,0)) - p;
    int k2 = std::lower_bound(p + end,p + 1 + n,Person(1,r,0,0,0)) - p - 1;
    if(l > r) {
        if(k1 <= n) t.update(1,1,n,k1,n,tag);
        if(k2 >= end) t.update(1,1,n,end,k2,tag);
    } else if(k1 <= k2) t.update(1,1,n,k1,k2,tag);
}
// int main() {
// for(int i = 1;i <= n;i++) {
        if(!--lim[tar]) {
            Modify1(a[c.pre(tar)],a[tar],Segment_Tree::tag((a[c.nxt(tar)] - a[tar] + l) % l,c.nxt(tar)));
            Modify2(a[tar],a[c.nxt(tar)],Segment_Tree::tag((a[tar] - a[c.pre(tar)] + l) % l,c.pre(tar)));
            c.del(tar); // 切记在链表中删除该出口
            if(++usdup == m) break;// 如果出口用尽，直接退出。
        }

大略来说，顺时针的 Modify1 处理，逆时针的 Modify2 处理。

k1,k2 在 Person 数组的 [1,end) 或 [end,n] 上进行 lower_bound 或 upper_bound，表示将要修改 [k1,k2] 的区间。

如果区间左端点大于右端点，则说明跨越了原点 0，需要拆开两段处理。

判断区间是否存在后（因为如果修改区间 k1 > k2，会出现无法预料的错误，这是使用 lower_bound 和 upper_bound 的重点），在线段树上进行修改。

这边大概也无法更加细致地讲了。整理出坑点如下：

  1. lower_bound 与 upper_bound 的使用与是否 -1；
  2. 右端点是 n 还是 end - 1:
  3. 一个人正好在出口的位置，就得从那个出口出去，需要注意它是否在修改范围内。

于是就是这么麻烦的了。

5.总结:

这题如果写出来，可能需要耗费一些精力；但是希望大家一定不能中途放弃（像我做题一样），多对拍，多上 gdb 调试。本人就做了 3-4 天。当然大神半天都不消罢。

常见坑点如开 long long 也赘述了。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long ll;
const int MAXN = 200011;
const int INF = 0x3f3f3f3f;

inline int read() {
    int x = 0; char ch = getchar();
    while(ch > '9' || ch < '0') ch = getchar();
    do x = x * 10 + ch - 48, ch = getchar(); while(ch >= '0' && ch <= '9');
    return x;
}

int n, m, l, end;
int a[MAXN], lim[MAXN];

struct Person
{
    int s,b,id,tar,dis;
    Person() {}
    Person(int _s,int _b,int _id,int _tar,int _dis) :
        s(_s), b(_b), id(_id), tar(_tar), dis(_dis) {} 
    friend bool operator < (const Person &x,const Person &y) {
        if(x.s != y.s) return x.s < y.s;
        return x.b < y.b;
    }
};

struct Chain
{
    int l[MAXN],r[MAXN];
    void init() {
        for(int i = 1;i <= m;i++) {
            l[i] = i - 1;
            r[i] = i + 1;
        }
        l[1] = m, r[m] = 1;
    }
    int pre(int x) {
        return l[x];
    }
    int nxt(int x) {
        return r[x];
    }
    void del(int x) {
        r[l[x]] = r[x];
        l[r[x]] = l[x];
    }
};

Person p[MAXN];
Chain c;

struct Segment_Tree
{
#define lc(k) k << 1
#define rc(k) k << 1 | 1
    struct node
    {
        int id,dis,tar;
        node() {}
        node(int _id,int _dis,int _tar) :
            id(_id), dis(_dis), tar(_tar) {}
        friend bool operator < (const node &x,const node &y) {
            if(x.dis != y.dis) return x.dis < y.dis;
            return ::p[x.id].id < ::p[y.id].id;
        }
    };

    struct tag
    {
        int dis, tar;
        tag() {}
        tag(int _dis,int _tar) :
            dis(_dis), tar(_tar) {}
    };

    node p[MAXN << 2];
    tag t[MAXN << 2];

    void pushdown(int k) {
        if(!t[k].dis && !t[k].tar) return;
        perform(lc(k),t[k]);
        perform(rc(k),t[k]);
        t[k].dis = t[k].tar = 0;
        return;
    }

    void pushup(int k) {
        p[k] = std::min(p[lc(k)],p[rc(k)]);
    }

    void perform(int k,tag x) {
        p[k].dis += x.dis;
        if(x.tar) p[k].tar = x.tar;
        t[k].dis += x.dis;
        if(x.tar) t[k].tar = x.tar;
        return;
    }

    void build(int k,int l,int r) {
        if(l == r) {
            p[k] = node(l,::p[l].dis,::p[l].tar);
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(k),l,mid);
        build(rc(k),mid + 1,r);
        pushup(k);
    }

    void update(int k,int l,int r,int x,int y,tag v) {
        if(l > y || r < x) return;
        if(l >= x && r <= y) {
            perform(k,v);
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(k);
        update(lc(k),l,mid,x,y,v);
        update(rc(k),mid + 1,r,x,y,v);
        pushup(k);
        return;
    }

    void upset(int k,int l,int r,int x) {
        if(l == r) {
            p[k].dis = INF;
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(k);
        if(x <= mid) upset(lc(k),l,mid,x);
        else upset(rc(k),mid + 1,r,x);
        pushup(k);
    }

    node query() {
        return p[1];
    }
};

Segment_Tree t;

void init() {
    for(int i = 1;i <= n;i++) {
        if(!p[i].s) {
            int k = std::lower_bound(a + 1,a + 1 + m,p[i].b) - a - 1;
            if(k == m) p[i].tar = 1, p[i].dis = l - p[i].b;
            else p[i].tar = k + 1, p[i].dis = a[k + 1] - p[i].b; 
        } else {
            int k = std::upper_bound(a + 1,a + 1 + m,p[i].b) - a - 1;
            p[i].tar = k, p[i].dis = p[i].b - a[k];
        }
    }
    return;
}

void Modify1(int l,int r,Segment_Tree::tag tag) {
    int k1 = std::upper_bound(p + 1,p + end,Person(0,l,0,0,0)) - p;
    int k2 = std::upper_bound(p + 1,p + end,Person(0,r,0,0,0)) - p - 1;
    if(l > r) {
        if(k1 < end) t.update(1,1,n,k1,end - 1,tag);
        if(k2 >= 1) t.update(1,1,n,1,k2,tag);
    } else if(k1 <= k2) t.update(1,1,n,k1,k2,tag);
}

void Modify2(int l,int r,Segment_Tree::tag tag) {
    int k1 = std::lower_bound(p + end,p + 1 + n,Person(1,l,0,0,0)) - p;
    int k2 = std::lower_bound(p + end,p + 1 + n,Person(1,r,0,0,0)) - p - 1;
    if(l > r) {
        if(k1 <= n) t.update(1,1,n,k1,n,tag);
        if(k2 >= end) t.update(1,1,n,end,k2,tag);
    } else if(k1 <= k2) t.update(1,1,n,k1,k2,tag);
}

int main() {
    n = read(), m = read(), l = read();
    for(int i = 2;i <= m;i++) a[i] = read();
    for(int i = 1;i <= m;i++) lim[i] = read();
    for(int i = 1;i <= n;i++) {
        p[i].s = read(), p[i].b = read();
        p[i].id = i;
    }
    std::sort(p + 1, p + 1 + n);
    while(end <= n && !p[end].s) end++;
    init();
    t.build(1,1,n);
    c.init();
    ll ans = 0; int usdup = 0;
    for(int i = 1;i <= n;i++) {
        Segment_Tree::node k = t.query();
        int id = k.id,tar = k.tar;
        ans ^= 1ll * p[id].id * tar;
        //std::printf("node = %d target = %d\n",p[id].id,tar);
        t.upset(1,1,n,id);
        if(!--lim[tar]) {
            Modify1(a[c.pre(tar)],a[tar],Segment_Tree::tag((a[c.nxt(tar)] - a[tar] + l) % l,c.nxt(tar)));
            Modify2(a[tar],a[c.nxt(tar)],Segment_Tree::tag((a[tar] - a[c.pre(tar)] + l) % l,c.pre(tar)));
            c.del(tar);
            if(++usdup == m) break;
        }
    }
    std::printf("%lld\n",ans);
    return 0;
}