线段树标记永久化..简单易懂代码量少
by Mystery_Peacock @ 2018-11-02 23:04:42
@[buer](/space/show?uid=25204) %%%可是不会qwq
by qsmoonzh @ 2018-11-02 23:08:04
@[qsmoonzh](/space/show?uid=96546) 线段树log的加inline会快吧
by codesonic @ 2018-11-02 23:08:13
@[codesonic](/space/show?uid=45443) 快了一点点，顺便%思考熊qwq
by qsmoonzh @ 2018-11-02 23:18:41
@[qsmoonzh](/space/show?uid=96546) 噫 那就短小操作参数加入register
by codesonic @ 2018-11-02 23:21:02
可以做到无pushdown操作..
```cpp
#include<bits/stdc++.h>
const int N=int(1e6)+10,INF=0x3f3f3f3f;
int n,m,R[N];
inline void inIO(int &x){
char ch;x=0;while(!isdigit(ch=getchar()));
do x=(x<<1)+(x<<3)+ch-'0';while(isdigit(ch=getchar()));
}
inline int min(int x,int y){
return x<y?x:y;
}
struct SegT{
struct Node{
int data,l,r,add;
inline void init(int x,int y,int z){
data=x,l=y,r=z,add=0;
}
}T[N*4];
inline void update(int x){
T[x].data=min(T[x<<1].data+T[x<<1].add,T[x<<1|1].data+T[x<<1|1].add);
}
void build(int x,int l,int r){
T[x].init(r-l?INF:R[l],l,r);
if(l-r){
int mid=l+r>>1;
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
update(x);
}
}
void modify(int x,int l,int r,int d){
if(T[x].l>r||T[x].r<l)return;
if(T[x].l>=l&&T[x].r<=r){
T[x].add+=d;return;
}
modify(x<<1,l,r,d),modify(x<<1|1,l,r,d);
update(x);
}
}_tree;
int main(){
inIO(n),inIO(m);
for(register int i=1;i<=n;++i)
inIO(R[i]);
_tree.build(1,1,n);
for(register int i=1;i<=m;++i){
int d,s,t;
inIO(d),inIO(s),inIO(t);
_tree.modify(1,s,t,-d);
if(_tree.T[1].data+_tree.T[1].add<0)return printf("-1\n%d\n",i),0;
}
return puts("0"),0;
}
```
by Mystery_Peacock @ 2018-11-02 23:42:04
@[buer](/space/show?uid=25204) %%%不过好像快不了多少qwq
by qsmoonzh @ 2018-11-03 11:53:04
表示线段树最慢的300$ms$
by SpXace @ 2018-11-05 07:41:43