P4180 [BJWC2010]严格次小生成树

可以证明，有至少一个（严格）次小生成树，和最小生成树之间只有一条边的差异。

先求出该图的最小生成树。

对于每一条边 e(u,v) ，若 \delta(u,v) 上存在一条严格次小于 e(u,v) 的边权，则可以用 e(u,v) 替换该边。

树剖或倍增求出路径上的最大、次大值即可。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e5 + 5, M = 3e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;

class UnionSet {
public :
    static const int N = ::N;
    int fa[N];

    UnionSet() {
        for(int i = 1; i < N; i++) fa[i] = i;
    }

    int leader(int x) {
        return fa[x] == x ? x : fa[x] = leader(fa[x]);
    }

    void merge(int x, int y) {
        int fax = leader(x), fay = leader(y);
        if(fax == fay) return ;
        fa[fax] = fay;
    }
} us;

struct Prepare {
    int u, v, w;
    bool operator<(const Prepare& a) const {
        return w < a.w;
    }
} e[M << 1];

int used[M];

struct Edge {
    int to, nxt, wei;
} Edge[M << 1];

int head[N], cnt;

void addEdge(int u, int v, int w) {
    Edge[++cnt].to = v;
    Edge[cnt].nxt = head[u];
    Edge[cnt].wei = w;
    head[u] = cnt;
}

int dep[N], fa[N][20], maxx[N][20], cmax[N][20], belongTo[N];

void dfs1(int u, int d, int depth) {
    dep[u] = depth; fa[u][0] = d;
    for(int i = 1; i <= 19; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = head[u]; i; i = Edge[i].nxt) {
        const int v = Edge[i].to;
        if(v == d) continue;
        dfs1(v, u, depth + 1);
        belongTo[v] = Edge[i].wei;
    }
}

typedef pair<int, int> pi;

pi merge(int a, int b, int c, int d) {
    vector<int> res {a, b, c, d};
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return make_pair(res[res.size() - 1], res.size() == 1 ? 0 : res[res.size() - 2]);
}

pi merge(int a, int b, int c, int d, int e, int f) {
    pi res = merge(a, b, c, d);
    return merge(res.first, res.second, e, f);
}

pi merge(int u, int v, int t) {
    return merge(maxx[u][t], cmax[u][t], maxx[v][t], cmax[v][t]);
}

void dfs2(int u, int d) {
    maxx[u][0] = belongTo[u];
    for(int i = 1; i <= 19; i++) {
        pi res = merge(u, fa[u][i - 1], i - 1);
        maxx[u][i] = res.first; cmax[u][i] = res.second;
    }

    for(int i = head[u]; i; i = Edge[i].nxt) {
        const int v = Edge[i].to;
        if(v == d) continue;
        dfs2(v, u);
    }
}

pi judge(int x, int y) {
    pi res = make_pair(0, 0);
    if(dep[x] < dep[y]) swap(x, y);
    int dis = dep[x] - dep[y];
    for(int i = 19; ~i; i--) if(dis & (1 << i)) {
        res = merge(res.first, res.second, maxx[x][i], cmax[x][i]);
        x = fa[x][i];
    }
    if(x == y) return res;
    for(int i = 19; ~i; i--) if(fa[x][i] != fa[y][i]) {
        res = merge(res.first, res.second, maxx[x][i], maxx[y][i], cmax[x][i], cmax[y][i]);
        x = fa[x][i]; y = fa[y][i];
    }
    res = merge(res.first, res.second, maxx[x][0], cmax[x][0], maxx[y][0], cmax[y][0]);
    return res;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    memset(cmax, 0xaf, sizeof cmax);
    memset(maxx, 0xaf, sizeof maxx);
    int n = rd(), m = rd();
    for(int i = 1; i <= m; i++) {
        e[i].u = rd(), e[i].v = rd(), e[i].w = rd();
    }
    sort(e + 1, e + m + 1);
    int sum = 0;
    for(int i = 1; i <= m; i++) {
        if(us.leader(e[i].u) == us.leader(e[i].v)) continue;
        addEdge(e[i].u, e[i].v, e[i].w); 
        addEdge(e[i].v, e[i].u, e[i].w);
        used[i] = true; sum += e[i].w;
        us.merge(e[i].u, e[i].v);
    }
    dfs1(1, 1, 1);
    dfs2(1, 1);
    int ans = inf;
    for(int i = 1; i <= m; i++) {
        if(used[i]) continue;
        if(e[i].u == e[i].v) continue;
        pi res = judge(e[i].u, e[i].v);
        int r = res.first == e[i].w ? res.second : res.first;
        ans = min(ans, sum - r + e[i].w);
    }
    cout << ans << endl;
    return 0;
}

P3787 冰精冻西瓜

本题区间修改，单点查询。

考虑到我们不会区间修改一些不同的量，所以只能在单点查询上下文章。

考虑我们能不能区间修改相同的量。

设 tot_u 表示 \delta(u, root) 的边权之积，root 为 u 所在树的树根。

注意到乘法具有可逆操作。如果我们统一地按照改动在树根上处理。就可以区间修改相同的值了。

对于边权为 0 的值特判即可。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define double long double
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e5 + 5, M = 1e5 + 5;

class SegmentTree {
public: 
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
    static const int N = 1e6 + 6;
    double val[N << 2], lzy[N << 2];
    void build(int l, int r, int x) {
        if(l == r) {
            cin >> val[x];
            return ;
        }
        MID; build(lson); build(rson);
        push_up(x);
    }

    void push_up(int x) {
        val[x] = val[x << 1] + val[x << 1 | 1];
    }

    void push_down(int l, int r, int x) {
        if(lzy[x]) {
            MID;
            val[x << 1] += lzy[x] * (mid - l + 1);
            val[x << 1 | 1] += lzy[x] * (r - mid);
            lzy[x << 1] += lzy[x];
            lzy[x << 1 | 1] += lzy[x];
            lzy[x] = 0;
        }
    }

    void add(int l, int r, int x, int p, int q, double v) {
        if(p <= l && r <= q) {
            val[x] += v * (r - l + 1);
            lzy[x] += v;
            return ;
        }
        MID; push_down(l, r, x);
        if(p <= mid) add(lson, p, q, v);
        if(q > mid) add(rson, p, q, v);
        push_up(x);
    }

    double query(int l, int r, int x, int p, int q) {
        if(p <= l && r <= q) {
            return val[x];
        }
        MID; push_down(l, r, x); double res = 0;
        if(p <= mid) res += query(lson, p, q);
        if(q > mid) res += query(rson, p, q);
        return res;
    }
} st;

const double eps = 0.00000001;
template<typename T>
T myabs(T x) {
    return x < 0 ? -x : x;
}

struct Prepare {
    int u, v;
    double w;
} e[N << 1];

class Graph {
public :
    static const int N = ::N, M = ::M;
    struct Edge {
        int to, nxt;
        double wei;
    } Edge[M << 1];

    int head[N], cnt;

    void addEdge(int u, int v, double w) {
        Edge[++cnt].to = v; 
        Edge[cnt].nxt = head[u];
        Edge[cnt].wei = w;
        head[u] = cnt;
    }
} g, gn;

vector<int> root;

void dfs1(int u, int d) {
    for(int i = g.head[u]; i; i = g.Edge[i].nxt) {
        const int v = g.Edge[i].to;
        if(v == d) continue;
//      printf("%d %d %.8lf\n", u, v, g.Edge[i].wei);
        if(myabs(g.Edge[i].wei) <= eps) {
            root.push_back(v);
        } else {
            gn.addEdge(u, v, g.Edge[i].wei);
            gn.addEdge(v, u, g.Edge[i].wei);
        }
        dfs1(v, u);
    }
}

int id[N], sz[N], idx;
double tot[N], c[N];
void dfs2(int u, int d) {
    id[u] = ++idx; sz[u] = 1;
    for(int i = gn.head[u]; i; i = gn.Edge[i].nxt) {
        const int &v = gn.Edge[i].to;
        if(v == d) continue;
        tot[v] = tot[u] * gn.Edge[i].wei;
        dfs2(v, u);
        sz[u] += sz[v];
    }
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd();
    for(int i = 1; i < n; i++) {
        int u = rd(), v = rd(); double w;
        scanf("%Lf", &w);
        e[i].u = u, e[i].v = v, e[i].w = w;
        g.addEdge(u, v, w); g.addEdge(v, u, w);
    }

    root.push_back(1);
    dfs1(1, 1);

//  for(auto it : root) cout << it << " "; cout << endl;
    for(auto it : root) {
        tot[it] = 1;
        dfs2(it, it);
    }

    int m = rd();
    for(int i = 1; i <= m; i++) {
        int opt = rd();
        if(opt == 1) {
            int pos = rd(); double v; scanf("%Lf", &v);
            st.add(1, n, 1, id[pos], id[pos] + sz[pos] - 1, v / tot[pos]);
        } else if(opt == 9) {
            int x = rd();
            printf("%.8Lf\n", st.query(1, n, 1, id[x], id[x]) * tot[x]);
        }
    }

    return 0;
}

P1712 [NOI2016] 区间

首先离散化不会影响答案。故离散化。

将区间按照长度排序后，应用双指针的思想。

发现我们还要维护是否有区间长度 >=m 因此线段树维护即可。

「接着我们又注意到题目要求的答案跟“最大”，“最小”有关，所以我们就会联想到单调性。」

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e6 + 233;
struct Lens {
    int l, r, len;
    bool operator<(const Lens& a) const {
        return len < a.len;
    }
} a[N];

vector<int> b;
int getRnk(int x) {
    return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
}

class SegmentTree { 
public :
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
    static const int N = ::N;
    int maxx[N << 2], sum[N << 2], add[N << 2];

    void modify_add(int l, int r, int x, int p, int q, int v) {
        if(p <= l && r <= q) {
            sum[x] = (r - l + 1) * v;
            maxx[x] += v;
            add[x] += v;
            return ;
        }
        MID; push_down(l, r, x);
        if(p <= mid) modify_add(lson, p, q, v);
        if(q > mid) modify_add(rson, p, q, v);
        push_up(x);
    }

    void push_up(int x) {
        sum[x] = sum[x << 1] + sum[x << 1 | 1];
        maxx[x] = max(maxx[x << 1], maxx[x << 1 | 1]);
    }

    void push_down(int l, int r, int x) {
        if(!add[x]) return ;
        MID;
        sum[x << 1] += (mid - l + 1) * add[x];
        sum[x << 1 | 1] += (r - mid) * add[x];
        add[x << 1] += add[x];
        add[x << 1 | 1] += add[x];
        maxx[x << 1] += add[x];
        maxx[x << 1 | 1] += add[x];
        add[x] = 0;
    }
} st;

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), m = rd();
    for(int i = 1; i <= n; i++) {
        a[i].l = rd(), a[i].r = rd();
        b.push_back(a[i].l); b.push_back(a[i].r);
        a[i].len = a[i].r - a[i].l + 1;
    }

    sort(b.begin(), b.end());
    for(int i = 1; i <= n; i++) {
        a[i].l = getRnk(a[i].l);
        a[i].r = getRnk(a[i].r);
    }

    sort(a + 1, a + n + 1);

    int ans = 0x3f3f3f3f, l = 0, r = 0;
    while(r < n) {
        while(r < n && st.maxx[1] < m) {
            ++r;
            st.modify_add(1, 2 * n + 5, 1, a[r].l, a[r].r, 1);
        }
        if(st.maxx[1] == m) {
            while(l < r && st.maxx[1] == m) {
                ++l;
                st.modify_add(1, 2 * n + 5, 1, a[l].l, a[l].r, -1);
            }
            ans = min(ans, a[r].len - a[l].len);
        }
    }

    if(ans == 0x3f3f3f3f) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

P3616 富金森林公园

考虑一个定理。对于一个相邻数字两两不相等的数列，其 peak-valley = 1 （两端数字为 -inf），其中 peak 和 valley 的定义为严格小于（大于）。

证明考虑数学归纳法。

考虑扩充定义使得该命题对于相邻两数字相等的情况也成立。

如果将 peak 定义为 a_{i-1} <= a_i > a{i+1} ，valley 定义为 a_{i-1} > a_i <= a_{i + 1} 。

我们发现上述命题同样成立。

因此本题可以维护可见的山峰和山谷。 peak - valley 即是答案。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

vector<int> b;
int getRnk(int x) {
    return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
}

const int N = 4e5 + 5, inf = 0x3f3f3f3f;

class TreeArray {
public :
    static const int N = ::N;
    int sum[N];
    int lowbit(int x) { return x & -x; }
    void add(int u, int v) { u++; for(int i = u; i < N; i += lowbit(i)) sum[i] += v; }
    int query(int u) { u++; int res = 0; for(int i = u; i; i -= lowbit(i)) res += sum[i]; return res; }
} peak, valley;

struct Question {
    int opt, x, y;
} Ques[N];

int a[N];

int totpeak = 0, totvalley = 0;
void update(int i, int v) {
    if(a[i - 1] <= a[i] && a[i] > a[i + 1]) peak.add(a[i], v), totpeak += v;
    if(a[i - 1] > a[i] && a[i] <= a[i + 1]) valley.add(a[i], v), totvalley += v;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), m = rd();
    for(int i = 1; i <= n; i++) {
        a[i] = rd();
        b.push_back(a[i]);
    }

    for(int i = 1; i <= m; i++) {
        Ques[i].opt = rd();
        Ques[i].x = rd();
        if(Ques[i].opt == 1) {
            b.push_back(Ques[i].x);
        } else if (Ques[i].opt == 2) {
            Ques[i].y = rd();
            b.push_back(Ques[i].y);
        }
    }

    sort(b.begin(), b.end());
    for(int i = 1; i <= n; i++) {
        a[i] = getRnk(a[i]);
    }

    for(int i = 1; i <= m; i++) {
        if(Ques[i].opt == 1) {
            Ques[i].x = getRnk(Ques[i].x);
        } else if(Ques[i].opt == 2) {
            Ques[i].y = getRnk(Ques[i].y);
        }
    }

    a[0] = -inf; a[n + 1] = -inf;
    for(int i = 1; i <= n; i++) {
        update(i, 1);
    }

    for(int j = 1; j <= m; j++) {
        if(Ques[j].opt == 1) {
            int x = Ques[j].x;
            printf("%d\n", totpeak - peak.query(x - 1) - (totvalley - valley.query(x - 1)));
        } else if(Ques[j].opt == 2) {
            int i = Ques[j].x, v = Ques[j].y;
            update(i, -1); 
            if(i != 1) update(i - 1, -1); 
            if(i != n) update(i + 1, -1);
            a[i] = v;
            update(i, 1); 
            if(i != 1) update(i - 1, 1); 
            if(i != n) update(i + 1, 1);
        }
    }
    return 0;
}

P3313 [SDOI2014]旅行

不想写。

树剖然后暴力开线段树就行。动态开点。

P4216 [SCOI2015]情报传递

不想写。

将每一个开始搜集情报的点打上标记（即开始时间） t_0，对于查询，设当前时间为 t。

查询对于 \theta(u,v) 上的所有点，有多少点满足 t - t_0 > C。即 t_0 < t - C 。

套路性的主席树维护即可。

最后修改：2021 年 01 月 27 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏