社区讨论

代码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 条回复,欢迎继续交流。

正在加载回复...