线段树求助
查看原帖
线段树求助
818475
ChpyX2楼主2024/10/23 19:38

出问题了但是不知道哪里错(((

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,m,c,a,b,t[maxn],w[maxn],tag[maxn];
int ls(int p){
    return p*2;
}
int rs(int p){
    return p*2+1;
}
void push_up(int p,int pl,int pr){
    t[p]=t[pl]+t[pr];
    return;
}
void addtag(int p,int pl,int pr){
    if(!tag[p])tag[p]=1;
    else tag[p]=0;
    t[p]=pr-pl+1-t[p];
    return;
}
void push_down(int p,int pl,int pr){
    if(!tag[p])return;
    int mid=(pl+pr)>>1;
    addtag(ls(p),pl,mid);
    addtag(rs(p),mid+1,pr);
    tag[p]=0;
}
void init(int p,int pl,int pr){
    if(pl==pr){
        t[pl]=w[pl];
        return;
    }
    int mid=(pl+pr)>>1;
    init(ls(p),pl,mid);
    init(rs(p),mid+1,pr);
    push_up(p,pl,pr);
    return;
}
int look(int l,int r,int p,int pl,int pr){
    if(l<=pl&&pr<=r){
        return t[p];
    }
    int mid=(pl+pr)>>1;
    int res=0;
    push_down(p,pl,pr);
    if(l<=pl&&mid<=r)res+=look(l,r,ls(p),pl,mid);
    if(l<=mid+1&&pr<=r)res+=look(l,r,rs(p),mid+1,pr);
    push_up(p,pl,pr);
    return res;
}
void update(int l,int r,int p,int pl,int pr){
    if(l<=pl&&pr<=r){
        addtag(p,pl,pr);
        return;
    }
    int mid=(pl+pr)>>1;
    if(l<=mid)update(l,r,ls(p),pl,mid);
    if(mid+1<=r)update(l,r,rs(p),mid+1,pr);
    return; 
}
int main(){
    cin>>n>>m;
    init(1,1,n);
    for(int i=1;i<=m;i++){
        cin>>c>>a>>b;
        if(c==0){
            update(a,b,1,1,n);
        }else{
            cout<<look(a,b,1,1,n)<<'\n';
        }
    }
    return 0;
}
//from chpyx2

感谢

2024/10/23 19:38
加载中...