more than OIers and algorithm learners

Recent Posts

[JLOI2015]城池攻占 题解

[JLOI2015]城池攻占 题解

题目地址:洛谷:【P3261】[JLOI2015]城池攻占 – 洛谷、BZOJ:Problem 4003. — [JLOI2015]城池攻占

题目描述

小铭铭最近获得了一副新的桌游,游戏中需要用 m 个骑士攻占 n 个城池。这 n 个城池用 1 到 n 的整数表示。除 1 号城池外,城池 i 会受到另一座城池 fi 的管辖,其中 fi < i。也就是说,所有城池构成了一棵有根树。这 m 个骑士用 1 到 m 的整数表示,其中第 i 个骑士的初始战斗力为 si,第一个攻击的城池为 ci。
每个城池有一个防御值 hi,如果一个骑士的战斗力大于等于城池的生命值,那么骑士就可以占领这座城池;否则占领失败,骑士将在这座城池牺牲。占领一个城池以后,骑士的战斗力将发生变化,然后继续攻击管辖这座城池的城池,直到占领 1 号城池,或牺牲为止。
除 1 号城池外,每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai =0,攻占城池 i 以后骑士战斗力会增加 vi;若 ai =1,攻占城池 i 以后,战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池,不管结果如何,均不会影响其他骑士攻击这座城池的结果。
现在的问题是,对于每个城池,输出有多少个骑士在这里牺牲;对于每个骑士,输出他攻占的城池数量。

输入输出格式

输入格式:
第 1 行包含两个正整数 n;m,表示城池的数量和骑士的数量。
第 2 行包含 n 个整数,其中第 i 个数为 hi,表示城池 i 的防御值。
第 3 到 n +1 行,每行包含三个整数。其中第 i +1 行的三个数为 fi;ai;vi,分别表示管辖这座城池的城池编号和两个战斗力变化参数。
第 n +2 到 n + m +1 行,每行包含两个整数。其中第 n + i 行的两个数为 si;ci,分别表示初始战斗力和第一个攻击的城池。
输出格式:
输出 n + m 行,每行包含一个非负整数。其中前 n 行分别表示在城池 1 到 n 牺牲的骑士数量,后 m 行分别表示骑士 1 到 m 攻占的城池数量。

输入输出样例

输入样例#1:

5 5
50 20 10 10 30
1 1 2
2 0 5
2 0 -10
1 0 10
20 2
10 3
40 4
20 4
35 5

输出样例#1:

2
2
0
0
0
1
1
3
1
1

说明

对于 100% 的数据,1 <= n;m <= 300000; 1 <= fi<i; 1 <= ci <= n; -10^18 <= hi,vi,si <= 10^18;ai等于1或者2;当 ai =1 时,vi > 0;保证任何时候骑士战斗力值的绝对值不超过 10^18。

题解

考虑对城池构成的树进行DFS转移。维护一个可并小根堆,表示能够到达该节点的骑士,开始时将骑士加入开始节点的左偏树,DFS时合并儿子节点的左偏树,并且将那些战斗力达不到的骑士pop出,并计入该城池牺牲骑士数以及骑士牺牲的位置。本题输入比较大,所以临时换了个fread板子。

代码

// Code by KSkun, 2018/2 
#include <cstdio>
#include <algorithm>
typedef long long LL;

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 LL readint() {
    register LL res = 0;
    register int 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 = 300005;

int dis[MAXN], rt[MAXN], ch[MAXN][2];
LL val[MAXN], add[MAXN], mul[MAXN];

inline void pushdown(int x) {
    if(ch[x][0]) {
        val[ch[x][0]] *= mul[x];
        val[ch[x][0]] += add[x];
        mul[ch[x][0]] *= mul[x];
        add[ch[x][0]] *= mul[x];
        add[ch[x][0]] += add[x];
    }
    if(ch[x][1]) {
        val[ch[x][1]] *= mul[x];
        val[ch[x][1]] += add[x];
        mul[ch[x][1]] *= mul[x];
        add[ch[x][1]] *= mul[x];
        add[ch[x][1]] += add[x];
    }
    mul[x] = 1;
    add[x] = 0;
}

inline int merge(int x, int y) {
    if(!x) return y;
    if(!y) return x;
    if(val[x] > val[y]) std::swap(x, y);
    pushdown(x);
    pushdown(y);
    ch[x][1] = merge(ch[x][1], y);
    if(dis[ch[x][0]] < dis[ch[x][1]]) std::swap(ch[x][0], ch[x][1]);
    dis[x] = dis[ch[x][1]] + 1;
    return x;
}

struct Edge {
    int to, nxt;
} gra[MAXN];
int head[MAXN], tot = 1;

inline void addedge(int u, int v) {
    gra[tot].to = v;
    gra[tot].nxt = head[u];
    head[u] = tot++;
}

int n, m, f, a[MAXN], c[MAXN], dep[MAXN], die[MAXN], end[MAXN];
LL h[MAXN], v[MAXN];

inline void dfs(int u) {
    for(int i = head[u]; i; i = gra[i].nxt) {
        int v = gra[i].to;
        dep[v] = dep[u] + 1;
        dfs(v);
        rt[u] = merge(rt[u], rt[v]);
    }
    while(rt[u] && val[rt[u]] < h[u]) {
        pushdown(rt[u]);
        die[u]++;
        end[rt[u]] = u;
        rt[u] = merge(ch[rt[u]][0], ch[rt[u]][1]);
    }
    if(!a[u]) {
        val[rt[u]] += v[u];
        add[rt[u]] += v[u];
    } else {
        val[rt[u]] *= v[u];
        add[rt[u]] *= v[u];
        mul[rt[u]] *= v[u]; 
    }
}

int main() {
    dis[0] = -1;
    n = readint();
    m = readint();
    for(int i = 1; i <= n; i++) {
        h[i] = readint();
    }
    for(int i = 2; i <= n; i++) {
        f = readint();
        a[i] = readint();
        v[i] = readint();
        addedge(f, i);
    } 
    for(int i = 1; i <= m; i++) {
        val[i] = readint();
        c[i] = readint();
        mul[i] = 1;
        rt[c[i]] = merge(rt[c[i]], i);
    }
    dep[1] = 1;
    dfs(1);
    for(int i = 1; i <= n; i++) {
        printf("%d\n", die[i]);
    }
    for(int i = 1; i <= m; i++) {
        printf("%d\n", dep[c[i]] - dep[end[i]]);
    }
    return 0;
}
左偏树原理与实现

左偏树原理与实现

注:本文部分图片来自互联网,其相关权利归原作者所有,感谢原作者的分享。

概述

左偏树是一种可并堆的类型,它能够实现插入、删除、合并O(\log n)的功能。这里介绍它的原理和实现。

原理

结构

pic1
上图为一个左偏树的示意图。
我们给出一些定义。定义一个点的距离为总是从右子树走到达一个没有右儿子的点的距离。可以发现,所谓左偏,就是指左儿子的距离不小于右儿子的距离,这种性质被称为左偏性
左偏树同时也要满足堆序性,对于小根堆,堆序性指的是对于每个点,值总比它的儿子小。
可以观察到,上图中的左偏树满足以上性质。

合并

左偏树的精髓即为合并操作。要实现O(\log n)的合并操作,我们首先得探究几个性质。
性质 一个点的距离等于右儿子的距离+1。
性质 一个点的左子树和右子树都是左偏树。
以小根堆的合并为例,首先,我们将根较小的一棵树作为基础,取它的右子树跟另外一棵树合并。合并完毕的树的根的距离可能改变,此时如果不满足左偏性需要调换左右子树。此外,还要更新现在根的距离。递归合并即可。

插入

即为一个单点左偏树和一个左偏树合并,直接合并即可。

删除根

重置左右儿子的父亲并且合并左右子树即可。

构造

一种方法是一个一个地插入。
考虑使用队列优化这种构造。从队列中取出2个元素,合并后插入队尾,以此类推,这种构造可以做到O(n)

删除任意

在堆中,没有快速查找某值的位置的方法,但是如果我们知道了一个位置,我们还是可以考虑删除该位置上的点。先合并左右子树,把合并后的左偏树挂到这个点上。这可能会导致这个点父亲不满足左偏性,因此要从这个点到根一层层检查交换左右子树。

例子

下图展示了一个左偏树合并的过程。图片来自远航之曲博客。
左偏树原理与实现

实现

准备工作

我们需要用四个数组构建一棵左偏树。val数组为节点值,fa数组为父亲节点,ch为子节点,dis为该点的距离。距离的定义见上。

合并

需要讨论两棵树存在一棵为空的情况,如果为空返回另一棵。

inline int merge(int x, int y) {
    if(x == 0) return y;
    if(y == 0) return x;
    if(val[x] > val[y]) std::swap(x, y);
    ch[x][1] = merge(ch[x][1], y);
    fa[ch[x][1]] = x;
    if(dis[ch[x][0]] < dis[ch[x][1]]) std::swap(ch[x][0], ch[x][1]);
    dis[x] = dis[ch[x][1]] + 1;
    return x;
}

删除树根

inline void delroot(int x) {
    val[x] = -1;
    fa[ch[x][0]] = fa[ch[x][1]] = 0;
    merge(ch[x][0], ch[x][1]);
}

删除任意

inline void delet(int x) {
    int p = merge(ch[x][0], ch[x][1]);
    fa[p] = fa[x];
    val[x] = -1;
    for(int i = fa[x]; i; i = fa[i]) {
        if(dis[ch[i][0]] < dis[ch[i][1]]) std::swap(ch[i][0], ch[i][1]);
        if(dis[i] == dis[ch[i][1]] + 1) return;
        dis[i] = dis[ch[i][1]] + 1;
    }
}

一道例题:【模板】左偏树(可并堆)

题意

有两种操作:①合并两个小根堆;②查询、删除堆的最小数。

题解

左偏树,支持合并、查所在树以及删除根即可。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>

struct io {
    char buf[1 << 26], *op;
    io() {
        fread(op = buf, 1, 1 << 26, stdin);
    }
    inline int readint() {
        register int res = 0, neg = 1;
        while(*op < '0' || *op > '9') if(*op++ == '-') neg = -1;
        while(*op >= '0' && *op <= '9') res = res * 10 + *op++ - '0';
        return res * neg;
    }
    inline char readchar() {
        return *op++;
    }
} ip;

#define readint ip.readint
#define readchar ip.readchar

// Leftist Tree

int fa[100005], val[100005], dis[100005], ch[100005][2];

inline int getroot(int x) {
    while(fa[x]) x = fa[x];
    return x;
}

inline int merge(int x, int y) {
    if(x == 0) return y;
    if(y == 0) return x;
    if(val[x] > val[y] || (val[x] == val[y] && x > y)) std::swap(x, y);
    ch[x][1] = merge(ch[x][1], y);
    fa[ch[x][1]] = x;
    if(dis[ch[x][0]] < dis[ch[x][1]]) std::swap(ch[x][0], ch[x][1]);
    dis[x] = dis[ch[x][1]] + 1;
    return x;
}

inline void poproot(int x) {
    val[x] = -1;
    fa[ch[x][0]] = fa[ch[x][1]] = 0;
    merge(ch[x][0], ch[x][1]);
}

int n, m, op, x, y;

int main() {
    n = readint();
    m = readint();
    dis[0] = -1;
    for(int i = 1; i <= n; i++) {
        val[i] = readint();
    }
    for(int i = 1; i <= m; i++) {
        op = readint();
        if(op == 1) {
            x = readint();
            y = readint();
            if(val[x] == -1 || val[y] == -1 || x == y) continue;
            x = getroot(x);
            y = getroot(y);
            merge(x, y);
        } else {
            x = readint();
            if(val[x] == -1) {
                printf("-1\n");
                continue;
            }
            x = getroot(x);
            printf("%d\n", val[x]);
            poproot(x);
        }
    }
    return 0;
}

参考资料

[POJ1177]Picture 题解

[POJ1177]Picture 题解

题目地址:POJ:1177 — Picture、vjudge:Picture – POJ 1177 – Virtual Judge、洛谷:【P1856】[USACO5.5]矩形周长Picture – 洛谷

题目描述

A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.
pic1
Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.
pic2
The corresponding boundary is the whole set of line segments drawn in Figure 2.
给若干矩形,求矩形并的周长和(重叠的边只算一次,只计算外围周长)。

输入输出格式

输入格式:
Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.
0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.
输出格式:
Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.

输入输出样例

输入样例#1:

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

输出样例#1:

228

题解

本题是一个扫描线的经典应用,我们按x从小到大的顺序依次扫过矩形的每一条横边,统计这一条横边对答案的贡献(具体而言,就是加入这一段横边后对横向的覆盖的增量),动态维护现在已经覆盖的位置与连续的线段数,借由这些数据还可以顺便算出纵边对答案的贡献,每个连续的横向线段的两侧必然有2个对纵向周长产生贡献的线段。维护已覆盖的位置与连续的线段数可以用线段树实现。设计len表示已覆盖的长度,lin表示区间内连续的线段数。每次合并时len直接加,lin加完以后判断有没有直线跨两个儿子区间减掉重复算的就可以了。
以题目附图为例,下面天蓝色表示扫到这一条线的时候对答案的贡献,深蓝色表示已经覆盖的位置。
pic3
pic4
pic5
pic6
pic7
pic8

代码

// Code by KSkun. 2018/2
#include <cstdio> 
#include <cstring>
#include <vector>
#include <algorithm>

struct Line {
    int x, y1, y2, v;
} line[10005];

inline bool cmp(Line a, Line b) {
    return a.x == b.x ? a.v > b.v : a.x < b.x; 
} 

int n, N, xa, ya, xb, yb, ans;
std::vector<int> vecy;
std::vector<int>::iterator yend;

// Segtree

#define lch o << 1
#define rch (o << 1) | 1
#define mid ((l + r) >> 1)

int val[40005], len[40005], lin[40005];
bool lft[40005], rgt[40005];

inline void callen(int o, int l, int r) {
    if(val[o] > 0) {
        len[o] = vecy[r - 1] - vecy[l - 1];
    } else {
        len[o] = len[lch] + len[rch];
    }
}

inline void callin(int o, int l, int r) {
    if(val[o] > 0) {
        lft[o] = rgt[o] = true;
        lin[o] = 1;
    } else if(l == r) {
        lft[o] = rgt[o] = false;
        lin[o] = 0;
    } else {
        lft[o] = lft[lch];
        rgt[o] = rgt[rch];
        lin[o] = lin[lch] + lin[rch];
        if(rgt[lch] && lft[rch]) lin[o]--; 
    }
}

inline void add(int o, int l, int r, int ll, int rr, int v) {
    if(l == ll && r == rr) {
        val[o] += v;
        callen(o, l, r);
        callin(o, l, r);
        return;
    }
    if(rr <= mid) {
        add(lch, l, mid, ll, rr, v);
    } else if(ll >= mid) {
        add(rch, mid, r, ll, rr, v);
    } else {
        add(lch, l, mid, ll, mid, v);
        add(rch, mid, r, mid, rr, v);
    }
    callen(o, l, r);
    callin(o, l, r);
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
        vecy.push_back(ya);
        vecy.push_back(yb);
        line[i].x = xa;
        line[i].y1 = ya;
        line[i].y2 = yb;
        line[i].v = 1;
        line[i + n].x = xb;
        line[i + n].y1 = ya;
        line[i + n].y2 = yb;
        line[i + n].v = -1;
    }
    std::sort(vecy.begin(), vecy.end());
    yend = std::unique(vecy.begin(), vecy.end());
    N = yend - vecy.begin();
    for(int i = 1; i <= n << 1; i++) {
        line[i].y1 = std::lower_bound(vecy.begin(), yend, line[i].y1) - vecy.begin() + 1;
        line[i].y2 = std::lower_bound(vecy.begin(), yend, line[i].y2) - vecy.begin() + 1;
    }
    std::sort(line + 1, line + (n << 1) + 1, cmp);
    line[0].x = -1e9;
    int lastlen = 0, lastlin = 0;
    for(int i = 1; i <= n << 1; i++) {
        add(1, 1, N, line[i].y1, line[i].y2, line[i].v);
        if(i > 1) ans += 2 * lastlin * (line[i].x - line[i - 1].x);
        ans += std::abs(len[1] - lastlen);
        lastlen = len[1];
        lastlin = lin[1];
    }
    printf("%d", ans);
    return 0;
}

Scroll Up