Alfred_zhc @ 2023-09-24 00:07:59
对付剩下的超时和溢出我实在弄不懂 只求拿个60就行:(
#include <bits/stdc++.h>
using namespace std;
int const M=2e6+7;
struct node {
// 线段树
int n;
int l, r;
int az;// 啊这,懒标记,没错,l az y
}nds[M*2];
int a[M];
int n, q;
int read() {
// 快读
int x=0, f=1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void build(int l, int r, int d) {
// 建树
if(l==r) {
nds[d] = {a[l], l, r, 0};
return;
}
int mid = (l+r)/2;
build(l, mid, d*2);
build(mid+1, r, d*2+1);
nds[d] = {max(nds[d*2].n, nds[d*2+1].n), l, r, 0};
}
void modify(int dl, int dr, int l, int r, int x, int d) {
// 替换
if(l==r) {
nds[d].n=x;
return;
}
int mid = (l+r)/2;
if(nds[d].az) {
// 下放标记
nds[d*2].n+=nds[d].az;
nds[d*2].az+=nds[d].az;
nds[d*2+1].n+=nds[d].az;
nds[d*2+1].az+=nds[d].az;
nds[d].az=0;
}
if(mid>=dl) modify(dl, dr, l, mid, x, d*2);
if(mid+1<=dr) modify(dl, dr, mid+1, r, x, d*2+1);
nds[d].n=max(nds[d*2].n, nds[d*2+1].n);
}
void plusf(int dl, int dr, int l, int r, int x, int d) {
// 齐增 懒标记
if(l>=dl&&r<=dr) {
nds[d].az+=x;
nds[d].n+=x;
return;
}
int mid = (l+r)/2;
if(nds[d].az) {
// 下放标记
nds[d*2].n+=nds[d].az;
nds[d*2].az+=nds[d].az;
nds[d*2+1].n+=nds[d].az;
nds[d*2+1].az+=nds[d].az;
nds[d].az=0;
}
if(mid>=dl) plusf(dl, dr, l, mid, x, d*2);
if(mid+1<=dr) plusf(dl, dr, mid+1, r, x, d*2+1);
nds[d].n=max(nds[d*2].n, nds[d*2+1].n);
}
int query(int dl, int dr, int l, int r, int d) {
// 求和
if(nds[d].az) {
// 下放标记
nds[d*2].n+=nds[d].az;
nds[d*2].az+=nds[d].az;
nds[d*2+1].n+=nds[d].az;
nds[d*2+1].az+=nds[d].az;
nds[d].az=0;
}
if(l>=dl&&r<=dr) return nds[d].n;
int mid = (l+r)/2;
int gl=INT_MIN, gr=INT_MIN;
if(mid>=dl) gl = query(dl, dr, l, mid, d*2);
if(mid+1<=dr) gr = query(dl, dr, mid+1, r, d*2+1);
return max(gl, gr);
}
int main() {
n=read();
q=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1, n, 1);
// for(int i=1;i<=n*2+1;i++) {
// cout<<nds[i].n<<' ';
// }
int op, a, b, c;
while(q--)
{
op=read();
if(op==1) {
a=read();b=read();c=read();
modify(a, b, 1, n, c, 1);
}
else if(op==2) {
// 同加
a=read();b=read();c=read();
plusf(a, b, 1, n, c, 1);
}
else {
// 区间最大
a=read();b=read();
cout<<query(a, b, 1, n, 1)<<'\n';
}
}
return 0;
}
//6 6
//1 1 4 5 1 4
//3 1 3
//3 2 5
//3 5 6
想知道到底是什么问题,或许和数据范围有关?求列位大佬解惑
看了一下,我的懒标记加的有些非主流,麻烦列位大佬的眼睛了故意的