动态开点线段树常数过大导致T? 求助
查看原帖
动态开点线段树常数过大导致T? 求助
209923
PRIMITIVE_LIGHTS楼主2022/7/3 10:27

这是AC代码

#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#define push_up(k) tr[k].w=tr[tr[k].lc].w+tr[tr[k].rc].w;
#define push_down(k,ll,rr){\
int ll1=ll,rr1=(ll+rr)>>1,ll2=((ll+rr)>>1)+1,rr2=rr;\
if(!tr[k].lc) tr[k].lc=++cnt;\
tr[tr[k].lc].w=tr[k].tag*(rr1-ll1+1),tr[tr[k].lc].tag=tr[k].tag;\
if(!tr[k].rc) tr[k].rc=++cnt;\
tr[tr[k].rc].w=tr[k].tag*(rr2-ll2+1),tr[tr[k].rc].tag=tr[k].tag;\
tr[k].tag=2;\
}
const int MAXN=16000000;
using namespace std;
struct seq{
    int w;int tag=2;
    int lc,rc;
}tr[MAXN];
int cnt=0,root;
int n,m;
int read(){
    int ans=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        ans=(ans<<1)+(ans<<3)+(ch^48);
        ch=getchar();
    }
    return ans*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void modify(int k,int ll,int rr,int l,int r,int v){
    if(ll>=l&&rr<=r){
        tr[k].w=v*(rr-ll+1);tr[k].tag=v;
        return ;
    }
    if(tr[k].tag!=2) push_down(k,ll,rr);
    int mid=(ll+rr)>>1;
    if(l<=mid) {
        if(!tr[k].lc) tr[k].lc=++cnt;
        modify(tr[k].lc,ll,mid,l,r,v);
    }
    if(r>mid){
        if(!tr[k].rc) tr[k].rc=++cnt;
        modify(tr[k].rc,mid+1,rr,l,r,v);
    }
    push_up(k);
}
int main(){
    n=read(),m=read();
    root=++cnt;
    modify(root,1,n,1,n,1);
    for(register int i=1;i<=m;i=-~i){
        int opt,x,y;
        x=read(),y=read(),opt=read();
        modify(root,1,n,x,y,opt-1);
        write(tr[root].w);puts("");
    }
}

令我无法理解的是为什么不加

#pragma GCC optimize(3)

会TLE on #19

还是我的动态开点线段树写假了?

2022/7/3 10:27
加载中...