acwing-个简单的整数问题2(线段树+懒惰标记)「建议收藏」

全栈程序员-站长 • 2022年8月8日下午1:00 • 未分类 • 阅读 7

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

原题链接
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。

输入格式
第一行两个整数 N,M。

第二行 N 个整数 A[i]。

接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。

输出格式
对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤109
输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

题解
线段树模板

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
struct Node{ 
   
    int l,r;
    ll v;
    ll add;    //懒惰标记,保存当前节点以及子节点应该加上的值
}tr[N * 4];
int a[N];
void push_up(int u){ 
   
    tr[u].v = tr[left(u)].v + (tr[left(u)].r - tr[left(u)].l + 1) * tr[left(u)].add
     + tr[right(u)].v + (tr[right(u)].r - tr[right(u)].l + 1) * tr[right(u)].add;
}
void push_down(int u){ 
   
    if(tr[u].add){ 
   
        tr[u].v += (tr[u].r - tr[u].l + 1) * tr[u].add;
        tr[left(u)].add += tr[u].add;
        tr[right(u)].add += tr[u].add;
        tr[u].add = 0;
    }
}
void build(int l,int r,int u){ 
   
    if(l == r){ 
   
        tr[u] = { 
   l,r,a[l],0};
        return;
    }
    else{ 
   
        tr[u] = { 
   l,r,0,0};
        int mid = (l + r) >> 1;
        build(l, mid, left(u));
        build(mid + 1, r, right(u));
        push_up(u);
    }
}
ll query(int l,int r,int u){ 
   
    push_down(u);
    if(tr[u].l >= l && tr[u].r <= r){ 
   
        return tr[u].v;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll sum = 0;
    if(l <= mid)sum += query(l,r,left(u));
    if(r > mid)sum += query(l,r,right(u));
    return sum;
}
void modify(int l,int r,int x,int u){ 
   
    if(tr[u].l >= l && tr[u].r <= r)tr[u].add += x;
    else{ 
   
        push_down(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid)modify(l,r,x,left(u));
        if(r > mid)modify(l,r,x,right(u));
        push_up(u);     //修改了值就要push_up
    }
}
void update(int x,int y,int u){ 
   
    if(tr[u].l == x && tr[u].r == x)tr[u].v = y;
    else{ 
   
        push_down(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid)update(x,y,left(u));
        else update(x,y,right(u));
        push_up(u);
    }
}
int main(){ 
   
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n;i ++){ 
   
        cin>>a[i];
    }
    build(1,n,1);
    char c;
    int l,r,a;
    for(int i = 0;i < m;i ++){ 
   
        cin>>c>>l>>r;
        if(c == 'Q'){ 
   
            cout<<query(l,r,1)<<endl;
        }else if(c == 'C'){ 
   
            cin>>a;
            modify(l,r,a,1);
        }
    }
    return 0;
}