cat_lover1 @ 2023-11-16 00:25:26
思路几乎与第一篇题解相同，得40分，后6个点都TLE了
#define max(a,b) ((a)>(b)?(a):(b))
#define mid l+(r-l>>1)
#define lc h<<1
#define rc h<<1|1
#define IN x<=l&&r<=y
#define OUT (y<l||r<x)
#define LL long long
#define nul 1000000001
tr[4000001],t1[4000001],t2[4000001],n,q,op,x,y,z;
void make_tag1(h,x){
tr[h]=t1[h]=x,t2[h]=0;
}
void make_tag2(h,x){
t2[h]+=x,tr[h]+=x;
t1[h]!=nul&&(t1[h]+=x);
}
void pushup(h){tr[h]=max(tr[lc],tr[rc]);}
void pushdown(h){
if(t1[h]!=nul){
make_tag1(lc,t1[h]),make_tag1(rc,t1[h]);
t1[h]=nul;
}
else if(t2[h]){
make_tag2(lc,t2[h]),make_tag2(rc,t2[h]);
t2[h]=0;
}
}
void build(h,l,r){
if(l^r){
build(lc,l,mid),
build(rc,mid+1,r);
pushup(h);
}
else scanf("%d",tr+h);
}
qry(h,l,r){
//printf("%d: %d %d %d %d %d\n",op,h,l,r,x,y);
if(IN)return tr[h];
if(!OUT){
pushdown(h);
return max(qry(lc,l,mid),qry(rc,mid+1,r));
}
return -nul;
}
void upd(h,l,r){
//printf("%d: %d %d %d %d %d %d\n",op,h,l,r,x,y,z);
if(IN)op==1?make_tag1(h,z):(make_tag2(h,z));
else if(!OUT)pushdown(h),upd(lc,l,mid),upd(rc,mid+1,r),pushup(h);
}
void init(){
for(int i=0;i<4000001;++i)t1[i]=nul;
scanf("%d%d",&n,&q);
build(1,1,n);
}
void solve(){
scanf("%d%d%d",&op,&x,&y);
if(op^3)scanf("%d",&z),upd(1,1,n);
else printf("%d\n",qry(1,1,n));
}
main(){
for(init();q--;)solve();
}
by Buried_Dream @ 2023-11-16 06:22:00
这是什么语言，为啥不用定义类型qwq
by Twiter_ln @ 2023-11-16 07:44:20
@cz_awa 同问
by Ryan_jiang07 @ 2023-11-16 07:59:45
同问
by 5t0_0r2 @ 2023-11-16 08:35:15
@cz_awa 有你这么建树的吗（还边读入边建）……
by cat_lover1 @ 2023-11-16 09:18:02
@Buried_Dream @Twiter_ln @Ryan_jiang07 这是C语言 @5t0_0r2 好，我改改
by 5t0_0r2 @ 2023-11-16 09:26:32
@cz_awa 还有你的 upd 传了 op 的参数吗
by 5t0_0r2 @ 2023-11-16 09:29:35
@cz_awa 还有你的 nul 小了（你加两次 10^9）不就超过了么
by Buried_Dream @ 2023-11-16 09:30:51
@5t0_0r2 为什么不能边读边建
by 5t0_0r2 @ 2023-11-16 09:31:32
@Buried_Dream 容易出 bug
by 5t0_0r2 @ 2023-11-16 09:32:01
@cz_awa 或者可参考这一份代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9,INF = 1e18,ROOT = 1;
int a[N];
struct seg_tree{
struct node {
int val,add,change;
} tree[N << 2];
bool in_range(int l,int r,int now_l,int now_r){
return l <= now_l && now_r <= r;
}
bool out_range(int l,int r,int now_l,int now_r){
return now_r < l || now_l > r;
}
void push_up(int root){
int lchild = root * 2,rchild = root * 2 + 1;
tree[root].val = max(tree[lchild].val,tree[rchild].val);
}
void make_tag(int root,int x,int type){
if(type == 1){
tree[root].add = 0;
tree[root].change = x;
tree[root].val = x;
}
else{
if(tree[root].change == INF)
tree[root].add += x;
else
tree[root].change += x;
tree[root].val += x;
}
}
void push_down(int root){
int lchild = root * 2,rchild = root * 2 + 1;
if(tree[root].change == INF){
make_tag(lchild,tree[root].add,2);
make_tag(rchild,tree[root].add,2);
tree[root].add = 0;
}
else{
make_tag(lchild,tree[root].change,1);
make_tag(rchild,tree[root].change,1);
tree[root].change = INF;
}
}
void build(int l,int r,int root) {
tree[root].change = INF;
if(l == r) {
tree[root].val = a[l];
return;
}
int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
build(l,mid,lchild);
build(mid + 1,r,rchild);
push_up(root);
}
void update(int l,int r,int now_l,int now_r,int root,int c,int type) {
if(in_range(l,r,now_l,now_r)) {
make_tag(root,c,type);
return;
}
else if(!out_range(l,r,now_l,now_r)){
int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
push_down(root);
update(l,r,mid + 1,now_r,rchild,c,type);
update(l,r,now_l,mid,lchild,c,type);
push_up(root);
}
return;
}
int getmax(int l, int r, int now_l, int now_r, int root) {
int mid = (now_l + now_r) / 2,lchild = root * 2,rchild = root * 2 + 1;
if(in_range(l,r,now_l,now_r))
return tree[root].val;
else if(!out_range(l,r,now_l,now_r)){
push_down(root);
return max(getmax(l,r,now_l,mid,lchild),getmax(l,r,mid + 1,now_r,rchild));
}
else
return -INF;
}
} seg;
int n,m;
int op,l,r,k;
signed main() {
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
seg.build(1,n,ROOT);
for(int i = 1; i <= m; i++) {
scanf("%lld", &op);
if(op == 1 || op == 2){
scanf("%lld%lld%lld" ,&l, &r, &k);
seg.update(l,r,1,n,ROOT,k,op);
}
else{
scanf("%lld%lld", &l, &r);
printf("%lld\n",seg.getmax(l,r,1,n,1));
}
}
}