线段树写挂了，样例没过

zhujiajun2013 @ 2024-07-24 13:57:07

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <memory>
using namespace std;
const int N=100000;
long long n,t,a[N+5],tr[4*N+5];
void pushup(int rt){
    tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        tr[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void change(int rt,int l,int r,int x,int y,int k){
    if(l==x&&r==y){
        tr[rt] += k;
        return ;
    }
    int mid=(l+r)>>1;
    if(y<=mid)change(rt<<1,l,mid,x,y,k);
    else if(x > mid) change(rt<<1|1,mid+1,r,x,y,k);
    else {
        change(rt<<1,l,mid,x,mid,k);
        change(rt<<1|1,mid+1,r,mid+1,y,k);
    }
}
int f3(int l,int r,int rt,int L,int R){
    if(L<=l&&r<=R){
        return tr[rt];
    }
    int mid=(l+r)>>1;
    if(R<=mid)return f3(l,mid,rt<<1,L,R);
    else if(L>mid) return f3(mid+1,r,rt<<1|1,L,R);
    else return f3(l,mid,rt<<1,L,mid)+f3(mid+1,r,rt<<1|1,mid+1,R);
}
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,n,1);
    while(t--){
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1){
            int k;
            cin>>k;
            change(1,1,n,x,y,k);
        }
        if(opt==2)
            cout<<f3(1,n,1,x,y)<<endl;
    }
    return 0;
}/*
样例输出：
11
6
12
*/

by 初星逝者 @ 2024-07-24 14:01:15

@SBAAAA0 要懒标记

by lzdqwq @ 2024-07-24 14:02:38

@SBAAAA0 你为什么改码风

by zhujiajun2013 @ 2024-07-24 14:03:11

@初星逝者 什么意思？

by lzdqwq @ 2024-07-24 14:03:47

@SBAAAA0,快来评论

by lzdqwq @ 2024-07-24 14:05:01

@SBAAAA0 ，你忘标记啦！

by lzdqwq @ 2024-07-24 14:06:04

#include<bits/stdc++.h>
using namespace std;
#define N 1005
using namespace std;
struct bignum{
    int d[N];
    void read(){
        char s[N];
        cin>>s;
        int n=strlen(s);
        for(int i=0;i<n;i++) d[i]=s[n-i-1]-'0';
        for(int i=n;i<N;i++) d[i]=0;
    }
    void write(){
        int pos=N-1;
        while(pos>0&&!d[pos]) pos--;
        for(int i=pos;i>=0;i--) cout<<d[i];
    }
    bool operator<(bignum x){
        for(int i=N-1;i>=0;i--) if(d[i]!=x.d[i]) return d[i]<x.d[i];
        return 0;
    }
    bignum operator+(bignum x){
        bignum tmp;
        for(int i=0;i<N;i++) tmp.d[i]=d[i]+x.d[i];
        for(int i=0;i<N-1;i++){
            if(tmp.d[i]>=10){
                tmp.d[i]-=10;
                tmp.d[i+1]++; 
            }
        }
        return tmp;
    }
    bignum operator-(bignum x){
        bignum tmp;
        for(int i=0;i<N;i++) tmp.d[i]=d[i]-x.d[i];
        for(int i=0;i<N-1;i++){
            if (tmp.d[i]<0){
                tmp.d[i]+=10;
                tmp.d[i+1]--; 
            }
        }
        return tmp;
    }
    bignum operator*(bignum x){
        bignum tmp;
        for(int i=0;i<N;i++) tmp.d[i]=0;
        for(int i=0;i<N;i++) for(int j=0;j+i<N;j++) tmp.d[i+j]+=d[i]*x.d[j];
        for(int i=0;i<N-1;i++){
            tmp.d[i+1]+=tmp.d[i]/10;
            tmp.d[i]%=10;
        }
        return tmp;
    }
    bignum operator*(int x){
        bignum tmp;
        for(int i=0;i<N;i++) tmp.d[i]=d[i]*x;
        for(int i=0;i<N-1;i++){
            tmp.d[i+1]+=tmp.d[i]/10;
            tmp.d[i]%=10;
        }
        return tmp;
    }
    bignum operator/(int x){
        long long res=0;
        bignum tmp;
        for(int i=N-1;i>=0;i--){
            res=res*10+d[i];
            tmp.d[i]=res/x;
            res=res%x;
        }
        return tmp;
    }
    void init(){
        for(int i=0;i<N;i++) d[i]=0;
    }
    bignum operator/(bignum x){
        bignum tmp,a,b;
        tmp.init();
        for(int i=0;i<N;i++) a.d[i]=d[i];
        for(int i=N/2-1;i>=0;i--){
            b.init();
            for(int j=0;j<N/2;j++) b.d[j+i]=x.d[j];
            while(!(a<b)) a=a-b,tmp.d[i]++;
        }
        return tmp;
    }
};
int n,xs[10005],ys[10005],fa[10005];
int find(int x){
    if(fa[x]==x) return (x);
    return (fa[x]=find(fa[x]));
}
int l,r,ans=0;
int check(int x){
    for(register int i=0;i<n;i++){
        fa[i]=i;
    }
    for(register int i=0;i<n;i++){
        for(register int j=i+1;i<n;i++){
            int dis=abs(xs[i]-xs[j])+abs(ys[i]-ys[j]);
            if(dis<=x*2){
                int aa=find(i);
                int ab=find(j);
                if(aa!=ab) fa[aa]=ab; 
            }
        }
    }
    int cnt=0;
    for(register int i=0;i<n;i++){
        if(fa[i]==i){
            cnt++;
        }
    }
    return cnt;
}
using namespace std;
const int N=100000;
long long n,t,a[N+5],tr[4*N+5];
void pushup(int rt){
    tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        tr[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void change(int rt,int l,int r,int x,int y,int k){
    if(l==x&&r==y){
        tr[rt] += k;
        return ;
    }
    int mid=(l+r)>>1;
    if(y<=mid)change(rt<<1,l,mid,x,y,k);
    else if(x > mid) change(rt<<1|1,mid+1,r,x,y,k);
    else {
        change(rt<<1,l,mid,x,mid,k);
        change(rt<<1|1,mid+1,r,mid+1,y,k);
    }
}
int f3(int l,int r,int rt,int L,int R){
    if(L<=l&&r<=R){
        return tr[rt];
    }
    int mid=(l+r)>>1;
    if(R<=mid)return f3(l,mid,rt<<1,L,R);
    else if(L>mid) return f3(mid+1,r,rt<<1|1,L,R);
    else return f3(l,mid,rt<<1,L,mid)+f3(mid+1,r,rt<<1|1,mid+1,R);
}
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,n,1);
    while(t--){
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1){
            int k;
            cin>>k;
            change(1,1,n,x,y,k);
        }
        if(opt==2)
            cout<<f3(1,n,1,x,y)<<endl;
    }
    return 0;
}

by zhujiajun2013 @ 2024-07-24 14:06:45

@lzdqwq 哪儿

by zhujiajun2013 @ 2024-07-24 14:09:31

@lzdqwq 有区别吗 怎么连并查集都加进来了？

by wfirstzhang @ 2024-07-24 14:14:26

@SBAAAA0 改 70 了，没 Lazy_Tag。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <memory>
using namespace std;
const int N=100000;
long n,t,a[N+5],tr[4*N+5];
void pushup(int rt){
    tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        tr[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void change(int rt,int l,int r,int x,int y,long k){
    if(l==r){
        tr[rt] += k;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)change(rt<<1,l,mid,x,y,k);
    if(y > mid) change(rt<<1|1,mid+1,r,x,y,k);
    pushup(rt);
}
long f3(int l,int r,int rt,int L,int R){
    if(L<=l&&r<=R){
        return tr[rt];
    }
    long res = 0;
    int mid=(l+r)>>1;
    if(L<=mid)res +=  f3(l,mid,rt<<1,L,R);
    if(R>mid) res +=  f3(mid+1,r,rt<<1|1,L,R);
    return res;
}
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)scanf("%ld",a+i);
    build(1,n,1);
    while(t--){
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1){
            long k;
            cin>>k;
            change(1,1,n,x,y,k);
        }
        if(opt==2)
            cout<<f3(1,n,1,x,y)<<endl;
    }
    return 0;
}

赠送一份我的代码：

#include <iostream>
template<class Tp = int>
class seg_tree {
    struct node {
        Tp data;
        Tp lazy_tag;
        node *lson, *rson;
        node& operator=(const node* const other) {
            data = other->data; lazy_tag = other->lazy_tag;
            if(other->lson != nullptr) { if(lson == nullptr) lson = new node; *lson = other->lson; }
            if(other->rson != nullptr) { if(rson == nullptr) rson = new node; *rson = other->rson; }
            return *this;
        }
        node() :data(0), lazy_tag(0), lson(nullptr), rson(nullptr)
        {}
        ~node() { delete lson; delete rson; }
    };
    static void push_up(node* parent) { parent->data = parent->lson->data + parent->rson->data; }
    static bool cover(long l, long r, long part_l, long part_r) { return part_l >= l && part_r <= r; }
    void build(const Tp* arr, node* parent, long part_l, long part_r) {
        if(part_l == part_r) {
            parent->data = arr[part_l];
            return;
        }
        long mid = part_l + part_r >> 1;
        if(parent->lson == nullptr) parent->lson = new node;
        if(parent->rson == nullptr) parent->rson = new node;
        build(arr, parent->lson, part_l, mid);
        build(arr, parent->rson, mid + 1, part_r);
        push_up(parent);
    }
    static void add_tag(node* parent, long part_l, long part_r, Tp val) {
        parent->lazy_tag += val;
        parent->data += (part_r - part_l + 1) * val;
    }
    void push_down(node* parent, long part_l, long part_r) {
        if(!parent->lazy_tag)   return;
        long mid = part_l + part_r >> 1;
        add_tag(parent->lson, part_l, mid, parent->lazy_tag);
        add_tag(parent->rson, mid + 1, part_r, parent->lazy_tag);
        parent->lazy_tag = 0;
    }
public:
    node* root;
    void adjust(long left, long right, Tp val, long part_r, long part_l, node* parent) {
        if(cover(left, right, part_l, part_r)) {
            add_tag(parent, part_l, part_r, val);
            return;
        }
        push_down(parent, part_l, part_r);
        long mid = part_l + part_r >> 1;
        if(left <= mid) adjust(left, right, val, mid, part_l, parent->lson);
        if(right > mid) adjust(left, right, val, part_r, mid + 1, parent->rson);
        push_up(parent);
    }
    Tp query(long left, long right, long part_r, long part_l, node* parent) {
        if(cover(left, right, part_l, part_r))
            return parent->data;
        push_down(parent, part_l, part_r);
        Tp res = 0;
        long mid = part_l + part_r >> 1;
        if(left <= mid) res += query(left, right, mid, part_l, parent->lson);
        if(right > mid) res += query(left, right, part_r, mid + 1, parent->rson);
        return res;
    }
    constexpr seg_tree() :root(new node) {}
    seg_tree(const Tp* arr, long len) :root(new node) { build(arr, root, 1, len); }
    seg_tree(const seg_tree& tree) :root(new node) { *root = tree.root; }
    ~seg_tree() { delete root; }
};
int main() {
    using namespace std;
    long n, m, op, l, r, k;
    cin >> n >> m;
    long* arr = new long[n + 1];
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    seg_tree tree(arr, n);
    delete[] arr;
    while(m--) {
        cin >> op;
        if(op == 1) {
            cin >> l >> r >> k;
            tree.adjust(l, r, k, n, 1, tree.root);
        }
        else {
            cin >> l >> r;
            cout << tree.query(l, r, n, 1, tree.root) << endl;
        }
    }
    return 0;
}

by zhujiajun2013 @ 2024-07-24 14:16:25

@wfirstzhang 谢了