比赛 2025.3.8 评测结果 AAAAAAAAAAAAAA
题目名称 线段覆盖 最终得分 100
用户昵称 wdsjl 运行时间 1.002 s
代码语言 C++ 内存使用 4.76 MiB
提交时间 2025-03-08 09:18:32
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int n,t;

struct tr{
	int sum,ceng;//sum段数ceng 层数 
	int lc,rc;//是否和左右相连 
	int len;
}tr[4*N];

void up(int o,int l,int r){
    if(tr[o].ceng>0){
        tr[o].lc=tr[o].rc=tr[o].sum=1;
        tr[o].len=r-l+1;
        return;
    }
    else{
        tr[o].lc=tr[o*2].lc;
        tr[o].rc=tr[o*2+1].rc;
        tr[o].len=tr[o*2].len+tr[o*2+1].len;
        tr[o].sum=tr[o*2].sum+tr[o*2+1].sum;
        if(tr[o*2].rc==1&&tr[o*2+1].lc==1)tr[o].sum--;
        return ;
    }
}

void add(int o,int l,int r,int ql,int qr,int v){
    if(l>=ql&&r<=qr){
        tr[o].ceng+=v;
        if(l==r){
            if(tr[o].ceng>0){
                tr[o].len=tr[o].lc=tr[o].rc=tr[o].sum=1;
                return;
            }
            else{
                tr[o].len=tr[o].lc=tr[o].rc=tr[o].sum=0;
                return;
            }
        }
        else{
            up(o,l,r);
            return;
        }
    }
    int mid=(l+r)>>1;
    if(mid>=ql)add(o*2,l,mid,ql,qr,v);
    if(mid<qr)add(o*2+1,mid+1,r,ql,qr,v);
    up(o,l,r);
}

int main(){
    freopen("xdfg.in","r",stdin);
    freopen("xdfg.out","w",stdout);
    scanf("%d%d",&n,&t);
    while(t--){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x==1){
            add(1,1,n,y,y+z-1,1);
        }
        else{
            add(1,1,n,y,y+z-1,-1);
        }
        printf("%d %d\n",tr[1].sum,tr[1].len);
    }
    return 0;
}