文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/CF438D
D
e
s
c
r
i
p
t
i
o
n
Description
Description
写一种数据结构要求支持区间查询和，区间取模，单点修改
数据范围：
n
,
m
≤
1
0
5
n,m\leq 10^5
n,m≤105
S
o
l
u
t
i
o
n
Solution
Solution
难点在取模 一个数至多取模
l
o
g
log
log次，建立指针数组判断最大值位于哪棵子树，然后做单点修改
时间复杂度：
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)
C
o
d
e
Code
Code
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std
;int n
,m
,a
[N
],opt
,l
,r
,x
;
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
struct xds
{
#define lson k<<1
#define rson k<<1|1
LL sum
[N
<<2];int maxn
[N
<<2],p
[N
<<2];
inline void pushup(int k
)
{
sum
[k
]=sum
[lson
]+sum
[rson
];
maxn
[k
]=max(maxn
[lson
],maxn
[rson
]);
p
[k
]=maxn
[k
]==maxn
[lson
]?p
[lson
]:p
[rson
];
return;
}
inline void build(int k
=1,int l
=1,int r
=n
)
{
if(l
==r
)
{
sum
[k
]=a
[l
];
maxn
[k
]=a
[l
];
p
[k
]=l
;
return;
}
int mid
=l
+r
>>1;
build(lson
,l
,mid
);build(rson
,mid
+1,r
);
return (void)(pushup(k
));
}
inline LL
Query(int ql
,int qr
,int k
=1,int l
=1,int r
=n
)
{
if(ql
<=l
&&r
<=qr
) return sum
[k
];
LL res
=0;int mid
=l
+r
>>1;
if(ql
<=mid
) res
+=Query(ql
,qr
,lson
,l
,mid
);
if(qr
>mid
) res
+=Query(ql
,qr
,rson
,mid
+1,r
);
return res
;
}
inline void Updata(int ql
,int qr
,int d
,int k
=1,int l
=1,int r
=n
)
{
if(ql
<=l
&&r
<=qr
) {while(maxn
[k
]>=d
) Modify(p
[k
],maxn
[k
]%d
,k
,l
,r
);return;}
int mid
=l
+r
>>1;
if(ql
<=mid
) Updata(ql
,qr
,d
,lson
,l
,mid
);
if(qr
>mid
) Updata(ql
,qr
,d
,rson
,mid
+1,r
);
return (void)(pushup(k
));
}
inline void Modify(int x
,int d
,int k
=1,int l
=1,int r
=n
)
{
if(l
==r
) {maxn
[k
]=d
;p
[k
]=x
;sum
[k
]=d
;return;}
int mid
=l
+r
>>1;
if(x
<=mid
) Modify(x
,d
,lson
,l
,mid
);
else Modify(x
,d
,rson
,mid
+1,r
);
return (void)(pushup(k
));
}
}T
;
signed main()
{
n
=read();m
=read();
for(register int i
=1;i
<=n
;i
++) a
[i
]=read();
T
.build();
while(m
--)
{
opt
=read();
if(opt
==1)
{
l
=read();r
=read();
printf("%lld\n",T
.Query(l
,r
));
continue;
}
if(opt
==2)
{
l
=read();r
=read();x
=read();
T
.Updata(l
,r
,x
);
continue;
}
if(opt
==3)
{
l
=read();x
=read();
T
.Modify(l
,x
);
continue;
}
}
}
