CF915E
洛谷链接
题目大意（懒狗直接偷的题面）：
从现在到学期结束还有 \(n\) 天(从 \(1\) 到 \(n\) 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出 \(q\) 个指令，每个指令可以用三个参数 \(l,r,k\) 描述：
- 如果 \(k=1\)，那么从 \(l\) 到 \(r\) （包含端点）的所有日子都变成非工作日。
- 如果 \(k=2\)，那么从 \(l\) 到 \(r\) （包含端点）的所有日子都变成工作日。
统计每个指令下发后，剩余的工作日天数。
输入格式：
第一行一个整数 \(n\)，第二行一个整数 \(q\) \((1\le n\le 10^9,\;1\le q\le 3\cdot 10^5)\)，分别是剩余的天数和指令的个数。
接下来 \(q\) 行，第 \(i\) 行有 \(3\) 个整数 \(l_i,r_i,k_i\)，描述第 \(i\) 个指令 \((1\le l_i,r_i\le n,\;1\le k\le 2)\)。
输出格式：
输出 \(q\) 行，第 \(i\) 行表示第 \(i\) 个指令被下发后剩余的工作日天数。
样例输入 #1
4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2
样例输出 #1
2
0
2
3
1
4
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 16e6+10;
inline int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int n,m,root=0;
int cnt;
struct T{
int l,r,val,lazy;
}t[MAXN];
int newnode(){
cnt++;
t[cnt].lazy=-1;
return cnt;
}
void update(int p){
t[p].val=t[t[p].l].val+t[t[p].r].val;
}
void pushdown(int l,int r,int p){
if(l==r||t[p].lazy==-1){
return;
}
if(!t[p].l){
t[p].l=newnode();
}
if(!t[p].r){
t[p].r=newnode();
}
int mid=(l+r)>>1;
t[t[p].l].val=(mid-l+1)*t[p].lazy;
t[t[p].r].val=(r-mid)*t[p].lazy;
t[t[p].l].lazy=t[p].lazy;
t[t[p].r].lazy=t[p].lazy;
t[p].lazy=-1;
}
void change(int l,int r,int &p,int x,int y,int k){
if(r<x||y<l) {
return ;
}
if(!p) p=newnode();
if(x<=l&&r<=y){
t[p].lazy=k;
t[p].val=(r-l+1)*k;
return;
}
pushdown(l,r,p);
int mid=(l+r)>>1;
change(l,mid,t[p].l,x,y,k);
change(mid+1,r,t[p].r,x,y,k);
//update(p);
t[p].val=t[t[p].l].val+t[t[p].r].val;
}
signed main(){
n=read();
m=read();
change(1,n,root,1,n,1);
for(int i=1;i<=m;i++){
int l,r,op;
l=read();
r=read();
op=read();
if(op==1){
change(1,n,root,l,r,0);
}
else{
change(1,n,root,l,r,1);
}
printf("%d\n",t[1].val);
}
return 0;
}
