Codeforces438D题解

发表于

Scape的原题,优美的线段树

题意翻译

给定数列，区间查询和，区间取模，单点修改。

n,m小于10^5

Inputs and Outputs examples

Inputs’ e.g. #1

1
2
3
4
5
6
7
5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

Outputs’ e.g. #1

1
2
8
5

Inputs’ e.g. #2

1
2
3
4
5
6
7
8
9
10
11
12
10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10

Outputs’ e.g. #2

1
2
3
4
5
49
15
23
1
9

分析

Scape数据结构模拟原题赛T3.

看到单点修改这个东西,我们就可以想到线段树了吧qwq

重点是这个区间取模怎么办,我们可以证明一个数最多被取模$\log$次,那么我们就可以考虑记一个区间最大值.

当这个最大值小于模数时,我们就可以直接return,如果大于,我们就像区间查最值一样暴力改下去即可.

代码

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
150
151
152
153
154
155
156
157
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e5 + 10;
#define int long long
struct SegMentTree{
    int max,sum;
}Tree[MAXN << 2];
int n,m,a[MAXN];
/* functions */
inline void pushUp(int k){
    Tree[k].sum = Tree[LeftChild(k)].sum + Tree[RightChild(k)].sum;
    Tree[k].max = std::max(Tree[LeftChild(k)].max,Tree[RightChild(k)].max);
}
inline void Build(int l,int r,int k){
    if(l == r){
        Tree[k].sum = Tree[k].max = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    Build(l,mid,LeftChild(k));
    Build(mid+1,r,RightChild(k));
    pushUp(k);
}
inline void UpdateMod(int k,int l,int r,int L,int R,int mod){
    if(Tree[k].max < mod) return;
    if(l == r){
        Tree[k].sum = Tree[k].sum % mod;
        Tree[k].max = Tree[k].max % mod;
        return ;
    }
    int mid = (l + r) >> 1;
    if(L <= mid) UpdateMod(LeftChild(k),l,mid,L,R,mod);
    if(mid < R) UpdateMod(RightChild(k),mid+1,r,L,R,mod);
    pushUp(k);
}
inline void Updateadd(int k,int l,int r,int place,int val){
    if(l == r){
        Tree[k].sum = Tree[k].max = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if(place <= mid) Updateadd(LeftChild(k),l,mid,place,val);
    else Updateadd(RightChild(k),mid+1,r,place,val);
    pushUp(k);
}
inline int Query(int k,int l,int r,int L,int R){
    if(L <= l && r <= R) return Tree[k].sum;
    int ans = 0;
    int mid = (l + r) >> 1;
    if(L <= mid) ans += Query(LeftChild(k),l,mid,L,R);
    if(mid < R) ans += Query(RightChild(k),mid+1,r,L,R);
    return ans;
}
signed main(void){
    scanf("%lld%lld",&n,&m);
    FOR(i,1,n,1) scanf("%lld",&a[i]);
    Build(1,n,1);
    while(m--){
        int op,l,r,x;
        scanf("%lld",&op);
        if(op == 1ll){
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",Query(1,1,n,l,r));
        }
        if(op == 2ll){
            scanf("%lld%lld%lld",&l,&r,&x);
            UpdateMod(1,1,n,l,r,x);
        }
        if(op == 3ll){
            scanf("%lld%lld",&l,&x);
            Updateadd(1,1,n,l,x);
        }
    }
    return 0;
}

THE END