暑期集训20190730 取模(mod)

用线段树处理，用线段树维护区间最大值以及区间和。

进行取模操作时，如果x> 区间最大值那么退出，否则两边都递归下去。

（其实第一次做也不太明白，套模板加瞎蒙数据结果还真ac了）

这里先码一下，再复习一下线段树之后编辑详细思路。

#include <bits/stdc++.h>

#define N 1000010

#define fuck return

using namespace std;

typedef long long ll;

int n, m;

int arr[N], l[N], r[N], maxn[N];

ll sum[N];

void upd(int num) {

    sum[num] = sum[num*] + sum[num*|];

    maxn[num] = max(maxn[num*], maxn[num*|]);

    fuck;

}

void build(int num, int pos, int y) {

    l[num] = pos, r[num]=y;

    if(pos == y) {

        maxn[num] = arr[pos];

        sum[num] = arr[pos];

        fuck;

    }

    build(num*, pos, (pos+y)/);

    build(num*|, (pos+y)/+ ,y);

    upd(num);

}

void mod(int num, int pos, int y, int val) {

    if(pos>r[num] || y<l[num] || maxn[num]<val) fuck;

    if(l[num] == r[num]) {

        sum[num] %= val;

        maxn[num] = sum[num];

        fuck;

    }

    mod(num*, pos, y, val);

    mod(num*|, pos, y, val);

    upd(num);

}

void act(int num, int pos, int y) {

    if(l[num] == r[num]) {

        maxn[num] = y;

        sum[num] = y;

        fuck;

    }

    if(pos <= (l[num] + r[num]) / ) act(num*, pos, y);

    else act(num*|, pos, y);

    upd(num);

}

ll output(int num, int pos, int y) {

    if(pos>r[num] || y<l[num]) fuck ;

    if(pos<=l[num] && y>=r[num]) fuck sum[num];

    fuck output(num*, pos, y) + output(num*|, pos, y);

}

int main() {

    freopen("mod.in", "r", stdin);

    freopen("mod.out", "w", stdout);

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

    for(int i=; i<=n; i++) {

        scanf("%d", &arr[i]);

    }

    build(, , n);

    int pos, y, val, opt;

    while(m--) {

        scanf("%d", &opt);

        switch(opt) {

            case :

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

                printf("%lld\n", output(, pos, y));

                break;

            case :

                scanf("%d%d%d", &pos, &y, &val);

                mod(, pos, y, val);

                break;

            case :

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

                act(, pos, y);

                break;

        }

    }

    fuck ;

}

//being fucked by this code (2) hr (16) min