社区讨论
代码70pts,reload()怎么去掉
P3373【模板】线段树 2参与者 4已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mk2j8z79
- 此快照首次捕获于
- 2026/01/06 19:55 上个月
- 此快照最后确认于
- 2026/01/10 08:55 上个月
记得开ull,ll会爆
代码70pts,复杂度平方不知道怎么去掉(更改之后必须刷新一下,不然就WA),求调
CPP#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N = 1e5 + 5;
int n, m, q;
struct node{
int l, r, lf, rt, sm, lz_add, lz_multi;
/*
l: left border
r: right border
lf: left son
rt: right son
sm: the sum of the values
lz_add: unadded value for sons
lz_multi: unmultipled value for sons
*/
int len() { return r - l + 1; }//get length
void modify_add(int x){//add value
sm += x * len(), sm %= m, lz_add += x;
}
void modify_multi(int x){//multiply value
sm *= x, sm %= m, lz_multi *= x;
}
void merge(node a, node b){//get the sum of node a and b
sm = a.sm + b.sm;
}
node(){
l = lf = rt = sm = lz_add = 0, r = -1, lz_multi = 1;
}
};
struct smt{
int cnt; node a[N << 1];
void build(int l, int r, int x){//build node,left border = l,right border = r,node pointer = x
a[x].l = l, a[x].r = r;
if (l == r){//quit if there's only one member
return;
}
int mid = ((l + r) >> 1);
a[x].lf = ++cnt, a[x].rt = ++cnt;
build(l, mid, a[x].lf), build(mid + 1, r, a[x].rt);//build son
}
void update_add(int x){//load the unadded value
if (a[x].lz_add){
a[a[x].lf].modify_add(a[x].lz_add), a[a[x].rt].modify_add(a[x].lz_add);
a[x].lz_add = 0;
}
}
void update_multi(int x){//load the unmultipled value
if (a[x].lz_multi>1){
a[a[x].lf].modify_multi(a[x].lz_multi), a[a[x].rt].modify_multi(a[x].lz_multi);
a[x].lz_multi = 1;
}
}
void modify_add(int x, int s, int t, int d){//add value d from range [s,t],x = present node
if (a[x].r < s || t < a[x].l){//the range isn't in [s,t]
return;
}
if (s <= a[x].l && a[x].r <= t){//add if the range is in [s,t]
a[x].modify_add(d);
return;
}
update_add(x);//add the value to sons
modify_add(a[x].lf, s, t, d), modify_add(a[x].rt, s, t, d);//sons
a[x].merge(a[a[x].lf], a[a[x].rt]);//check value in the present node
}
void modify_multi(int x, int s, int t, int d){//multiply value d from range [s,t],x = present node
if (a[x].r < s || t < a[x].l){//the range isn't in [s,t]
return;
}
if (s <= a[x].l && a[x].r <= t){//multiply if the range is in [s,t]
a[x].modify_multi(d);
return;
}
update_multi(x);//multiply the value to sons
modify_multi(a[x].lf, s, t, d), modify_multi(a[x].rt, s, t, d);//sons
a[x].merge(a[a[x].lf], a[a[x].rt]);//check value in the present node
}
node query(int x, int s, int t){//query the sum of [s,t] , x = present node
if (a[x].r < s || t < a[x].l){//the range isn't in [s,t]
return node();
}
if (s <= a[x].l && a[x].r <= t){//add to sum if the range is in [s,t]
return a[x];
}
update_multi(x);//multiply the value to sons
update_add(x);//load the value to sons
node tmp; tmp.merge(query(a[x].lf, s, t), query(a[x].rt, s, t));//get the data of [s,t]
return tmp;
}
void reload()
{
for(int i=1;i<=cnt;i++)update_multi(i),update_add(i);
}
smt(){
cnt = 1;
}
} sum;
signed main(){
freopen("D:\\P3373_4.in","r",stdin);
cin >> n >> q >> m;
sum.build(1, n, 1);
for (int i = 1; i <= n; i++){
int x; cin >> x;
sum.modify_add(1, i, i, x);//set start value
}
while (q--){
int op; cin >> op;
if (op == 2){
int x, y, k; cin >> x >> y >> k;
sum.modify_add(1, x, y, k);//operate value
sum.reload();
}
else if (op == 1)
{
int x, y, k; cin >> x >> y >> k;
sum.modify_multi(1, x, y, k);//operate value
sum.reload();
}
else{
int x, y; cin >> x >> y;
cout << ((sum.query(1, x, y)).sm) % m << "\n";//query the sum
}
}
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...