借教室 Vijos 1782 NOIP2012 D2T2 Lazy 线段树-白红宇

借教室 Vijos 1782 NOIP2012 D2T2 Lazy 线段树

阅读量：5811 次

发布时间：2019-06-18

本文共 2595 字，大约阅读时间需要 8 分钟。

怎么说呢，最后一个点跑了1234ms但是vijos没给TLE，我就厚颜无耻地认为自己过了吧！

标准的lazy线段树写法，权当存个模版了！

#	状态	耗时	内存占用
#1	Accepted	4ms	380.0 KiB
#2	Accepted	4ms	348.0 KiB
#3	Accepted	3ms	384.0 KiB
#4	Accepted	4ms	372.0 KiB
#5	Accepted	4ms	360.0 KiB
#6	Accepted	4ms	348.0 KiB
#7	Accepted	42ms	3.219 MiB
#8	Accepted	57ms	3.734 MiB
#9	Accepted	76ms	3.836 MiB
#10	Accepted	96ms	2.375 MiB
#11	Accepted	104ms	2.859 MiB
#12	Accepted	116ms	2.492 MiB
#13	Accepted	150ms	4.25 MiB
#14	Accepted	116ms	3.082 MiB
#15	Accepted	440ms	18.121 MiB
#16	Accepted	619ms	17.84 MiB
#17	Accepted	859ms	17.824 MiB
#18	Accepted	943ms	16.742 MiB
#19	Accepted	1185ms	18.117 MiB
#20	Accepted	1234ms	18.461 MiB

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 template
          
            inline void read(T &_a){ 8 bool f=0;int _ch=getchar();_a=0; 9 while(_ch<'0' || _ch>'9'){ if(_ch=='-')f=1;_ch=getchar();}10 while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}11 if(f)_a=-_a;12 }13 14 const int maxn=1000001;15 struct fff16 {17 int minn,lazy;18 }node[(maxn<<2)+(maxn<<1)];19 int n,m;20 21 inline void pushup(int u)22 {23 node[u].minn=min(node[u<<1].minn,node[u<<1|1].minn);24 }25 26 inline void pushdown(int u)27 {28 if(node[u].lazy)29 {30 node[u<<1].lazy+=node[u].lazy;31 node[u<<1|1].lazy+=node[u].lazy;32 node[u<<1].minn-=node[u].lazy;33 node[u<<1|1].minn-=node[u].lazy;34 node[u].lazy=0;35 }36 }37 38 void build(int u,int l,int r)39 {40 if(l==r) { read(node[u].minn); return ; }41 int mid=(l+r)>>1;42 build(u<<1,l,mid);43 build(u<<1|1,mid+1,r);44 pushup(u);45 }46 47 int query(int u,int l,int r,int L,int R)48 {49 if(L<=l&&r<=R) return node[u].minn;50 pushdown(u);51 int mid=(l+r)>>1;52 if(R<=mid) return query(u<<1,l,mid,L,R);53 if(L>mid) return query(u<<1|1,mid+1,r,L,R);54 return min(query(u<<1,l,mid,L,R),query(u<<1|1,mid+1,r,L,R));55 }56 57 void update(int u,int l,int r,int L,int R,int val)58 {59 if(L<=l&&r<=R)60 {61 node[u].lazy+=val;62 node[u].minn-=val;63 return ;64 }65 pushdown(u);66 int mid=(l+r)>>1;67 if(L<=mid) update(u<<1,l,mid,L,R,val);68 if(R>mid) update(u<<1|1,mid+1,r,L,R,val);69 pushup(u);70 return ;71 }72 73 inline void out()74 {75 for (register int i=1;i<=n;++i)76 printf("%d ",query(1,1,n,i,i));putchar('\n');77 }78 79 int main()80 {81 read(n); read(m);82 build(1,1,n);83 // out();84 for (register int cas=1,d,s,j;cas<=m;++cas)85 {86 read(d); read(s); read(j);87 int num=query(1,1,n,s,j);88 // printf("[%d]\n",num);89 if(num