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