50pts球调，应该不是负无穷问题

P1253 扶苏的问题

cengzh @ 2024-10-15 18:59:24

rt

# include <stdio.h>
# include <limits.h>
# include <iostream>

using namespace std;

long long Tree[1000005*4];
long long tag1[1000005*4];
long long tag2[1000005*4];
long long arr[1000005];
int n,m;

void add_tag1(int node,int l,int r,int k)
{
    tag1[node] += k;
    Tree[node] += k;
    return ;
}

void add_tag2(int node,int l,int r,int k)
{
    tag1[node] = 0;
    tag2[node] = k;
    Tree[node] = k;
    return ;
}

void push_down(int node,int l,int r)
{
    if (tag2[node] != LLONG_MAX)
    {
        int mid = (l + r) / 2;
        add_tag2(node*2,l,mid,tag2[node]);
        add_tag2(node*2+1,mid+1,r,tag2[node]);
        tag2[node] = LLONG_MAX;     
    }
    if (tag1[node] != 0)
    {
        int mid = (l + r) / 2;
        add_tag1(node*2,l,mid,tag1[node]);
        add_tag1(node*2+1,mid+1,r,tag1[node]);
        tag1[node] = 0;
    }
    return ;
}

void Build(int node,int l,int r)
{
    tag2[node] = LLONG_MAX;
    if (l == r)
    {
        Tree[node] = arr[l];
        return ;
    }

    int mid = (l+r) /2;
    Build(node*2,l,mid);
    Build(node*2+1,mid+1,r);

    Tree[node] = max(Tree[node*2],Tree[node*2+1]);

    return  ;
}

void Update1(int node,int l,int r,int tl,int tr,int w)
{
    if (tl <= l && tr >= r)
    {
        add_tag1(node,l,r,w);
        return ;
    }

    push_down(node,l,r);
    int mid = (l+r) / 2;

    if (mid  >= tl)
    {
        Update1(node*2,l,mid,tl,tr,w);
    }
    if (mid < tr)
    {
        Update1(node*2+1,mid+1,r,tl,tr,w);
    }

    Tree[node] = max(Tree[node*2],Tree[node*2+1]);

    return ;
}

void Update2(int node,int l,int r,int tl,int tr,int w)
{
    if (tl <= l && tr >= r)
    {
        add_tag2(node,l,r,w);
        return ;
    }

    push_down(node,l,r);
    int mid = (l+r) / 2;

    if (mid >= tl)
    {
        Update2(node*2,l,mid,tl,tr,w);
    }
    if (mid < tr)
    {
        Update2(node*2+1,mid+1,r,tl,tr,w);
    }

    Tree[node] = max(Tree[node*2],Tree[node*2+1]);

    return ;
}

long long Query(int node,int l,int r,int tl,int tr)
{
    if (tl <= l && tr >= r)
    {
        return Tree[node];
    }

    int mid = (l+r)/2;

    push_down(node,l,r);
    long long res=LLONG_MIN;

    if (mid  >= tl)
    {
        res = max(Query(node*2,l,mid,tl,tr),res);
    }
    if (mid < tr)
    {
        res = max(Query(node*2+1,mid+1,r,tl,tr),res);
    }

    return res;
}

int main (void)
{

    scanf ("%d %d",&n,&m);

    for (int i=1;i<=n;i++)
    {
        scanf ("%lld",&arr[i]);
    }

    Build(1,1,n);

    for (int i=0;i<m;i++)
    {
        int opt,x,y;
        scanf ("%d %d %d",&opt,&x,&y);
        if (opt == 1)
        {
            int k;
            scanf ("%d",&k);
            Update2(1,1,n,x,y,k);
        }
        else if (opt == 2)
        {
            int k;
            scanf ("%d",&k);
            Update1(1,1,n,x,y,k);           
        }
        else
        {
            printf ("%lld\n",Query(1,1,n,x,y));
        }    
    }

    return 0;
}

C语言且码风良好（？

by liuzhengtao @ 2024-10-21 22:56:03

我去老铁，咱俩的代码几乎一摸一样啊，我也50points，WA50分，现在你搞懂了吗，请问能帮帮我吗？

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
const int maxN=1e6+10,inf=0x3f3f3f3f3f3f3f3f;
int ma[maxN*4],add[maxN*4],add2[maxN*4];
int a[maxN],n,m;
void pushUp(int k)
{
    ma[k]=max(ma[k*2],ma[k*2+1]);
}
void build(int k,int L,int R)
{
    if(L==R){
        ma[k]=a[L],add2[k]=inf;
        return;
    } 
    int mid=L+R>>1;
    build(k*2,L,mid);
    build(k*2+1,mid+1,R);
    pushUp(k); 
    add2[k]=inf;//啊啊啊啊啊，别忘记加 
}  
void change(int k,int L,int R,int v)
{
    ma[k]+=v;
    add[k]+=v; 
}
void change2(int k,int L,int R,int v)
{
    ma[k]=v;
    add[k]=0;
    add2[k]=v;
}
void pushdown(int k,int L,int R)
{
    if(add2[k]!=inf)
    {
        int mid=L+R>>1;
        change2(k*2,L,mid,add2[k]);
        change2(k*2+1,mid+1,R,add2[k]);
        add2[k]=inf;        
    }
    if(add[k]!=0)
    {
        int mid=L+R>>1;
        change(k*2,L,mid,add[k]);
        change(k*2+1,mid+1,R,add[k]);
        add[k]=0; 
    }
}
void fuzhi(int k,int L,int R,int x,int y,int v)
{
    if(L>=x&&R<=y)
    {
        change2(k,L,R,v);
        return;
    } 
    pushdown(k,L,R);
    int mid=L+R>>1;
    if(x<=mid) fuzhi(k*2,L,mid,x,y,v);
    if(y>=mid+1) fuzhi(k*2+1,mid+1,R,x,y,v);
    pushUp(k); 
}
void update(int k,int L,int R,int x,int y,int v) 
{
    if(L>=x&&R<=y)
    {
        change(k,L,R,v);
        return;
    } 
    pushdown(k,L,R);
    int mid=L+R>>1;
    if(x<=mid) update(k*2,L,mid,x,y,v);
    if(y>=mid+1) update(k*2+1,mid+1,R,x,y,v);
    pushUp(k); 
}
ll query(int k,int L,int R,int x,int y)
{
    if(x<=L&&y>=R) return ma[k];
    pushdown(k,L,R);
    int mid=L+R>>1;
    ll res=0;
    if(x<=mid)  res=query(k*2,L,mid,x,y); 
    if(y>=mid+1) res=max(res,query(k*2+1,mid+1,R,x,y));
    return res;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int q,x,y,k;
        scanf("%lld",&q);
        switch(q)
        {
            case 1:{
                scanf("%lld%lld%lld",&x,&y,&k);
                fuzhi(1,1,n,x,y,k);
                break;
            }
            case 2:{
                scanf("%lld%lld%lld",&x,&y,&k);
                update(1,1,n,x,y,k);
                break;
            }
            case 3:{
                scanf("%lld%lld",&x,&y);
                printf("%lld\n",query(1,1,n,x,y));
                break;
            }
        }
    }
    return 0;
}

by liuzhengtao @ 2024-10-21 22:59:31

好了，我知道问题出哪里了

by liuzhengtao @ 2024-10-21 23:05:23

# include <stdio.h>
# include <limits.h>
# include <iostream>
using namespace std;
#define int long long
long long Tree[1000005*4];
long long tag1[1000005*4];
long long tag2[1000005*4];
long long arr[1000005];
int n,m;

void add_tag1(int node,int l,int r,int k)
{
    tag1[node] += k;
    Tree[node] += k;
    return ;
}

void add_tag2(int node,int l,int r,int k)
{
    tag1[node] = 0;
    tag2[node] = k;
    Tree[node] = k;
    return ;
}

void push_down(int node,int l,int r)
{
    if (tag2[node] != LLONG_MAX)
    {
        int mid = (l + r) / 2;
        add_tag2(node*2,l,mid,tag2[node]);
        add_tag2(node*2+1,mid+1,r,tag2[node]);
        tag2[node] = LLONG_MAX;     
    }
    if (tag1[node] != 0)
    {
        int mid = (l + r) / 2;
        add_tag1(node*2,l,mid,tag1[node]);
        add_tag1(node*2+1,mid+1,r,tag1[node]);
        tag1[node] = 0;
    }
    return ;
}

void Build(int node,int l,int r)
{
    tag2[node] = LLONG_MAX;
    if (l == r)
    {
        Tree[node] = arr[l];
        return ;
    }

    int mid = (l+r) /2;
    Build(node*2,l,mid);
    Build(node*2+1,mid+1,r);

    Tree[node] = max(Tree[node*2],Tree[node*2+1]);

    return  ;
}

void Update1(int node,int l,int r,int tl,int tr,int w)
{
    if (tl <= l && tr >= r)
    {
        add_tag1(node,l,r,w);
        return ;
    }

    push_down(node,l,r);
    int mid = (l+r) / 2;

    if (mid  >= tl)
    {
        Update1(node*2,l,mid,tl,tr,w);
    }
    if (mid < tr)
    {
        Update1(node*2+1,mid+1,r,tl,tr,w);
    }

    Tree[node] = max(Tree[node*2],Tree[node*2+1]);

    return ;
}

void Update2(int node,int l,int r,int tl,int tr,int w)
{
    if (tl <= l && tr >= r)
    {
        add_tag2(node,l,r,w);
        return ;
    }

    push_down(node,l,r);
    int mid = (l+r) / 2;

    if (mid >= tl)
    {
        Update2(node*2,l,mid,tl,tr,w);
    }
    if (mid < tr)
    {
        Update2(node*2+1,mid+1,r,tl,tr,w);
    }

    Tree[node] = max(Tree[node*2],Tree[node*2+1]);

    return ;
}

long long Query(int node,int l,int r,int tl,int tr)
{
    if (tl <= l && tr >= r)
    {
        return Tree[node];
    }

    int mid = (l+r)/2;

    push_down(node,l,r);
    long long res=LLONG_MIN;

    if (mid  >= tl)
    {
        res = max(Query(node*2,l,mid,tl,tr),res);
    }
    if (mid < tr)
    {
        res = max(Query(node*2+1,mid+1,r,tl,tr),res);
    }

    return res;
}

signed main ()
{

    scanf ("%lld %lld",&n,&m);

    for (int i=1;i<=n;i++)
    {
        scanf ("%lld",&arr[i]);
    }

    Build(1,1,n);

    for (int i=0;i<m;i++)
    {
        int opt,x,y;
        scanf ("%lld %lld %lld",&opt,&x,&y);
        if (opt == 1)
        {
            int k;
            scanf ("%lld",&k);
            Update2(1,1,n,x,y,k);
        }
        else if (opt == 2)
        {
            int k;
            scanf ("%lld",&k);
            Update1(1,1,n,x,y,k);           
        }
        else
        {
            printf ("%lld\n",Query(1,1,n,x,y));
        }    
    }

    return 0;
}

by liuzhengtao @ 2024-10-21 23:05:44

改完了，求壶关

by liuzhengtao @ 2024-10-21 23:08:03

把int 全改为long long 原因不知道，但是肯定是这快出错了，自己仔细查一查。

by cengzh @ 2024-10-23 17:49:49

@liuzhengtao 谢谢宝宝

by ChpyX2 @ 2024-10-24 16:45:56

@liuzhengtao @cengzh 同样的问题,刚刚测试了一下,发现只有函数和数组可以改longlong,其他改longlong还是错,错误的输出里面一些地方会变成0,可能是用longlong当下标导致的?

by cengzh @ 2024-10-25 00:20:18

@ChpyX2 感觉这种问题一直蛮困扰我的，太难了TvT

|