警钟撅烂：建议写挂的都进来看看，汇总了各类错误

AC_love @ 2023-08-14 22:26:34

0 分 - 20 分的：检查一下线段树写没写错，有没有少写 pushdown 和 pushup 什么的。

50 分的：开 long long，然后把你的不需要覆盖的懒标记的情况的值设小一点，比如我最开始设成 -2147483647 就只有 50 分，换成 -21474836470000 就 60 分了。

60 分的：可能是下传标记的顺序错了，或者下传的时候加了一些多余的覆盖语句导致把已经修改过的内容覆盖了。

90 分的：如果是 RE 大概率是数组开小了，建议换成八倍数组。

如果是 TLE 了，建议使用 scanf 和 printf 输入输出（我用 cin 和 cout 最后一个点就 T 了，用 scanf 和 printf 就顺利 A 掉）。

by WsW_ @ 2023-08-14 22:28:21

20分呜呜

#include<bits/stdc++.h>
#define ll long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;

struct node{
    int l,r;
    bool f;
//  int z;
    ll add;
    ll val;
}tree[4000000];
int a[1000001];
int op,l,r,x;
int n,q;

void pushup(int id){
    tree[id].val=max(tree[ls(id)].val,tree[rs(id)].val);
}

void pushdown(int id){
    if(tree[id].f){
        tree[id].f=0;
        tree[ls(id)].f=tree[rs(id)].f=1;
        tree[ls(id)].val=tree[rs(id)].val=tree[id].val;
        tree[ls(id)].add=tree[rs(id)].add=tree[id].add=0;
    }
    else{
        tree[ls(id)].add+=tree[id].add;
        tree[rs(id)].add+=tree[id].add;
        tree[ls(id)].val+=tree[id].add;
        tree[rs(id)].val+=tree[id].add;
        tree[id].add=0;
    }
}

void build(int id,int l,int r){
//  cout<<id<<":　"<<l<<"~~"<<r<<endl; 
    tree[id].l=l;
    tree[id].r=r;
    tree[id].add=tree[id].val=tree[id].f=0;
    if(l==r){
        tree[id].val=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(ls(id),l,mid);
    build(rs(id),mid+1,r);
    pushup(id);
}

void upd(int id,int l,int r,int x,int op){
//  cout<<id<<": "<<tree[id].l<<"--"<<tree[id].r<<endl;
    if(l<=tree[id].l&&tree[id].r<=r){
        if(op==1){
            tree[id].f=1;
            tree[id].add=0;
            tree[id].val=x;
        }
        else{
            if(!tree[id].f)tree[id].add+=x;
            tree[id].val+=x;
        }
        return ;
    }
    pushdown(id);
    int mid=tree[id].l+tree[id].r>>1;
    if(l<=mid)upd(ls(id),l,r,x,op);
    if(r>mid)upd(rs(id),l,r,x,op);
    pushup(id);
}

ll query(int id,int l,int r){
    if(l<=tree[id].l&&tree[id].r<=r){
        return tree[id].val;
    }
    pushdown(id);
    int mid=tree[id].l+tree[id].r>>1;
    ll ans=-1e18;
    if(l<=mid)ans=max(ans,query(ls(id),l,mid));
    if(r>mid)ans=max(ans,query(rs(id),mid+1,r));
    return ans;
}

int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(q--){
        scanf("%d%d%d",&op,&l,&r);
        if(op==3){
            printf("%lld\n",query(1,l,r));
        }
        else{
            scanf("%d",&x);
            upd(1,l,r,x,op);
        }
    }
    return 0;
}

by ncwzdlsd @ 2023-08-14 22:41:22

巨佬%%%

by ncwzdlsd @ 2023-08-14 22:41:48

@AC_love 大佬教我线段树优化 DP 吧/bx/bx

by ncwzdlsd @ 2023-08-14 22:42:24

@AC_love 不一定非得用 scanf，你把同步流关了捆绑关了也能过吧

by AC_love @ 2023-08-14 22:47:07

@ncwzdlsd

关同步流的 cin 和 cout 速度比 printf 和 scanf 确实可能快很多，但是当你换了 printf 和 scanf 的时候，你的代码复杂度的瓶颈就已经不在输入输出上了，所以这个关闭同步流其实我觉得意义不大，而且有时候关闭同步流却不小心把两种输入输出混用还会导致挂掉，这样就很难办

by AC_love @ 2023-08-14 22:56:24

@WsW_ 你在每个函数里加点输出当前节点维护权值还有更新什么的语句自己调一调看看吧，我自己的代码调了两个小时才调出来，刚才我给你看了几遍感觉逻辑上没毛病，应该是细节出问题了，你输出一下中间变量试试看

比如这样：

#include <bits/stdc++.h>
#define int long long
#define tpl t[p].l
#define tpr t[p].r
#define t2pl t[p*2].l
#define t2pr t[p*2].r
#define t2p1l t[p*2+1].l
#define t2p1r t[p*2+1].r
#define tpa t[p].add
#define tpm t[p].m
#define tpc t[p].changement
#define t2pm t[p*2].m
#define t2p1m t[p*2+1].m
#define t2pc t[p*2].changement
#define t2p1c t[p*2+1].changement
#define t2pa t[p*2].add
#define t2p1a t[p*2+1].add
#define mn -214748364700000
using namespace std;
int a[1919810];
struct tree
{
    int l;
    int r;
    int add;
    int changement;
    int m;
};
tree t[8114514];

void build(int p, int l, int r)
{
    tpl = l;
    tpr = r;
    tpc = mn;
    if(l == r)
    {
        tpm = a[l];
        tpc = mn;
//      cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，最大值为" << tpm << "\n";
        return;
    }

    int mid = (l + r) / 2;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    tpm = max(t2pm, t2p1m);
//  cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，最大值为" << tpm << "\n";
    return;
}

void spreadc(int p)
{
    if(tpc != mn)
    {
//      cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，更改为了" << tpc << "\n";
//      tpm = tpc;
        t2pm = tpc;
        t2p1m = tpc;
        t2pc = tpc;
        t2p1c = tpc;
        t2pa = 0;
        t2p1a = 0;
//      tpa = 0;
//      cout << 2*p << "号节点维护的范围为从" << t2pl << "到" << t2pr << "，更改为了" << tpc << "\n";
//      cout << 2*p+1 << "号节点维护的范围为从" << t2p1l << "到" << t2p1r << "，更改为了" << tpc << "\n";
        tpc = mn;
    }
}

void spreada(int p)
{
    if(tpa != 0)
    {

        t2pm += tpa;
        t2p1m += tpa;
        t2pa += tpa;
        t2p1a += tpa;
//      cout << 2*p << "号节点维护的范围为从" << t2pl << "到" << t2pr << "，更改了" << tpa << "\n";
//      cout << 2*p+1 << "号节点维护的范围为从" << t2p1l << "到" << t2p1r << "，更改了" << tpa << "\n";
        tpa = 0;
    }
}

void pushdown(int p)
{
    spreadc(p);
    spreada(p);
}

void changec(int p, int l, int r, int k)
{
    if(l <= tpl && tpr <= r)
    {
//      cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，更改为了" << k << "\n";
        tpm = k;
        tpa = 0;
        tpc = k;
        return;
    }
    pushdown(p);

    int mid = (tpl + tpr) / 2;
    if(l <= mid)
        changec(p * 2, l, r, k);
    if(r > mid)
        changec(p * 2 + 1, l, r, k);
    tpm = max(t2pm, t2p1m);
}

void changea(int p, int l, int r, int k)
{
    pushdown(p);
    if(l <= tpl && tpr <= r)
    {
//      cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，更改了" << k << "\n";
        tpm += k;
        tpa += k;
        return;
    }
    pushdown(p);

    int mid = (tpl + tpr) / 2;
    if(l <= mid)
        changea(p * 2, l, r, k);
    if(r > mid)
        changea(p * 2 + 1, l, r, k);
    tpm = max(t2pm, t2p1m);
}

int ask(int p, int l, int r)
{
    if(l <= tpl && tpr <= r)
    {
//      cout << p << "号节点在区间范围内，维护的范围为从" << tpl << "到" << tpr << "，最大值为" << tpm << "\n";
        return tpm;
    }
    pushdown(p);
    int mid = (tpl + tpr) / 2;
//  cout << mid << "??????" << l << " " << r << "\n"; 
    int maxn = mn;
    if(l <= mid)
    {
//      cout << 2 * p << "号节点部分在区间范围内，维护的范围为从" << t2pl << "到" << t2pr << "\n";
        maxn = max(maxn, ask(p * 2, l, r));
    }
    if(r > mid)
    {
//      cout << 2 * p + 1 << "号节点部分在区间范围内，维护的范围为从" << t2p1l << "到" << t2p1r << "\n";
        maxn = max(maxn, ask(p * 2 + 1, l, r));
    }
    return maxn;
}

//void print(int p)
//{
//  cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，最大值为" << tpm << "\n";
//  
//  if(tpl == tpr)
//      return;
//  
//  print(p * 2);
//  print(p * 2 + 1);
//}
int n, m;

signed main()
{
//  freopen("a.txt", "r", stdin);
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i = i + 1)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    for(int i = 1; i <= m; i = i + 1)
    {
        int op, l, r, x;
        scanf("%lld%lld%lld", &op, &l, &r);
        if(op == 1)
        {
            scanf("%lld", &x);
            changec(1, l, r, x);
        }
        if(op == 2)
        {
            scanf("%lld", &x);
            changea(1, l, r, x);
        }
        if(op == 3)
            printf("%lld\n", ask(1, l, r));
//      cout << "\n\n\n";
//      
//      print(1);
//      cout << "\n\n\n";
    }
    return 0;
}

by JT_dw_ @ 2023-08-14 23:12:28

@AC_love %%%

by Falling_Sakura @ 2023-08-15 20:52:15

加前的覆盖注意不要下放到叶子节点，这就是为什么八倍空间才能过。

if(tr[u].l!=tr[u].r) pushdown2(u);

by Enoch006 @ 2023-08-24 18:36:00

%%% 栽在了inf上