本题是线段树板子题,简单维护一下即可
2024-07-10 15:52:53
发布于:浙江
107阅读
0回复
0点赞
本题是线段树板子题,简单维护一下即可
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100010;
struct Node{
LL sum;
LL tag;
}seg[N * 4];
int n, m;
LL a[N];
void pushup(int u){
seg[u].sum = seg[u << 1].sum + seg[u << 1 | 1].sum;
}
void pushdown(int u, int l, int r){
LL &x = seg[u].tag;
seg[u << 1].tag += x;
seg[u << 1 | 1].tag += x;
int mid = l + r >> 1;
seg[u << 1].sum += 1ll *(mid - l + 1) * x;
seg[u << 1 | 1].sum += 1ll * (r - (mid + 1) + 1) * x;
seg[u].tag = 0;//x = 0;
}
void build(int u, int l, int r){
if(l == r){
seg[u].sum = a[l];
seg[u].tag = 0;
return;
}
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 ql, int qr, int x){
if(l == ql && r == qr){
seg[u].tag += x;
seg[u].sum += 1ll * (r - l + 1) * x;
return;
}
pushdown(u, l, r);
int mid = l + r >> 1;
if(qr <= mid) modify(u << 1, l, mid, ql, qr, x);
else if(ql > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, x);
else{
modify(u << 1, l, mid, ql, mid, x);
modify(u << 1 | 1, mid + 1, r, mid + 1, qr, x);
}
pushup(u);
}
LL query(int u, int l, int r, int ql, int qr){
if(l == ql && r == qr){
return seg[u].sum;
}
pushdown(u, l, r);
int mid = l + r >> 1;
if(qr <= mid) return query(u << 1, l, mid, ql, qr);
else if(ql > mid) return query(u << 1 | 1, mid + 1, r, ql, qr);
else{
return query(u << 1, l, mid, ql, mid) + query(u << 1 | 1, mid + 1, r, mid + 1, qr);
}
// pushup(u);
}
int main(){
int a, b; cin >> a >> b;
build(1, 1, 1000);
modify(1, 1, 1000, 1, 1, a);
modify(1, 1, 1000, 2, 2, b);
cout << query(1, 1, 1000, 1, 2) << endl;
}
全部评论 2
666
2025-03-12 来自 江西
0Vocal
2024-10-10 来自 广东
0
有帮助,赞一个