【赏关注】20pts，#1 #3 AC求调 qwq

hanyuchen2019 @ 2023-01-15 14:39:07

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
    int x_=0,f_=1;char c_=getchar();
    while(!isdigit(c_)){if(c_=='-') f_=-1;c_=getchar();}
    while(isdigit(c_))x_=x_*10+(c_^48),c_=getchar();
    return x_*f_;
}
struct node{ll a,add,cz;}tree[4000005];
void pushup(int u)
{
    tree[u].a=max(tree[u*2].a,tree[u*2+1].a);
}
void build(int u,int l,int r)
{
    tree[u].cz=LLONG_MIN;
    if(l==r)
    {
        tree[u].a=read();
        return;
    }
    int m=l+r>>1;
    build(u*2,l,m);
    build(u*2+1,m+1,r);
    pushup(u);
}
void pushdown(int u)
{
    if(tree[u].cz!=LLONG_MIN)
    {
        tree[u*2].cz=tree[u*2+1].cz=tree[u].cz;
        tree[u*2].a=tree[u*2+1].a=tree[u].cz;
        tree[u*2].add=tree[u*2+1].add=0;
    }
    tree[u*2].add+=tree[u].add;
    tree[u*2+1].add+=tree[u].add;
    tree[u*2].a+=tree[u].add;
    tree[u*2+1].a+=tree[u].add;

    tree[u].add=0;
    tree[u].cz=LLONG_MIN;
}
void update1(int L,int R,int x,int l,int r,int u)
{
    if(L<=l&&r<=R)
    {
        tree[u].a=x;
        tree[u].cz=x;
        return;
    }
    int m=l+r>>1;
    if(L<=m)update1(L,R,x,l,m,u*2);
    if(m<R)update1(L,R,x,m+1,r,u*2+1);
    pushdown(u);
    pushup(u);
}
void update2(int L,int R,int x,int l,int r,int u)
{
    if(L<=l&&r<=R)
    {
        tree[u].a+=x;
        tree[u].add+=x;
        return;
    }
    int m=l+r>>1;
    if(L<=m)update2(L,R,x,l,m,u*2);
    if(m<R)update2(L,R,x,m+1,r,u*2+1);
    pushdown(u);
    pushup(u);
}
ll query(int L,int R,int l,int r,int u)
{
    ll ans=LLONG_MIN;
    if(L<=l&&r<=R)
    {
        return tree[u].a;
    }
    int m=l+r>>1;
    if(L<=m)ans=max(query(L,R,l,m,u*2),ans);
    if(m<R)ans=max(query(L,R,m+1,r,u*2+1),ans);
    return ans;
}
int main()
{
    int n=read(),q=read();
    build(1,1,n);
    int op,l,r,x;
    while(q--)
    {
        op=read(),l=read(),r=read();
        if(op==1)
        {
            x=read();
            update1(l,r,x,1,n,1);
        }
        else if(op==2)
        {
            x=read();
            update2(l,r,x,1,n,1);
        }
        else
        {
            printf("%lld\n",query(l,r,1,n,1));
        }
    }
    return 0;
}

by AThls123 @ 2023-01-15 14:51:26

@hanyuchen2019 你的 pushdown 位置放的有问题

by hanyuchen2019 @ 2023-01-15 14:53:09

@AThls123 能说具体一点吗？qwq

by AThls123 @ 2023-01-15 14:54:52

应该放在m 的前面 。 还有 query 的时候也要pushdown

by AThls123 @ 2023-01-15 14:56:36

@hanyuchen2019 像这样

void update2(int L,int R,int x,int l,int r,int u){
  if(L<=l&&r<=R){
      tree[u].a+=x;
      tree[u].add+=x;
      return;
    }
  int m=l+r>>1;
  pushdown(u);
  if(L<=m)update2(L,R,x,l,m,u*2);
  if(m<R)update2(L,R,x,m+1,r,u*2+1);
  pushup(u);
}
ll query(int L,int R,int l,int r,int u){
  ll ans=LLONG_MIN;
  if(L<=l&&r<=R) {
    return tree[u].a;
  }
  int m=l+r>>1;
  pushdown(u);
  if(L<=m)ans=max(query(L,R,l,m,u*2),ans);
  if(m<R)ans=max(query(L,R,m+1,r,u*2+1),ans);
  return ans;
}

by AThls123 @ 2023-01-15 14:58:31

@hanyuchen2019 A 了

by AThls123 @ 2023-01-15 15:06:14

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
  int x_=0,f_=1;char c_=getchar();
  while(!isdigit(c_)){if(c_=='-') f_=-1;c_=getchar();}
  while(isdigit(c_))x_=x_*10+(c_^48),c_=getchar();
  return x_*f_;
}
struct node{
  ll a,add,cz;
}tree[4000005];
void pushup(int u){
  tree[u].a=max(tree[u*2].a,tree[u*2+1].a);
}
void build(int u,int l,int r)
{
    tree[u].cz=LLONG_MIN;
    if(l==r) {
        tree[u].a=read();
        return;
    }
    int m=l+r>>1;
    build(u*2,l,m);
    build(u*2+1,m+1,r);
    pushup(u);
}
void pushdown(int u){
  if(tree[u].cz!=LLONG_MIN){
    tree[u*2].cz=tree[u*2+1].cz=tree[u].cz;
    tree[u*2].a=tree[u*2+1].a=tree[u].cz+tree[u].add;
    tree[u*2].add=tree[u*2+1].add=tree[u].add;
  }
  else {
    tree[u*2].add+=tree[u].add;
    tree[u*2+1].add+=tree[u].add;
    tree[u*2].a+=tree[u].add;
    tree[u*2+1].a+=tree[u].add;
  }
  tree[u].add=0;
  tree[u].cz=LLONG_MIN;
}
void update1(int L,int R,int x,int l,int r,int u)
{
  if(L<=l&&r<=R) {
      tree[u].a=x;
      tree[u].cz=x;
      tree[u].add=0;
      return;
    }
  int m=l+r>>1;
  pushdown(u);
  if(L<=m)update1(L,R,x,l,m,u*2);
  if(m<R)update1(L,R,x,m+1,r,u*2+1);
  pushup(u);
}
void update2(int L,int R,int x,int l,int r,int u){
  if(L<=l&&r<=R){
    tree[u].a+=x;
    tree[u].add+=x;
    return;
  }
  int m=l+r>>1;
  pushdown(u);
  if(L<=m)update2(L,R,x,l,m,u*2);
  if(m<R)update2(L,R,x,m+1,r,u*2+1);
  pushup(u);
}
ll query(int L,int R,int l,int r,int u){
  ll ans=LLONG_MIN;
  if(L<=l&&r<=R) {
    return tree[u].a;
  }
  int m=l+r>>1;
  pushdown(u);
  if(L<=m)ans=max(query(L,R,l,m,u*2),ans);
  if(m<R)ans=max(query(L,R,m+1,r,u*2+1),ans);
  return ans;
}
int main(){
  int n=read(),q=read();
  build(1,1,n);
  int op,l,r,x;
  while(q--) {
    op=read(),l=read(),r=read();
    if(op==1) {
      x=read();
      update1(l,r,x,1,n,1);
    }
    else if(op==2) {
      x=read();
      update2(l,r,x,1,n,1);
    }
    else {
      printf("%lld\n",query(l,r,1,n,1));
    }
  }
  return 0;
}