简单线段树WA 60pts求hack或帮调

P1253 扶苏的问题

紊莫 @ 2024-01-11 14:51:53

// Problem: P1253 扶苏的问题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1253
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
inline int rd() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x) {
    if(x<0)x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline int lowbit(int x) {
    return x&(-x);
}
typedef long long ll;
typedef pair<int,int> Pair;

const int N=1000005,M=(N<<1),inf=1e18,mod=1e9+7;
int n,q,a[N];
struct SegmentTree{
    int l,r,mx,add,tag;
}t[N<<2];
void upd(int p){
    t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
}
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;t[p].tag=inf;
    if(l==r){ t[p].mx=a[l];return; }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    upd(p);
}
void spread(int p){
    int q=t[p].tag;
    if(q!=inf){
        t[p*2].mx=t[p*2+1].mx=q;
        t[p*2].add=t[p*2+1].add=0;
        t[p*2].tag=t[p*2+1].tag=q;
        t[p].tag=inf;t[p].add=0;
    }
    q=t[p].add;
    if(q){
        t[p*2].mx+=q;
        t[p*2+1].mx+=q;
        t[p*2].add+=q;
        t[p*2+1].add+=q;
        t[p].add=0;
    }
}
void change2(int p,int l,int r,int v){
    if(l<=t[p].l&&r>=t[p].r) {
        t[p].mx=v;t[p].add=0;t[p].tag=v;
        return;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) change2(p*2,l,r,v);
    if(r>mid) change2(p*2+1,l,r,v);
    upd(p);
}
void change1(int p,int l,int r,int v){
    if(l<=t[p].l&&r>=t[p].r) {
        int q=t[p].tag;
        if(q!=inf){
            t[p*2].mx=t[p*2+1].mx=q;
            t[p*2].add=t[p*2+1].add=0;
            t[p*2].tag=t[p*2+1].tag=q;
            t[p].tag=inf;t[p].add=0;
        }
        t[p].mx+=v;t[p].add+=v;
        return;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) change1(p*2,l,r,v);
    if(r>mid) change1(p*2+1,l,r,v);
    upd(p);
}
int ask(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)
        return t[p].mx;
    int rt=-inf,mid=(t[p].l+t[p].r)/2;
    spread(p);
    if(l<=mid) rt=max(rt,ask(p*2,l,r));
    if(r>mid) rt=max(rt,ask(p*2+1,l,r));
    return rt;
}
void solve(){
    n=rd();q=rd();
    F(i,1,n)a[i]=rd();
    build(1,1,n);
    while(q--){
        int op=rd(),l=rd(),r=rd();
        if(op==1) change2(1,l,r,rd());
        else if(op==2) change1(1,l,r,rd());
        else write(ask(1,l,r)),cout<<"\n";
    }
}
signed main() {
    solve();
    return 0;
}

by Cure_Wing @ 2024-01-11 20:54:57

@紊莫

Hack:

Input:

8 4
1 2 3 4 5 6 7 8
1 1 8 5
2 1 8 1
2 1 8 3
3 3 6

Output:

5

Answer:

9

原因:第 61 行和第 90 行,下传标记时使用了 t[p].add=0;,这会使得在有区间推平操作后连续进行区间加操作时会覆盖之前的区间加操作导致错误,删去这两处即可 AC。


by 紊莫 @ 2024-01-11 20:57:31

@Sunmoon /bx


|