2020牛客寒假算法基础集训营3 - G. 牛牛的Link Power II(线段树)

题目链接：牛牛的Link Power II

题意：给你一个只含$0$和$1$的串，定义串的$Link$值为串中两个的$1$之间的距离的和，$(u,v)$和$(v,u)$被看认为是同一对，有$m$次操作，每次操作可以把串中某个$1$变为$0$，或者把某个$0$变为$1$，求一开始和每次操作后串的$Link$值。

思路：线段树，维护区间内$1$的数量$cnt、$区间的$Link$值$w、$区间内所有的$1$到区间左边界的距离之和$dl、$区间内所有的$1$到区间右边界的距离之和$dr$，查询时只要输出$tree[1].w$即可，修改时只用改变区间内$1$的$cnt$，然后进行区间合并，区间合并的公式画个图推导一下即可。

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

typedef long long ll;

const int N = ;

const ll mod = ;

struct node {

    int l, r;

    ll dl, dr, w, cnt;

};

node tree[ * N];

char s[N];

int n, q;

void update(int k)

{

    tree[k].cnt = tree[ * k].cnt + tree[ * k + ].cnt;

    ll t = tree[ * k].cnt * tree[ * k + ].dl + tree[ * k + ].cnt * tree[ * k].dr;

    tree[k].w = tree[ * k].w + tree[ * k + ].w + t + tree[ * k].cnt * tree[ * k + ].cnt;

    tree[k].dl = tree[ * k].dl + tree[ * k + ].dl + tree[ * k + ].cnt * (tree[ * k].r - tree[ * k].l + );

    tree[k].dr = tree[ * k].dr + tree[ * k + ].dr + tree[ * k].cnt * (tree[ * k + ].r - tree[ * k + ].l + );

}

void build(int k, int lef, int rig)

{

    tree[k].l = lef, tree[k].r = rig;

    if (tree[k].l == tree[k].r) {

        tree[k].w = tree[k].dl = tree[k].dr = ;

        if ('' == s[tree[k].l]) tree[k].cnt = ;

        else tree[k].cnt = ;

        return;

    }

    int mid = (lef + rig) / ;

    build(k * , lef, mid);

    build(k *  + , mid + , rig);

    update(k);

}

void change_point(int k, int x, int y)

{

    if (tree[k].l == tree[k].r) {

        tree[k].cnt = y;

        return;

    }

    int mid = (tree[k].l + tree[k].r) / ;

    if (x <= mid) change_point( * k, x, y);

    else change_point( * k + , x, y);

    update(k);

}

int main()

{

    scanf("%d%s", &n, s + );

    build(, , n);

    printf("%lld\n", tree[].w % mod);

    scanf("%d", &q);

    while (q--) {

        int kd, pos;

        scanf("%d%d", &kd, &pos);

        change_point(, pos,  == kd ?  : );

        printf("%lld\n", tree[].w % mod);

    }

    return ;

}

巴特西

2020牛客寒假算法基础集训营3 - G. 牛牛的Link Power II(线段树)

最新文章

热门文章