线段树

/* http://acm.cug.edu.cn/problem.php?cid=1176&pid=1 */
// 区间赋值为0/1,区间的值取反
//线段树动态开点

//  区间翻转0/1+区间赋值0/1+区间求和的双标记动态开点线段树.html

#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=5e4+5;
int rev[maxn*2*35],cov[maxn*2*35],sum[maxn*2*35],ls[maxn*2*35],rs[maxn*2*35],a[maxn],tot;

void push_son(int&son,int l,int r,int covrt,int revrt){
    if(son==0) {
        son=++tot;
        cov[son]=-1;
        rev[son]=0;
        sum[son]=0;
        ls[son]=0;
        rs[son]=0;
    }
    if(covrt!=-1){
        sum[son]=(r-l+1)*covrt;
        cov[son]=covrt;
        rev[son]=0;
    }
    if(revrt!=0){
        sum[son]=(r-l+1)-sum[son];
        rev[son]^=1;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls[rt],l,ml,cov[rt],rev[rt]);
    push_son(rs[rt],mr,r,cov[rt],rev[rt]);
    cov[rt]=-1; rev[rt]=0;
}

void push_up(int rt,int l,int r){
    sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}

void build(int&rt,int l,int r){
    rt=tot=0;
    push_son(rt,l,r,-1,0);
}

void update(int rt,int l,int r,int ql,int qr,int d,int type){
    if(ql<=l&&r<=qr){
        if(type==1) push_son(rt,l,r,-1,1);//rev
        if(type==2) push_son(rt,l,r, d,0);//cover
    }
    else{
        push_down(rt,l,r);
        if(ml>=ql) update(ls[rt],l,ml,ql,qr,d,type);
        if(mr<=qr) update(rs[rt],mr,r,ql,qr,d,type);
        push_up(rt,l,r);
    }
}

int query(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    else{
        push_down(rt,l,r);
        int ret=0;
        if(ml>=ql) ret+=query(ls[rt],l,ml,ql,qr);
        if(mr<=qr) ret+=query(rs[rt],mr,r,ql,qr);
        return ret;
    }
}

离散化方法线段树

/*

3 6 
1 1 1 
1 1 4
1 2 2 
1 2 4 
1 3 3 
1 3 4


*/




#include<bits/stdc++.h>
using namespace std;

vector<int>disc;
int getid(int x){
    return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;
}

//hdu 4578
#define ls (rt<<1)
#define rs (ls|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=55555*6;
int rev[maxn<<2],cov[maxn<<2],sum[maxn<<2],a[maxn];

void push_son(int son,int l,int r,int covrt,int revrt){
    if(covrt!=-1){
        sum[son]=((disc[r-1+1]-1)-disc[l-1]+1)*covrt;
        cov[son]=covrt;
        rev[son]=0;
    }
    if(revrt!=0){
        sum[son]=((disc[r-1+1]-1)-disc[l-1]+1)-sum[son];
        rev[son]^=1;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls,l,ml,cov[rt],rev[rt]);
    push_son(rs,mr,r,cov[rt],rev[rt]);
    cov[rt]=-1; rev[rt]=0;
}

void push_up(int rt,int l,int r){
    sum[rt]=sum[ls]+sum[rs];
}

void build(int rt,int l,int r){
    cov[rt]=-1;
    rev[rt]=0;
    if(l==r){
        sum[rt]=0;
    }
    else{
        build(ls,l,ml);
        build(rs,mr,r);
        push_up(rt,l,r);
    }
}

void update(int rt,int l,int r,int ql,int qr,int d,int type){
    if(l!=r) push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        if(type==1) push_son(rt,l,r,-1,1);//rev
        if(type==2) push_son(rt,l,r, d,0);//cover
    }
    else{
        if(ml>=ql) update(ls,l,ml,ql,qr,d,type);
        if(mr<=qr) update(rs,mr,r,ql,qr,d,type);
        push_up(rt,l,r);
    }
}

int query(int rt,int l,int r,int ql,int qr){
    if(l!=r) push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    else{
        int ret=0;
        if(ml>=ql) ret+=query(ls,l,ml,ql,qr);
        if(mr<=qr) ret+=query(rs,mr,r,ql,qr);
        return ret;
    }
}

int read(){
    int ret=0,fu=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') fu=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9') {
        ret=(ret<<1)+(ret<<3)+(ch^48);
        ch=getchar();
    }
    return ret*fu;
}


int L[maxn],R[maxn],OP[maxn];

int main(){
    int n=read();
    int q=read();
    for(int i=0;i<q;i++) {
        L[i]=read();
        R[i]=read();
        OP[i]=read();
        disc.push_back(L[i]);
        disc.push_back(R[i]);
        disc.push_back(L[i]+1);
        disc.push_back(R[i]+1);
        disc.push_back(L[i]-1);
        disc.push_back(R[i]-1);
    }
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());

    build(1,1,disc.size());
    for(int i=0;i<q;i++){
        int l=getid(L[i]);
        int r=getid(R[i]);
        int op=OP[i];
        if(op==1) update(1,1,disc.size(),l,r,0,2);
        if(op==2) update(1,1,disc.size(),l,r,1,2);
        if(op==3) update(1,1,disc.size(),l,r,1,1);
        if(op==4) printf("%d\n",query(1,1,disc.size(),l,r));
    }
}