CEFqwq @ 2024-03-23 13:53:22
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define mxn 200005
struct node{
int l, r, vl, lzy;
}tr[mxn << 2 | 3];
int a[mxn], n, q;
int ls(int u){
return u << 1;
}
int rs(int u){
return u << 1 | 1;
}
int glz(int u, int k){
tr[u].lzy += k;
}
int gv(int u, int k){
tr[u].vl += k;
}
int md(int l, int r){
return (l + r) >> 1;
}
void pup(int u){
tr[u].vl = tr[ls(u)].vl + tr[rs(u)].vl;
}
void build(int u, int l, int r){
tr[u].l = l;
tr[u].r = r;
if (l == r){
tr[u].vl = a[l];
return;
}
int mid = md(l, r);
build(ls(u), l, mid);
build(rs(u), mid + 1, r);
pup(u);
}
bool inr(int l, int r, int ql, int qr){
return (ql <= l && qr >= r);
}
bool otr(int l, int r, int ql, int qr){
return (ql > r || qr < l);
}
void pdn(int u, int l, int r){
int mid = md(l, r);
glz(ls(u), tr[u].lzy);
gv(ls(u), tr[u].lzy * (mid - l + 1));
glz(rs(u), tr[u].lzy);
gv(rs(u), tr[u].lzy * (r - mid));
tr[u].lzy = 0;
}
void upd(int u, int ql, int qr, int x){
if (inr(tr[u].l, tr[u].r, ql, qr)){
glz(u, x);
gv(u, x * (tr[u].r - tr[u].l + 1));
return;
}
if (otr(tr[u].l, tr[u].r, ql, qr))
return;
pdn(u, ql, qr);
int mid = md(tr[u].l, tr[u].r);
if (ql <= mid)
upd(ls(u), ql, qr, x);
if (qr > mid)
upd(rs(u), ql, qr, x);
}
int qry(int u, int ql, int qr){
int res = 0;
if (inr(tr[u].l, tr[u].r, ql, qr))
return tr[u].vl;
if (otr(tr[u].l, tr[u].r, ql, qr))
return 0;
pdn(u, ql, qr);
int mid = md(tr[u].l, tr[u].r);
if (ql <= mid)
res += qry(ls(u), ql, qr);
if (qr > mid)
res += qry(rs(u), ql, qr);
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (q--){
int op;
cin >> op;
if (op == 1){
int l, r, x;
cin >> l >> r >> x;
upd(1, l, r, x);
}else{
int l, r;
cin >> l >> r;
cout << qry(1, l, r) << "\n";
}
}
}我下载了数据点1，本地运行和答案结果完全相同，但是洛谷RE。
by xhgua @ 2024-03-23 13:58:30
把没有返回值的函数改成 void 就行了。不返回开了 O2 会 RE。
by CEFqwq @ 2024-03-23 14:01:48
@xhgua 是 Linux 特有的吗（
拜谢 xhgua
by xhgua @ 2024-03-23 14:03:15
@爱肝大模拟的tlxjy 未定义行为，不开 O2 大概率没事。
by CEFqwq @ 2024-03-23 14:04:42
@xhgua 我本地开了 O2 没事，洛谷不开 O2 出事/yun
by xhgua @ 2024-03-23 14:08:48
@爱肝大模拟的tlxjy 可能版本比较低，我本地开了 O2 会挂
by CEFqwq @ 2024-03-23 14:09:47
@xhgua 你是什么版本……
我 Dev-C++5.11 ISOC++11 O2
by xhgua @ 2024-03-23 14:11:53
@爱肝大模拟的tlxjy 很难绷，我版本比你还低... 那有点奇怪...
by CEFqwq @ 2024-03-23 14:23:23
@xhgua 好像我还有哪里 UB 了/yun/yun/yun
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define mxn 200005
struct node{
int l, r, vl, lzy;
}tr[mxn << 2 | 3];
int a[mxn], n, q;
int ls(int u){
return u << 1;
}
int rs(int u){
return u << 1 | 1;
}
void glz(int u, int k){
tr[u].lzy += k;
}
void gv(int u, int k){
tr[u].vl += k;
}
int md(int l, int r){
return (l + r) >> 1;
}
void pup(int u){
tr[u].vl = tr[ls(u)].vl + tr[rs(u)].vl;
}
void build(int u, int l, int r){
tr[u].l = l;
tr[u].r = r;
if (l == r){
tr[u].vl = a[l];
return;
}
int mid = md(l, r);
build(ls(u), l, mid);
build(rs(u), mid + 1, r);
pup(u);
}
bool inr(int l, int r, int ql, int qr){
return (ql <= l && qr >= r);
}
bool otr(int l, int r, int ql, int qr){
return (ql > r || qr < l);
}
void pdn(int u, int l, int r){
int mid = md(l, r);
glz(ls(u), tr[u].lzy);
gv(ls(u), tr[u].lzy * (mid - l + 1));
glz(rs(u), tr[u].lzy);
gv(rs(u), tr[u].lzy * (r - (mid + 1) + 1));
tr[u].lzy = 0;
}
void upd(int u, int ql, int qr, int x){
if (inr(tr[u].l, tr[u].r, ql, qr)){
glz(u, x);
gv(u, x * (tr[u].r - tr[u].l + 1));
return;
}
if (otr(tr[u].l, tr[u].r, ql, qr))
return;
pdn(u, ql, qr);
int mid = md(tr[u].l, tr[u].r);
upd(ls(u), ql, qr, x);
upd(rs(u), ql, qr, x);
}
int qry(int u, int ql, int qr){
int res = 0;
if (inr(tr[u].l, tr[u].r, ql, qr))
return tr[u].vl;
if (otr(tr[u].l, tr[u].r, ql, qr))
return 0;
pdn(u, ql, qr);
int mid = md(tr[u].l, tr[u].r);
res += (qry(ls(u), ql, qr) + qry(rs(u), ql, qr));
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (q--){
int op;
cin >> op;
if (op == 1){
int l, r, x;
cin >> l >> r >> x;
upd(1, l, r, x);
}else{
int l, r;
cin >> l >> r;
cout << qry(1, l, r) << "\n";
}
// for (int i = 1; i <= n; i++)
// cout << qry(1, i, i) << " ";
// cout << "\n";
}
}by 094913a @ 2024-03-23 14:56:18
u7y