70分求助，T了3个点

__zhang__ @ 2024-04-30 19:23:27

#include<bits/stdc++.h>
using namespace std;
list<int> l;
int main(){
    int m,n;
    cin>>m>>n;

    for(int i=1;i<=m;i++){
        int s;
        cin>>s;
        l.push_back(s);
    }
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        if(a==1){
            int x,y,k;
            cin>>x>>y>>k;
            auto it=l.begin();
            for(int j=0;j<x-1;j++){
                ++it;
            }

            for(int j=x-1;j<y;j++){
                *it+=k;
                it++;
            }
        }
        else {
            int x,y;
            cin>>x>>y;
            auto it=l.begin();
            for(int j=0;j<x-1;j++){
                ++it;
            }
            int ans=0;
            for(int j=x-1;j<y;j++){
                ans+=*it;
                it++;

            }
            cout<<ans<<endl;    
        }
    }
} 

by __zhang__ @ 2024-04-30 19:25:06

不会线段树，谁能教我怎么用链表写

by Untitled_unrevised @ 2024-04-30 19:33:31

你链表时间复杂度上本来就过不去的啊。

by Lijunzhuo @ 2024-04-30 19:39:24

？（这道题链表时间复杂度能达到线段树？）

by Lijunzhuo @ 2024-04-30 19:40:53

链表达不到 O(m log n)

by Lijunzhuo @ 2024-04-30 19:41:17

emm

by __zhang__ @ 2024-05-26 16:39:34

@Lijunzhuo这样可以吗？

#include<bits/stdc++.h>
#define L_s (node*2)
#define R_s (node*2+1)
#define ll long long
using namespace std;
const int Max=0xfffff;
int n,m,a[Max*4];
int step;
struct segment_tree{
    int lazy;
    int l,r;
    ll sum;
}tree[Max*4];
void pushup(ll node){
    tree[node].sum=tree[L_s].sum+tree[R_s].sum;
}
void build(ll l,ll r,ll node){
    tree[node].l=l;
    tree[node].r=r;
    tree[node].lazy=0;
    if(l==r){
        tree[node].sum=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(l,mid,L_s);
    build(mid+1,r,R_s);
    pushup(node);
}
void maketag(ll k,ll node){
    tree[node].sum+=k*(tree[node].r-tree[node].l+1);
    tree[node].lazy+=k;
}
void pushdown(ll node){
    maketag(tree[node].lazy,L_s);
    maketag(tree[node].lazy,R_s);
    tree[node].lazy=0;
}
void update(ll l,ll r,ll add,ll node){
    if(l>tree[node].r||r<tree[node].l)return;
    if(l<=tree[node].l&&r>=tree[node].r){
        tree[node].sum+=add*(tree[node].r-tree[node].l+1);
        tree[node].lazy+=add;
        return;
    }
    pushdown(node);
    update(l,r,add,L_s);    
    update(l,r,add,R_s);    
    pushup(node);
}
ll query_sum(ll l,ll r,ll node){
    if(l>tree[node].r||r<tree[node].l)return 0;
    if(l<=tree[node].l&&r>=tree[node].r)return tree[node].sum;
    pushdown(node);
    return query_sum(l,r,L_s)+query_sum(l,r,R_s);
} 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);
    while(m--){
        cin>>step;
        if(step==1){
            int x,y,k;
            cin>>x>>y>>k;
            update(x,y,k,1);
            continue;   
        }
        else {
            int x,y;
            cin>>x>>y;
            cout<<query_sum(x,y,1)<<'\n';
            continue;
        }
    }
}