Codeforces 915 E Physical Education Lessons

題目描述

This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn't attended a single lesson!

Since Alex doesn't want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:

There are?

Help Alex to determine the number of working days left after each order!

輸入輸出格式

輸入格式：

The first line contains one integer? $integer?qq?(?1<=n<=10^{9}1<=n<=109?,?1<=q<=3·10^{5}1<=q<=3?105) — the number of days left before the end of the term, and the number of orders, respectively.$

Then? $integers?l_{i}li??,?r_{i}ri??and?k_{i}ki??representing?ii?-th order (?1<=l_{i}<=r_{i}<=n1<=li?<=ri?<=n?,?1<=k_{i}<=21<=ki?<=2?).$

輸出格式：

Print?

輸入輸出樣例

輸入樣例#1：?

輸出樣例#1：?

2
0
2
3
1
4

下午去湘江邊的橘子洲van了一圈，然而明天就要去雅禮報道了hhhh


很明顯n<=10^9肯定不能用普通的線段樹做，雖然可能離散化完了之后會有奇淫技巧能做。。。。
但是我首先想到的是動態開點直接打標機下傳、、、畢竟線段樹一次操作涉及的節點數是log n級別的，就算是區間操作+需要標記下傳的話，
需要的空間也只是常數大了大，復雜度依然是log n的，而且很多操作還會有重復的區間呢。

于是我就動態開點+線段樹打tag瞎做了做，，，本地垃圾筆記本3s才能過極端數據，，，，不過codeforces的評測機跑的飛快，硬生生的縮成了300+ms。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define maxn 200005
using namespace std;
struct node{int lc,rc;int tag,sum;
}nil[maxn*71];
int n,le,ri,tot;
int q,opt,cnt=1;inline void work(int v,int tmp,int len){if(tmp==-1) nil[v].tag=-1,nil[v].sum=0;else nil[v].tag=1,nil[v].sum=len;
}inline void pushdown(int o,int l,int r){int ls=nil[o].lc,rs=nil[o].rc,mid=l+r>>1;if(nil[o].tag==-1){nil[o].tag=0;work(ls,-1,mid-l+1);work(rs,-1,r-mid);}else if(nil[o].tag==1){nil[o].tag=0;work(ls,1,mid-l+1);work(rs,1,r-mid);}
}void update(int u,int l,int r){if(l>=le&&r<=ri){int pre=nil[u].sum;work(u,opt,r-l+1);tot+=nil[u].sum-pre;return;}if(!nil[u].lc) nil[u].lc=++cnt;if(!nil[u].rc) nil[u].rc=++cnt;pushdown(u,l,r);int mid=l+r>>1;if(le<=mid) update(nil[u].lc,l,mid);if(ri>mid) update(nil[u].rc,mid+1,r);nil[u].sum=nil[nil[u].lc].sum+nil[nil[u].rc].sum;
}int main(){
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);int root=1;nil[1]=(node){0,0,0,0};scanf("%d%d",&n,&q);while(q--){scanf("%d%d%d",&le,&ri,&opt);opt=(opt==2?-1:1);update(root,1,n);printf("%d\n",n-tot);}return 0;
}

轉載于:https://www.cnblogs.com/JYYHH/p/8406106.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/390250.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/390250.shtml
英文地址，請注明出處：http://en.pswp.cn/news/390250.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！