TLE on #5 求卡常/求调
查看原帖
TLE on #5 求卡常/求调
1690315
DPOI楼主2025/8/1 14:46
#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=1e6+5;
struct node{
    int son[2];
    int val;
    int tag;
}tr[4*N];
int tot=0,a[N];
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');
}
inline void push_down(int x,int l,int r){
    if(!tr[x].tag)return;
    int m=(l+r)/2;
    if(!lc(x))lc(x)=++tot;
    if(!rc(x))rc(x)=++tot;
    tr[lc(x)].val=(m-l+1)*(tr[x].tag-1);
    tr[rc(x)].val=(r-m)*(tr[x].tag-1);
    tr[lc(x)].tag=tr[rc(x)].tag=tr[x].tag;
    tr[x].tag=0;
}

inline void build(int &x,int l,int r){
    x=++tot;
    if(l==r){
        tr[x].val=1;
        return;
    }
    int m=(l+r)/2;
    build(lc(x),l,m);
    build(rc(x),m+1,r);
    tr[x].val=tr[lc(x)].val+tr[rc(x)].val;
}

inline void uqd(int &x,int l,int r,int L,int R,int k){
    if(!x)x=++tot;
    if(R<l||L>r)return;
    if(L<=l&&r<=R){
        tr[x].val=(r-l+1)*(k-1);
        tr[x].tag=k;
        return;
    }
    push_down(x,l,r);
    int m=(l+r)/2;
    uqd(lc(x),l,m,L,R,k);
    uqd(rc(x),m+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();
    int rt=0;
    build(rt,1,n);
    while(q--){
        int l,r,k;l=read(),r=read(),k=read();
        uqd(rt,1,n,l,r,k);
        write(tr[rt].val);
        putchar('\n');
    }
    return 0;
}
2025/8/1 14:46
加载中...