codeforces

你爱的姑娘，在桥下洗着你最喜欢的衣裳。 ——Wood

CF438D 线段树

传送门： http://codeforces.com/contest/438/problem/D
题解：

线段树维护区间求和，区间取模（更新），单点修改

维护区间最大值剪枝，记录区间最大值。

复杂度：nlogn(很神) 如果X比区间最大值还大，不用取模更新。否则暴力更新。

y mod x,如果x>y/2,那么y取模后小于y/2;

​ 如果x<y/2, 取模后也小于y/2;

所以每个数取模不会超过logn次。

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

#include<bits/stdc++.h>
#define LL long long
//区间求和 区间取模 单点更新
using namespace std;
const int N = 100010;
struct Tree{
    int l;
    int r;
    LL sum;
    LL  lazy; //延迟标记
    LL maxn;
};
Tree tree[N*4];
int ma[N];
int n,m;
LL max(LL a, LL b){
return a>b?a:b;
}
void up(int x){ //更新区间和
    tree[x].sum = tree[x<<1].sum+tree[x<<1|1].sum;
    tree[x].maxn = max(tree[x<<1].maxn,tree[x<<1|1].maxn);
}
//延迟标记 用于区间加
void down(int x){
      LL t = tree[x].lazy;
      if(t){
        tree[x].lazy =0;
        tree[x<<1].sum+=(tree[x<<1].r-tree[x<<1].l+1)*t;
        tree[x<<1].lazy+=t;
        tree[x<<1|1].sum+=(tree[x<<1|1].r - tree[x<<1|1].l+1)*t;
        tree[x<<1|1].lazy+=t;
      }
}

//build
void build(int x,int l,int r){
    tree[x].l=l;
    tree[x].r=r;
    tree[x].lazy=0;
    if(l==r){
         tree[x].maxn = tree[x].sum=ma[l];
        return;
    }
    else{
        int mid = l+( (r-l)>>1);
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        up(x);
    }
}

//单点更新 x k v
void update1(int x,int k,int v){
    int ll = tree[x].l;
    int rr = tree[x].r;
    if(ll==rr){
        tree[x].maxn=tree[x].sum=v;
        return;
    }
    int mid = ll+((rr-ll)>>1);
    if(k<=mid) update1(x<<1,k,v);
    else  update1(x<<1|1,k,v);
    up(x);

}

//区间加操作 x l r v
void update(int x,int l,int r,int v){
    int ll = tree[x].l;
    int rr = tree[x].r;
    if(l>r){
        return;
    }
    if(ll==l&&rr==r){
        tree[x].sum += (tree[x].r - tree[x].l+1)*v;
        tree[x].lazy+=v;
    }
    else{
        int mid = ll+((rr-ll)>>1);
        down(x);
        update(x<<1,l,min(mid,r),v);
        update(x<<1|1,max(mid+1,l),r,v);
        up(x);
    }
}
//区间取模
void updateModify(int x,int l,int r,int v){
    int ll = tree[x].l;
    int rr = tree[x].r;
    if(l>tree[x].r || r<tree[x].l || v>tree[x].maxn) return;  //maxn主要用于在这剪枝
    if(tree[x].l==tree[x].r){
        tree[x].sum = tree[x].maxn = tree[x].sum % v;
        return;
    }
    int mid = ll+((rr-ll)>>1);
    if(r<=mid) updateModify(x<<1,l,r,v);
    else if(l>mid) updateModify(x<<1|1,l,r,v);
    else{
        updateModify(x<<1,l,mid,v);
        updateModify(x<<1|1,mid+1,r,v);
    }
    up(x);
}

//区间查询
LL quary(int x,int l,int r){
    int ll = tree[x].l;
    int rr = tree[x].r;
    if(l>r) return 0;
    if(ll==l&&rr==r){
        return tree[x].sum;
    }
    else{
        int mid = ll + ((rr-ll)>>1);
        LL ans=0;
        down(x);
        ans+=quary(x<<1,l,min(mid,r));
        ans+=quary(x<<1|1,max(mid+1,l),r);
        up(x);
        return ans;
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&ma[i]);
    }
    build(1,1,n);
    while(m--){
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        switch(op){
        case 1:
            printf("%lld\n",quary(1,a,b));
            break;
        case 2:
            LL v;
            scanf("%lld",&v);
            updateModify(1,a,b,v);
            break;
        default:
            update1(1,a,b);
            break;
        }
    }
return 0;
}