线段树板子写挂了求调

P3372 【模板】线段树 1

Vsinger_洛天依 @ 2023-10-10 17:12:59

谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;
    int dat;
}t[0x66ccf];
int ant[0x66ccf];
void APJ(int a,int b,int c){
    t[a].l=b;
    t[a].r=c;
    if(b==c){
        t[a].dat=ant[b];
        return;
    }
    int mid=(b+c)/2;
    APJ(a*2,b,mid);
    APJ(a*2+1,mid+1,c);
    t[a].dat=t[2*a].dat+t[2*a+1].dat;
}
void Soytony(int a,int b,int c){
    if(t[a].l==b){
        t[a].dat=c;
        return;
    }
    int mid=(b+c)/2;
    if(b<=mid){
        Soytony(a*2,b,c);
    }
    else{
        Soytony(a*2+1,b,c);
    }
    t[a].dat=t[2*a].dat+t[2*a+1].dat;
}
long long K8he(int a,int b,int c){
    if(t[a].l>=b && t[a].r<=c){
        return t[a].dat;
    }
    long long jijidawang=0;
    if(t[a].l>=b){
        jijidawang+=K8he(2*a,b,c);
    }
    if(t[a].r<=c){
        jijidawang+=K8he(2*a+1,b,c);
    }
    return jijidawang; 
}
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=1;i<=a;i++){
        cin>>ant[i];
    }
    APJ(1,1,b);
    for(int i=1;i<=b;i++){
        int c;
        cin>>c;
        if(c==1){
            int x,y,z;
            cin>>x>>y>>z;
            for(int j=x;j<=y;j++){
                Soytony(1,j,z);
            }
        }
        else{
            int x,y;
            cin>>x>>y;
            cout<<K8he(1,x,y)<<endl;
        }
    }
}

评测记录:here


by _Wind_Leaves_ShaDow_ @ 2023-10-10 17:18:53

很抽象,不管怎么样你这个都是 n^2 的吧。是因为不想写 lazytag 吗。


by xuhaotian @ 2023-10-10 17:19:18

int mid=(b+c)/2;

应该为

(t[a].l+t[a].r)/2

by _Wind_Leaves_ShaDow_ @ 2023-10-10 17:19:23

你要这么写还不如暴力 qwq。


by xuhaotian @ 2023-10-10 17:20:39

这线段树太抽象了\ 蒟蒻看不懂


by _Wind_Leaves_ShaDow_ @ 2023-10-10 17:22:49

确实写的很抽象。


by Vsinger_洛天依 @ 2023-10-10 17:24:56

QAQ


by Vsinger_洛天依 @ 2023-10-10 17:26:45

我觉得我写的也抽象其实


by FatOldEight @ 2023-10-10 17:27:26

首先:int mid=(b+c)/2;改成int mid=(t[a].l+t[a].r)/2.

然後,建議去學一下懶標記,因爲你這代碼是 O(n^2\log n) 的。

以及建議不要把同學作爲函數和變量名


by Vsinger_洛天依 @ 2023-10-10 17:29:56

@FatOldEight @xuhaotian @ zsq20100122

谢谢谢谢


by Vsinger_洛天依 @ 2023-10-10 17:30:36

?怎么有一个没@到


| 下一页