社区讨论
全部RE,佬们可以帮我看看吗
P2357守墓人参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2v6o2j
- 此快照首次捕获于
- 2023/10/23 20:18 2 年前
- 此快照最后确认于
- 2023/10/23 20:18 2 年前
CPP
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 5e6 + 10;
typedef long long ll;
ll n , m , a[N];
struct tree{
ll l , r , sum , lazy;
}tr[4 * N];
void pushup(ll u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(ll u){
if(tr[u].lazy){
tr[u << 1].lazy += tr[u].lazy , tr[u << 1 | 1].lazy += tr[u].lazy;
tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].lazy , tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].lazy;
tr[u].lazy = 0;
}
}
void build(ll u,ll l,ll r){
tr[u].lazy = 0;
if(l == r) tr[u] = { l , r , a[r] , 0};
else{
tr[u] = {l , r};
ll mid = l + r >> 1;
build(u << 1 , 1 , mid) , build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
}
void modify(ll u , ll l , ll r , ll v){
if(l <= tr[u].l && tr[u].r <= r){
tr[u].sum += (tr[u].r - tr[u].l + 1) * v;
tr[u].lazy += v;
}
else{
pushdown(u);
ll mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1 , l , r , v);
if(r > mid) modify(u << 1 | 1 , l , r , v);
pushup(u);
}
}
ll query(ll u,ll l,ll r){
if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
else{
ll mid = tr[u].l + tr[u].r >> 1;
ll tot = 0;
if(l <= mid) tot = query(u << 1 , l , r);
if(r > mid) tot += query(u << 1 | 1 , l , r);
return tot;
}
}
int main()
{
cin >> n >> m;
for (int i = 1 ; i <= n ; ++i) cin >> a[i];
build(1 , 1 , n);
while(m--)
{
int op , l , r , c , k;
cin >> op;
if(op == 1){
cin >> l >> r >> c;
modify(1 , l , r , c);
}else if(op == 2){
cin >> k;
modify(1 , 1 , 1 , k);
}else if(op == 3){
cin >> k;
modify(1 , 1 , 1 , -k);
}else if(op == 4){
cin >> l >> r;
cout << query(1 , l , r) << endl;
}else {
cout << query(1 , 1 , 1) << endl;
}
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...