没搞懂，线段树理论复杂度应该是 $O(n \log n + m \log n)$ 的啊，应该显著大于并查集的 $O(n+m)$.

// Author:zymooll

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define int long long
using namespace std;
int read(){
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=s*10+c-'0';
		c=getchar();
	}
	return s*w;
}
void print(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10)print(x/10);
	putchar(x%10+'0');
	return;
}
int n,m;
struct Node{
    int l,r,bcnt,wcnt,flag;
}t[400010];
int ncnt;
int newnode(int l,int r){
    int p=++ncnt;
    t[p].bcnt=(r-l)+1;
    return p;
}
int modify(int p,int l,int r,int L,int R){
    if(!p)p=newnode(l,r);
    if(L<=l&&r<=R){
        t[p].flag=1;
        t[p].bcnt=0;
        t[p].wcnt=(r-l)+1;
        return p;
    }
    int mid=(l+r)/2;
    if(L<=mid&&!t[t[p].l].flag)t[p].l=modify(t[p].l,l,mid,L,R);
    if(R>mid&&!t[t[p].r].flag)t[p].r=modify(t[p].r,mid+1,r,L,R);
    if(t[p].l&&t[p].r){
        t[p].wcnt=t[t[p].l].wcnt+t[t[p].r].wcnt;
        t[p].bcnt=t[t[p].l].bcnt+t[t[p].r].bcnt;
    }
    else if(t[p].l){
        t[p].wcnt=t[t[p].l].wcnt;
        t[p].bcnt=t[t[p].l].bcnt+(r-(mid+1))+1;
    }
    else if(t[p].r){
        t[p].wcnt=t[t[p].r].wcnt;
        t[p].bcnt=(mid-l)+1+t[t[p].r].bcnt;
    }
    return p;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read();
    int root=newnode(1,n);
    while(m--){
        int l=read(),r=read();
        modify(root,1,n,l,r);
        print(t[1].bcnt),putchar('\n');
    }
	return 0;
}

time:100ms mem:808k