hiho1116 - 数据结构线段树(区间合并)

题目链接

现在有一个有n个元素的数组a₁, a₂, ..., a_n。

记f(i, j) = a_i * a_i+1 * ... * aj。

初始时，a₁ = a₂ = ... = a_n = 0，每次我会修改一个a_i的值，你需要实时反馈给我 ∑_{1 <= i <= j <= n}f(i, j)的值 mod 10007。

第一行包含两个数n(1<=n<=100000)和q(1<=q<=500000)。

接下来q行，每行包含两个数i, x，代表我把a_i的值改为了x。

/*******************************************************/

记两个数的区间【a,b】

[a,b].sum = a+b+a*b;

[a,b].prefix = a+a*b;

[a,b].suffix = b+a*b;

[a,b].product = a*b;

当合并区间【a,b】和【c,d】时

有[a,b,c,d].sum = [a,b].sum+[c,d].sum+[a,b].suffix*[c,d].prefix;

[a,b,c,d].product = a*b*c*d = [a,b].product*[c,d].product;

.product的存在是为了维护prefix和suffix,因为：

[a,b,c,d].prefix = [a,b].prefix + [a,b].product*[c,d].prefix;

[a,b,c,d].suffix = [c,d].suffix + [c,d].product*[a,b].suffix;

#include <cstdio>

#include <cstring>

const int N = ;

const int MOD = ;

struct NODE{

    int l,r;

    int sum;

    int prefix,suffix,product;

    NODE(){

        sum = prefix = suffix = product = ;

    }

    int MID(){ return (l+r)>>;    }

};

NODE segtree[N*];

void build(int id,int l,int r){

    segtree[id].l = l;

    segtree[id].r = r;

    if(l==r) return ;

    int mid = (l+r)>>;

    build(id*,l,mid);

    build(id*+,mid+,r);

}

void modify(int id,int pos,int value){

    if((segtree[id].l==segtree[id].r)&&(segtree[id].l==pos)){

        segtree[id].sum = segtree[id].prefix = segtree[id].suffix = segtree[id].product = (value)%MOD;

        return ;

    }

    int mid = segtree[id].MID();

    if(pos<=mid) modify(id*,pos,value);

    else modify(id*+,pos,value);

    segtree[id].sum = ((segtree[id*].sum+segtree[id*+].sum)+(segtree[id*].suffix*segtree[id*+].prefix)%MOD)%MOD;

    segtree[id].prefix = (segtree[id*].prefix+(segtree[id*].product*segtree[id*+].prefix)%MOD)%MOD;

    segtree[id].suffix = (segtree[id*+].suffix+(segtree[id*+].product*segtree[id*].suffix)%MOD)%MOD;

    segtree[id].product = (segtree[id*].product*segtree[id*+].product)%MOD;

}

int main(){

    int n,q,a,b;

    scanf("%d%d",&n,&q);

    build(,,n);

    while(q--){

        scanf("%d%d",&a,&b);

        modify(,a,b);

        printf("%d\n",segtree[].sum);

    }

    return ;

}

巴特西

hiho1116 - 数据结构线段树(区间合并)

最新文章

热门文章

巴特西

hiho1116 - 数据结构 线段树(区间合并)

最新文章

热门文章

hiho1116 - 数据结构线段树(区间合并)