RE on #18 求调
查看原帖
RE on #18 求调
1690315
DPOI楼主2025/8/1 15:23
#include<bits/stdc++.h>
#define lc(x) tr[x].son[0]
#define rc(x) tr[x].son[1]
#define vc(x) tr[x].val
using namespace std;
const int N=1e7+5; 
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)){
		if (ch=='-') 
			f=-1;
		ch=getchar();
	}
	while (isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if (x<0)putchar('-'),x=-x;
	if (x>9)write(x/10);
	putchar(x%10+'0');
}
struct node{
    int son[2]={0,0}; 
    int val=0;
    int tag=0;  
}tr[N];
int tot=1; 
int root=1; 

inline void push_down(int x,int l,int r){
    if(!tr[x].tag) return;
    int mid=(l+r)>>1;
    if(!lc(x))lc(x)=++tot;
    tr[lc(x)].val=(tr[x].tag-1)*(mid-l+1);
    tr[lc(x)].tag=tr[x].tag;
    if(!rc(x))rc(x)=++tot;
    tr[rc(x)].val=(tr[x].tag-1)*(r-mid);
    tr[rc(x)].tag=tr[x].tag;
    tr[x].tag=0;
}

inline void update(int x,int l,int r,int L,int R,int k){
    if(L<=l&&r<=R){
        tr[x].val=(k-1)*(r-l+1);
        tr[x].tag=k;
        return;
    }
    push_down(x,l,r);
    int mid=(l+r)>>1;
    if(L<=mid){
        if(!lc(x)) lc(x)=++tot;
        update(lc(x),l,mid,L,R,k);
    }
    if(R>mid){
        if(!rc(x)) rc(x)=++tot;
        update(rc(x),mid+1,r,L,R,k);
    }
    tr[x].val=tr[lc(x)].val+tr[rc(x)].val;
}

int main(){
    int n,q;n=read(),q=read();
    tr[root].val=n; 
    tr[root].tag=2;
    while(q--){
        int l=read(),r=read(),k=read();
        update(root,1,n,l,r,k);
        write(tr[root].val);
        putchar('\n');
    }
}
2025/8/1 15:23
加载中...