AC日记——The Child and Sequence codeforces 250D

D - The Child and Sequence

思路：

　　因为有区间取模操作所以没法用标记下传；

　　我们发现，当一个数小于要取模的值时就可以放弃；

　　凭借这个来减少更新线段树的次数；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 100005

#define ll long long

struct TreeNodeType {

    ll l, r, mid, dis, max;

};

struct TreeNodeType tree[maxn << ];

ll n,m;

inline void in(ll &now)

{

    char Cget = getchar(); now = ;

    while (Cget > '' || Cget < '') Cget = getchar();

    while (Cget >= ''&&Cget <= '')

    {

        now = now *  + Cget - '';

        Cget = getchar();

    }

}

void tree_build(ll now, ll l, ll r)

{

    tree[now].l = l, tree[now].r = r;

    if (l == r)

    {

        in(tree[now].dis);

        tree[now].max = tree[now].dis;

        return;

    }

    tree[now].mid = l + r >> ;

    tree_build(now << , l, tree[now].mid);

    tree_build(now <<  | , tree[now].mid + , r);

    tree[now].dis = tree[now << ].dis + tree[now <<  | ].dis;

    tree[now].max = max(tree[now << ].max, tree[now <<  | ].max);

}

void tree_to(ll now, ll to,ll x)

{

    if (tree[now].l == tree[now].r)

    {

        tree[now].dis = x;

        tree[now].max = x;

        return;

    }

    if (to <= tree[now].mid) tree_to(now << , to, x);

    else tree_to(now <<  | , to, x);

    tree[now].dis = tree[now << ].dis + tree[now <<  | ].dis;

    tree[now].max = max(tree[now << ].max, tree[now <<  | ].max);

}

void tree_mod(ll now, ll l, ll r, ll x)

{

    if (tree[now].max < x) return;

    if (tree[now].l >= l&&tree[now].r <= r) tree[now].dis %= x, tree[now].max %= x;

    if (tree[now].l == tree[now].r) return;

    if (l <= tree[now].mid) tree_mod(now << , l, r, x);

    if (r > tree[now].mid) tree_mod(now << |, l, r, x);

    tree[now].dis = tree[now << ].dis + tree[now <<  | ].dis;

    tree[now].max = max(tree[now << ].max, tree[now <<  | ].max);

    //cout <<"^ "<< l << ' ' << r << ' ' << tree[now].dis << ' ' << tree[now].max << endl;

}

ll tree_query(ll now, ll l, ll r)

{

    if (tree[now].l == l&&tree[now].r == r) return tree[now].dis;

    if (l > tree[now].mid) return tree_query(now <<  | , l, r);

    else if (r <= tree[now].mid) return tree_query(now << , l, r);

    else return tree_query(now << , l, tree[now].mid) + tree_query(now <<  | , tree[now].mid + , r);

}

int main()

{

    in(n), in(m);

    tree_build(, , n);

    ll op, u, v, x;

    for (; m--;)

    {

        in(op),in(u),in(v);

        if (op == ) printf("%lld\n", tree_query(, u, v));

        if (op == ) in(x), tree_mod(, u, v, x);

        if (op == ) tree_to(, u, v);

    }

    return ;

}