比赛 |
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;
}