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

const int MX=200010;

struct node{
    int l,r,cv,ct,ln;
    bool lf,rt;
    int ad;
}s[MX*4];
void pd(int u);
void upd(int u){
    node&n=s[u];
    if(n.cv>0){
        n.ct=1;
        n.ln=n.r-n.l+1;
        n.lf=n.rt=1;
    }else{
        if(n.l==n.r){
            n.ct=0;
            n.ln=0;
            n.lf=n.rt=0;
        }else{
            pd(u);
            node&l=s[u<<1];
            node&r=s[u<<1|1];
            n.ct=l.ct+r.ct;
            if(l.rt&&r.lf)n.ct-=1;
            n.ln=l.ln+r.ln;
            n.lf=(l.cv>0)?1:l.lf;
            n.rt=(r.cv>0)?1:r.rt;
        }
    }
}


void pd(int u){
    node&n=s[u];
    if(n.ad==0)return;
    node&l=s[u<<1];
    node&r=s[u<<1|1];
    l.cv+=n.ad;
    l.ad+=n.ad;
    r.cv+=n.ad;
    r.ad+=n.ad;
    upd(u<<1);
    upd(u<<1|1);
    n.ad=0;
}


void bd(int u,int l,int r){
    s[u].l=l;
    s[u].r=r;
    s[u].cv=0;
    s[u].ct=0;
    s[u].ln=0;
    s[u].lf=0;
    s[u].rt=0;
    s[u].ad=0;
    if(l==r)return;
    int m=(l+r)>>1;
    bd(u<<1,l,m);
    bd(u<<1|1,m+1,r);
}

void ud(int u,int a,int b,int v){
    node&n=s[u];
    if(a>n.r||b<n.l)return;
    if(a<=n.l&&n.r<=b){
        n.cv+=v;
        n.ad+=v;
        upd(u);
        return;
    }
    pd(u);
    ud(u<<1,a,b,v);
    ud(u<<1|1,a,b,v);
    upd(u);
}

int main(){
	ios::sync_with_stdio(false);
		    cin.tie(0);
    freopen("xdfg.in","r",stdin);
    freopen("xdfg.out","w",stdout);
    int L,n;
    cin>>L>>n;
    bd(1,0,L-1);
    for(int i=0;i<n;++i){
        int m,a,T;
        cin>>m>>a>>T;
        if(T==0){
            cout<<s[1].ct<<" "<<s[1].ln<<endl;
            continue;
        }
        int b=a+T-1;
        a=max(a,0);
        b=min(b,L-1);
        if(a>b){
            cout<<s[1].ct<<" "<<s[1].ln<<endl;
            continue;
        }
        int v=(m==1)?1:-1;
        ud(1,a,b,v);
        cout<<s[1].ct<<" "<<s[1].ln<<endl;
    }
    return 0;
}