这是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
还是我的动态开点线段树写假了?