洛谷P3373线段树2！求调！

Question

洛谷P3373 【模板】线段树 2
代码基本是跟着洛谷《深进》写的，改成了结构体的形式
样例是对的

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
typedef long long ll;
int n,q,m;ll a[MAXN];
struct node{
    //sum表示区间和,lzy_add是加法的懒标记,lzy_mul是乘法的懒标记 
    ll sum,lzy_add,lzy_mul;
    node(){sum=lzy_add=0;lzy_mul=1;}
}w[MAXN*4];
inline void pushup(const int u){//更新节点u的值 
    w[u].sum=(w[u<<1].sum+w[(u<<1)+1].sum)%m;
}
void build(const int u,int L,int R){//建立线段树 
    if(L==R){
        w[u].sum=a[L];
        return;
    }
    int M=L+R>>1;
    build(u<<1,L,M);
    build((u<<1)+1,M+1,R);
    pushup(u);
}
//制作懒标记 
inline void make_tag(const int u,int L,int R,int type,ll num){
    if(type==1){//type=1表示*
        w[u].sum*=num;
        w[u].lzy_mul*=num;
        w[u].lzy_add*=num;
    }
    else{//type=2表示+
        w[u].sum+=(R-L+1)*num;
        w[u].lzy_add+=num;
    }
    w[u].sum%=m;w[u].lzy_add%=m;w[u].lzy_mul%=m;
}
inline void pushdown(const int u,int L,int R){//懒标记下放 
    int M=L+R>>1;
    make_tag(u<<1,L,M,2,w[u].lzy_add);
    make_tag(u<<1,L,M,1,w[u].lzy_mul);
    make_tag((u<<1)+1,M+1,R,2,w[u].lzy_add);
    make_tag((u<<1)+1,M+1,R,1,w[u].lzy_mul);
    w[u].lzy_add=0;w[u].lzy_mul=1;
}
bool InRange(int L,int R,int l,int r){//判断[L,R]是否完全被[l,r]包含
    return l<=L&&R<=r;
}
bool OutofRange(int L,int R,int l,int r){//判断[L,R]与[l,r]完全无交集
    return L>r||R<l;
}
ll query(const int u,int L,int R,int l,int r){//查询[l,r]的区间和
    if(InRange(L,R,l,r))return w[u].sum;
    else if(!OutofRange(L,R,l,r)){
        int M=L+R>>1;
        pushdown(u,L,R);
        return (query(u<<1,L,M,l,r)+query((u<<1)+1,M+1,R,l,r))%m;
    }
    return 0;
}
//修改[l,r] 
void update(const int u,int L,int R,int l,int r,int type,ll num){
    if(InRange(L,R,l,r))make_tag(u,L,R,type,num);
    else if(!OutofRange(L,R,l,r)){
        int M=L+R>>1;
        pushdown(u,L,R);
        update(u<<1,L,M,l,r,type,num);
        update((u<<1)+1,M+1,R,l,r,type,num);
        pushup(u);
    }
}
int main(){
    scanf("%d%d%d",&n,&q,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        int opt;
        scanf("%d",&opt);
        if(opt==1||opt==2){
            int x,y;ll k;
            scanf("%d%d%lld",&x,&y,&k);
            update(1,1,n,x,y,opt,k);
        }
        else{
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

Answer 1

晚上好🌙🌙🌙
本答案参考通义千问

你的代码整体结构是正确的，但在实现过程中存在一些问题需要修正。以下是分析和解决方案：

问题分析

1. 懒标记的处理不正确：

   • 在 pushdown 函数中，懒标记的传递顺序和计算方式有问题。
   • 懒标记的更新逻辑没有正确处理加法和乘法的优先级。

2. 懒标记的初始化和使用不一致：

   • 懒标记的初始值应该是 1 和 0，但你在构造函数中已经正确初始化了。

3. 区间更新时的懒标记合并问题：

   • 在 update 函数中，懒标记的传递和合并逻辑不完整。

解决方案

以下是修正后的代码，重点解决了上述问题，并优化了一些细节：

#include <bits/stdc++.h>
using namespace std;

#define MAXN 1000010
typedef long long ll;

int n, q, m;
ll a[MAXN];
struct node {
    ll sum, lzy_add, lzy_mul;
    node() { sum = 0; lzy_add = 0; lzy_mul = 1; }
} w[MAXN * 4];

// 更新节点u的值
inline void pushup(int u) {
    w[u].sum = (w[u << 1].sum + w[(u << 1) | 1].sum) % m;
}

// 懒标记下放
inline void pushdown(int u, int L, int R) {
    int M = L + R >> 1;
    // 处理乘法懒标记
    if (w[u].lzy_mul != 1) {
        w[u << 1].sum = (w[u << 1].sum * w[u].lzy_mul) % m;
        w[(u << 1) | 1].sum = (w[(u << 1) | 1].sum * w[u].lzy_mul) % m;
        w[u << 1].lzy_mul = (w[u << 1].lzy_mul * w[u].lzy_mul) % m;
        w[(u << 1) | 1].lzy_mul = (w[(u << 1) | 1].lzy_mul * w[u].lzy_mul) % m;
        w[u << 1].lzy_add = (w[u << 1].lzy_add * w[u].lzy_mul) % m;
        w[(u << 1) | 1].lzy_add = (w[(u << 1) | 1].lzy_add * w[u].lzy_mul) % m;
        w[u].lzy_mul = 1;
    }
    // 处理加法懒标记
    if (w[u].lzy_add != 0) {
        w[u << 1].sum = (w[u << 1].sum + (M - L + 1) * w[u].lzy_add) % m;
        w[(u << 1) | 1].sum = (w[(u << 1) | 1].sum + (R - M) * w[u].lzy_add) % m;
        w[u << 1].lzy_add = (w[u << 1].lzy_add + w[u].lzy_add) % m;
        w[(u << 1) | 1].lzy_add = (w[(u << 1) | 1].lzy_add + w[u].lzy_add) % m;
        w[u].lzy_add = 0;
    }
}

// 判断[L,R]是否完全被[l,r]包含
inline bool InRange(int L, int R, int l, int r) {
    return l <= L && R <= r;
}

// 判断[L,R]与[l,r]完全无交集
inline bool OutofRange(int L, int R, int l, int r) {
    return L > r || R < l;
}

// 查询[l,r]的区间和
ll query(int u, int L, int R, int l, int r) {
    if (InRange(L, R, l, r)) return w[u].sum;
    if (OutOfRange(L, R, l, r)) return 0;
    pushdown(u, L, R);
    int M = L + R >> 1;
    return (query(u << 1, L, M, l, r) + query((u << 1) | 1, M + 1, R, l, r)) % m;
}

// 修改[l,r]
void update(int u, int L, int R, int l, int r, int type, ll num) {
    if (InRange(L, R, l, r)) {
        if (type == 1) { // 乘法更新
            w[u].sum = (w[u].sum * num) % m;
            w[u].lzy_mul = (w[u].lzy_mul * num) % m;
            w[u].lzy_add = (w[u].lzy_add * num) % m;
        } else { // 加法更新
            w[u].sum = (w[u].sum + (R - L + 1) * num) % m;
            w[u].lzy_add = (w[u].lzy_add + num) % m;
        }
    } else if (!OutOfRange(L, R, l, r)) {
        pushdown(u, L, R);
        int M = L + R >> 1;
        update(u << 1, L, M, l, r, type, num);
        update((u << 1) | 1, M + 1, R, l, r, type, num);
        pushup(u);
    }
}

int main() {
    scanf("%d%d%d", &n, &q, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    while (q--) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1 || opt == 2) {
            int x, y;
            ll k;
            scanf("%d%d%lld", &x, &y, &k);
            update(1, 1, n, x, y, opt, k);
        } else {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y));
        }
    }
    return 0;
}

关键点说明

1. 懒标记的处理顺序：

   • 先处理乘法懒标记，再处理加法懒标记。
   • 确保乘法懒标记不会影响加法懒标记的计算。

2. 懒标记的合并：

   • 在 pushdown 中，将懒标记传递到子节点时，需要正确处理乘法和加法的合并。

3. 区间更新的递归处理：

   • 在 update 函数中，递归地更新左右子树，并在更新完成后调用 pushup 更新父节点。

通过以上修改，代码可以正确处理区间加法和乘法更新以及区间查询操作。