109徐守佳

用户名：dotcpp0787174

访问量：1104

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	878
经　　验	3559
参赛次数	3
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

二分直接用现成的STL:lower_bound/upper_bound(新增手写二分)
浏览：60

[信息学奥赛一本通T1247-河中跳房子] 二分答案
浏览：52

[信息学奥赛一本通T1240-查找最接近的元素] 依旧是STL
浏览：38

你可能喜欢

[信息学奥赛一本通T1551-维护序列] 线段树

　　作者: 109徐守佳　　　　发表时间：2024-10-15 15:33:34 浏览：15　|　评论：0　

原题链接：信息学奥赛一本通T1551-维护序列

# 巧妙的把懒标记传给子节点
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define PII pair<int,int>
using namespace std;
const int N =  1 *1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m,p,a[N];
struct node{
    int l,r;
    int sum,add,mul;
}tr[N*4];
void eval(node &root,int add,int mul){
    root.sum = ((LL)root.sum * mul + (LL)(root.r - root.l + 1) * add) % p;
    root.mul = (LL)root.mul * mul % p;
    root.add = ((LL)root.add * mul + add) % p;
}
void pushup(int u){
    tr[u].sum = (tr[u<<1].sum + tr[u<<1|1].sum) % p;
}
void pushdown(int u){
    eval(tr[u<<1],tr[u].add,tr[u].mul);
    eval(tr[u<<1|1],tr[u].add,tr[u].mul);
    tr[u].add = 0 , tr[u].mul = 1;
}
void build(int u,int l,int r){
    if(l==r) tr[u] = {l,r,a[r],0,1};
    else{
        tr[u] = {l,r,0,0,1};
        int mid = l + r >> 1;
        build(u<<1,l,mid) , build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int add,int mul){
    if(tr[u].l >= l && tr[u].r <= r) eval(tr[u],add,mul);
    else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u<<1,l,r,add,mul);
        if(r > mid) modify(u<<1|1,l,r,add,mul);
        pushup(u);
    }
}
int query(int u,int l,int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if(l <= mid) sum = query(u<<1,l,r);
    if(r > mid) sum = (sum + query(u<<1|1,l,r)) % p; 
    return sum;
}
void solve(){
    cin >> n >> p;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1,1,n);
    cin >> m;
    while (m--){
        int op,l,r,x;
        cin >> op >> l >> r;
        if(op == 3){
            cout<<query(1,l,r)<<endl;
        }
        else{
            cin>>x;
            if(op == 1) modify(1,l,r,0,x);
            if(op == 2) modify(1,l,r,x,1);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.15 00:15:07
 */
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

宏定义（C语言代码）

C二级辅导-温度转换（C语言代码）

汽水瓶（C++代码）

整人!!

[信息学奥赛一本通T1551-维护序列] 线段树

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C二级辅导-同因查找（C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

【绝对值排序】（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-字符串比较（C++代码）

三角形（C++代码）记忆化搜索

1157题解

剪刀石头布（C++代码）

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

宏定义（C语言代码）

C二级辅导-温度转换 （C语言代码）

汽水瓶 （C++代码）

整人!!

[信息学奥赛一本通T1551-维护序列] 线段树

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C二级辅导-同因查找 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

【绝对值排序】 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-字符串比较 （C++代码）

三角形 （C++代码）记忆化搜索

1157题解

剪刀石头布 （C++代码）

C二级辅导-温度转换（C语言代码）

汽水瓶（C++代码）

　　评论区

C二级辅导-同因查找（C语言代码）

【绝对值排序】（C语言代码）

WU-字符串比较（C++代码）

三角形（C++代码）记忆化搜索

剪刀石头布（C++代码）