#6WA求助

P1253 扶苏的问题

Alfred_zhc @ 2023-09-24 00:07:59

对付剩下的超时和溢出我实在弄不懂 只求拿个60就行:(

#include <bits/stdc++.h>
using namespace std;

int const M=2e6+7;

struct node {
    // 线段树 
    int n;
    int l, r;
    int az;// 啊这,懒标记,没错,l az y
}nds[M*2];

int a[M]; 
int n, q;

int read() {
    // 快读 
    int x=0, f=1;
    char c = getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }

    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
} 

void build(int l, int r, int d) {
    // 建树 
    if(l==r) {
        nds[d] = {a[l], l, r, 0};
        return;
    }

    int mid = (l+r)/2;

    build(l, mid, d*2);
    build(mid+1, r, d*2+1);

    nds[d] = {max(nds[d*2].n, nds[d*2+1].n), l, r, 0};
}

void modify(int dl, int dr, int l, int r, int x, int d) {
    // 替换

    if(l==r) {
        nds[d].n=x;
        return;
    }
    int mid = (l+r)/2;

    if(nds[d].az) {
        // 下放标记
        nds[d*2].n+=nds[d].az;
        nds[d*2].az+=nds[d].az;
        nds[d*2+1].n+=nds[d].az;
        nds[d*2+1].az+=nds[d].az;
        nds[d].az=0;
    }

    if(mid>=dl) modify(dl, dr, l, mid, x, d*2);
    if(mid+1<=dr) modify(dl, dr, mid+1, r, x, d*2+1);

    nds[d].n=max(nds[d*2].n, nds[d*2+1].n);
}

void plusf(int dl, int dr, int l, int r, int x, int d) {
    // 齐增 懒标记 
    if(l>=dl&&r<=dr) {
        nds[d].az+=x;
        nds[d].n+=x;
        return;
    }
    int mid = (l+r)/2;

    if(nds[d].az) {
        // 下放标记
        nds[d*2].n+=nds[d].az;
        nds[d*2].az+=nds[d].az;
        nds[d*2+1].n+=nds[d].az;
        nds[d*2+1].az+=nds[d].az;
        nds[d].az=0;
    }

    if(mid>=dl) plusf(dl, dr, l, mid, x, d*2);
    if(mid+1<=dr) plusf(dl, dr, mid+1, r, x, d*2+1);

    nds[d].n=max(nds[d*2].n, nds[d*2+1].n);
}

int query(int dl, int dr, int l, int r, int d) {
    // 求和 

    if(nds[d].az) {
        // 下放标记
        nds[d*2].n+=nds[d].az;
        nds[d*2].az+=nds[d].az;
        nds[d*2+1].n+=nds[d].az;
        nds[d*2+1].az+=nds[d].az;
        nds[d].az=0;
    }

    if(l>=dl&&r<=dr) return nds[d].n;

    int mid = (l+r)/2;

    int gl=INT_MIN, gr=INT_MIN;

    if(mid>=dl) gl = query(dl, dr, l, mid, d*2);
    if(mid+1<=dr) gr = query(dl, dr, mid+1, r, d*2+1);

    return max(gl, gr);
}

int main() {
    n=read();
    q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1, n, 1);

//  for(int i=1;i<=n*2+1;i++) {
//      cout<<nds[i].n<<' ';
//  }

    int op, a, b, c;
    while(q--)
    {
        op=read();
        if(op==1) {
            a=read();b=read();c=read();
            modify(a, b, 1, n, c, 1);
        }
        else if(op==2) {
            // 同加 
            a=read();b=read();c=read();
            plusf(a, b, 1, n, c, 1);
        }
        else {
            // 区间最大 
            a=read();b=read();
            cout<<query(a, b, 1, n, 1)<<'\n';
        }
    }

    return 0;
}

//6 6
//1 1 4 5 1 4
//3 1 3
//3 2 5
//3 5 6

想知道到底是什么问题,或许和数据范围有关?求列位大佬解惑

看了一下,我的懒标记加的有些非主流,麻烦列位大佬的眼睛了故意的


|