还有3天AFO，60pts求调[大哭]

P1253 扶苏的问题

Little_Joker @ 2023-11-15 17:09:12

还有3天AFO了，调不动了，救救孩子吧[大哭]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=1e6+10;
const ll INF=4557430888798830399;
int n,m;
ll a[maxn],sum[4*maxn],lzy_tag[4*maxn],lzy_tag2[4*maxn],maxx[4*maxn];
//lzy_tag1[]是"加上x"的标记数组; lzy_tag2[]是"修改为x"的标记数组 
void build(int l,int r,int p)   //p是当前的节点
{
    if(l==r){
        maxx[p]=a[l];
        sum[p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,2*p);
    build(mid+1,r,2*p+1);
    sum[p]=sum[p*2]+sum[p*2+1];
    maxx[p]=max(maxx[2*p],maxx[2*p+1]);
}
void push_down_lzy_tag(int l,int r,int p)
{
    int mid=(l+r)>>1;
    sum[p*2]+=lzy_tag[p]*(mid-l+1);
    sum[p*2+1]+=lzy_tag[p]*(r-mid);
    maxx[p*2]+=lzy_tag[p];
    maxx[p*2+1]+=lzy_tag[p];
    lzy_tag[p*2]+=lzy_tag[p];
    lzy_tag[p*2+1]+=lzy_tag[p];
    lzy_tag[p]=0;
}
void push_down_lzy_tag2(int l,int r,int p)
{
    int mid=(l+r)>>1;
    sum[p*2]=lzy_tag2[p]*(mid-l+1);
    sum[p*2+1]=lzy_tag2[p]*(r-mid);
    maxx[p*2]=lzy_tag2[p];
    maxx[p*2+1]=lzy_tag2[p];
    lzy_tag2[p*2]=lzy_tag2[p];
    lzy_tag2[p*2+1]=lzy_tag2[p];
    lzy_tag2[p]=0;
}
ll getmax(int l,int r,int L,int R,int p)    //[L,R]是要查询的区间
{
    if(L<=l&&r<=R) return maxx[p];
    int mid=(l+r)>>1;
    ll maxxx=-INF;
    if(lzy_tag2[p]!=INF)
    {
        push_down_lzy_tag2(l,r,p);
    }
    if(lzy_tag[p])
    {
        push_down_lzy_tag(l,r,p);
    }
    if(L<=mid) maxxx=max(maxxx,getmax(l,mid,L,R,p*2));
    if(R>mid) maxxx=max(maxxx,getmax(mid+1,r,L,R,p*2+1));
    return maxxx;
}
void update(int l,int r,int L,int R,int p,int f)
{
    if(L<=l&&r<=R)
    {
        sum[p]+=(r-l+1)*f;
        maxx[p]+=f;
        lzy_tag[p]+=f;
        return;
    }
    if(lzy_tag2[p]!=INF)
    {
        push_down_lzy_tag2(l,r,p);
    }
    if(lzy_tag[p])
    {
        push_down_lzy_tag(l,r,p);
    }
    int mid=(l+r)>>1;
    if(L<=mid) update(l,mid,L,R,p*2,f);
    if(R>mid) update(mid+1,r,L,R,p*2+1,f);
    sum[p]=sum[p*2]+sum[p*2+1];
    maxx[p]=max(maxx[2*p],maxx[2*p+1]);
}
void update2(int l,int r,int L,int R,int p,int f)
{
    if(L<=l&&r<=R){
        sum[p]=(r-l+1)*f;
        maxx[p]=f;
        lzy_tag2[p]=f;
        return;
    }
    if(lzy_tag2[p]!=INF)
    {
        push_down_lzy_tag2(l,r,p);
    }
    if(lzy_tag[p])
    {
        push_down_lzy_tag(l,r,p);
    }
    int mid=(l+r)>>1;
    if(L<=mid) update2(l,mid,L,R,p*2,f);
    if(R>mid) update2(mid+1,r,L,R,p*2+1,f);
    sum[p]=sum[p*2]+sum[p*2+1];
    maxx[p]=max(maxx[2*p],maxx[2*p+1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(maxx,-0x3f,sizeof(maxx));
    memset(lzy_tag2,0x3f,sizeof(lzy_tag2));
    for(int i=1;i<=n;i++)   scanf("%lld",&a[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            int k;
            scanf("%d",&k);
            update2(1,n,x,y,1,k);
        }
        else if(op==2){
            int k;
            scanf("%d",&k);
            update(1,n,x,y,1,k);
        }
        else if(op==3){
            printf("%lld\n",getmax(1,n,x,y,1));
        }
    }
    return 0;
}

WA on #7~10

by qnqfff @ 2023-11-15 17:21:55

@Little_Joker

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=1e6+10;
const ll INF=4557430888798830399;
int n,m;
ll a[maxn],sum[4*maxn],lzy_tag[4*maxn],lzy_tag2[4*maxn],maxx[4*maxn];
//lzy_tag1[]是"加上x"的标记数组; lzy_tag2[]是"修改为x"的标记数组 
void build(int l,int r,int p)   //p是当前的节点
{
    if(l==r){
        maxx[p]=a[l];
        sum[p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,2*p);
    build(mid+1,r,2*p+1);
    sum[p]=sum[p*2]+sum[p*2+1];
    maxx[p]=max(maxx[2*p],maxx[2*p+1]);
}
void push_down_lzy_tag(int l,int r,int p)
{
    int mid=(l+r)>>1;
    sum[p*2]+=lzy_tag[p]*(mid-l+1);
    sum[p*2+1]+=lzy_tag[p]*(r-mid);
    maxx[p*2]+=lzy_tag[p];
    maxx[p*2+1]+=lzy_tag[p];
    lzy_tag[p*2]+=lzy_tag[p];
    lzy_tag[p*2+1]+=lzy_tag[p];
    lzy_tag[p]=0;
}
void push_down_lzy_tag2(int l,int r,int p)
{
    int mid=(l+r)>>1;
    sum[p*2]=lzy_tag2[p]*(mid-l+1);
    sum[p*2+1]=lzy_tag2[p]*(r-mid);
    maxx[p*2]=lzy_tag2[p];
    maxx[p*2+1]=lzy_tag2[p];
    lzy_tag2[p*2]=lzy_tag2[p];
    lzy_tag2[p*2+1]=lzy_tag2[p];
    lzy_tag2[p]=INF;
    lzy_tag[p*2]=lzy_tag[p*2+1]=0;
}
ll getmax(int l,int r,int L,int R,int p)    //[L,R]是要查询的区间
{
    if(L<=l&&r<=R) return maxx[p];
    int mid=(l+r)>>1;
    ll maxxx=-INF;
    if(lzy_tag2[p]!=INF)
    {
        push_down_lzy_tag2(l,r,p);
    }
    if(lzy_tag[p])
    {
        push_down_lzy_tag(l,r,p);
    }
    if(L<=mid) maxxx=max(maxxx,getmax(l,mid,L,R,p*2));
    if(R>mid) maxxx=max(maxxx,getmax(mid+1,r,L,R,p*2+1));
    return maxxx;
}
void update(int l,int r,int L,int R,int p,int f)
{
    if(L<=l&&r<=R)
    {
        sum[p]+=(r-l+1)*f;
        maxx[p]+=f;
        lzy_tag[p]+=f;
        return;
    }
    if(lzy_tag2[p]!=INF)
    {
        push_down_lzy_tag2(l,r,p);
    }
    if(lzy_tag[p])
    {
        push_down_lzy_tag(l,r,p);
    }
    int mid=(l+r)>>1;
    if(L<=mid) update(l,mid,L,R,p*2,f);
    if(R>mid) update(mid+1,r,L,R,p*2+1,f);
    sum[p]=sum[p*2]+sum[p*2+1];
    maxx[p]=max(maxx[2*p],maxx[2*p+1]);
}
void update2(int l,int r,int L,int R,int p,int f)
{
    if(L<=l&&r<=R){
        sum[p]=(r-l+1)*f;
        maxx[p]=f;
        lzy_tag2[p]=f;
        lzy_tag[p]=0;
        return;
    }
    if(lzy_tag2[p]!=INF)
    {
        push_down_lzy_tag2(l,r,p);
    }
    if(lzy_tag[p])
    {
        push_down_lzy_tag(l,r,p);
    }
    int mid=(l+r)>>1;
    if(L<=mid) update2(l,mid,L,R,p*2,f);
    if(R>mid) update2(mid+1,r,L,R,p*2+1,f);
    sum[p]=sum[p*2]+sum[p*2+1];
    maxx[p]=max(maxx[2*p],maxx[2*p+1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(maxx,-0x3f,sizeof(maxx));
    memset(lzy_tag2,0x3f,sizeof(lzy_tag2));
    for(int i=1;i<=n;i++)   scanf("%lld",&a[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            int k;
            scanf("%d",&k);
            update2(1,n,x,y,1,k);
        }
        else if(op==2){
            int k;
            scanf("%d",&k);
            update(1,n,x,y,1,k);
        }
        else if(op==3){
            printf("%lld\n",getmax(1,n,x,y,1));
        }
    }
    return 0;
}

by Exp10re @ 2023-11-15 17:29:04

@Little_Joker

update2 里面的：

if(L<=l&&r<=R){
    sum[p]=(r-l+1)*f;
    maxx[p]=f;
    lzy_tag2[p]=f;
    return;
}

改为：

if(L<=l&&r<=R){
    sum[p]=(r-l+1)*f;
    maxx[p]=f;
    lzy_tag2[p]=f;
    lzy_tag[p]=0;
    return;
}

push_down_lzy_tag2 后面


void push_down_lzy_tag2(int l,int r,int p)
{
    int mid=(l+r)>>1;
    sum[p*2]=lzy_tag2[p]*(mid-l+1);
    sum[p*2+1]=lzy_tag2[p]*(r-mid);
    maxx[p*2]=lzy_tag2[p];
    maxx[p*2+1]=lzy_tag2[p];
    lzy_tag2[p*2]=lzy_tag2[p];
    lzy_tag2[p*2+1]=lzy_tag2[p];
    lzy_tag2[p]=0;//here
}


void push_down_lzy_tag2(int l,int r,int p)
{
    int mid=(l+r)>>1;
    sum[p*2]=lzy_tag2[p]*(mid-l+1);
    sum[p*2+1]=lzy_tag2[p]*(r-mid);
    maxx[p*2]=lzy_tag2[p];
    maxx[p*2+1]=lzy_tag2[p];
    lzy_tag2[p*2]=lzy_tag2[p];
    lzy_tag2[p*2+1]=lzy_tag2[p];
    lzy_tag2[p]=INF;//here
    lzy_tag[p*2+1]=0;
    lzy_tag[p*2]=0;
}

by Exp10re @ 2023-11-15 17:30:00

@Little_Joker 原理是区间覆盖优先级大于区间加。

by Little_Joker @ 2023-11-15 17:37:32

@Exp10re @qnqfff 跪谢大佬终于AC了