比赛 2025.3.8 评测结果 AAAAAAAAAAAAAA
题目名称 线段覆盖 最终得分 100
用户昵称 徐诗畅 运行时间 0.976 s
代码语言 C++ 内存使用 4.76 MiB
提交时间 2025-03-08 09:07:29
显示代码纯文本
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=2e5+5;
  4. struct tree{
  5. int l,r,num,len,tag; //num:黑区间个数 len:黑区间长度 tag: 被全部覆盖几次 l:左端是否有1
  6. }t[N<<2];
  7. int len,n;
  8. void merge(int p,int l,int r){
  9. if(t[p].tag){
  10. t[p].l=t[p].r=t[p].num=1;
  11. t[p].len=r-l+1;
  12. }
  13. else{
  14. t[p].l=t[p<<1].l; t[p].r=t[p<<1|1].r;
  15. t[p].num=t[p<<1].num+t[p<<1|1].num;
  16. if(t[p<<1|1].l==1&&t[p<<1].r==1) t[p].num--;
  17. t[p].len=t[p<<1].len+t[p<<1|1].len;
  18. }
  19. }
  20. void update(int p,int l,int r,int L,int R,int d){
  21. if(L<=l&&R>=r){
  22. t[p].tag+=d;
  23. if(l==r){
  24. if(t[p].tag>0) t[p].l=t[p].r=t[p].num=t[p].len=1;
  25. else t[p].l=t[p].r=t[p].num=t[p].len=0;
  26. }
  27. else merge(p,l,r);
  28. return;
  29. }
  30. int mid=(l+r)>>1;
  31. if(L<=mid) update(p<<1,l,mid,L,R,d);
  32. if(R>mid) update(p<<1|1,mid+1,r,L,R,d);
  33. merge(p,l,r);
  34. }
  35. int main(){
  36. freopen("xdfg.in","r",stdin);
  37. freopen("xdfg.out","w",stdout);
  38. scanf("%d%d",&len,&n);
  39. while(n--){
  40. int op,a,T; scanf("%d%d%d",&op,&a,&T);
  41. if(op==1) update(1,1,len,a,a+T-1,1);
  42. else update(1,1,len,a,a+T-1,-1);
  43. printf("%d %d\n",t[1].num,t[1].len);
  44. }
  45. return 0;
  46. }
  47.