STO Meatherm orz
by SisconHL @ 2020-01-31 22:42:27
Meatherm Orz
by ieeqwq @ 2020-01-31 22:46:33
用 cin 读入 string？还行
@[Meatherm](/user/108949)
by ieeqwq @ 2020-01-31 22:49:55
@[wzsCD](/user/127284) 于是我改了一发2333
```cpp
# include <bits/stdc++.h>
# define rr register
# define lc(x) tree[x].son[0]
# define rc(x) tree[x].son[1]
const int N=500010;
struct Node{
int val;
int lval,rval;
int minx;
int son[2];
int rnd;
int size;
}tree[N*8];
int st[N],en[N];
int cnt;
int rta;
int rtv;
int n,m;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
inline int abs(int x){
return x>0?x:-x;
}
/*inline int& lc(int x){
return tree[x].son[0];
}
inline int& rc(int x){
return tree[x].son[1];
}*/
inline void update(int x){
tree[x].minx=1e9;
if(lc(x))
tree[x].lval=tree[lc(x)].lval,tree[x].minx=std::min(tree[x].minx,std::min(tree[lc(x)].minx,abs(tree[x].val-tree[lc(x)].rval)));
else
tree[x].lval=tree[x].val;
if(rc(x))
tree[x].rval=tree[rc(x)].rval,tree[x].minx=std::min(tree[x].minx,std::min(tree[rc(x)].minx,abs(tree[x].val-tree[rc(x)].lval)));
else
tree[x].rval=tree[x].val;
// tree[x].minx=std::min(std::min(tree[lc(x)].minx,tree[rc(x)].minx),std::min(abs(tree[x].val-tree[rc(x)].lval),abs(tree[x].val-tree[lc(x)].rval)));
tree[x].size=tree[lc(x)].size+tree[rc(x)].size+1;
return;
}
inline void NewNode(int &x,int v){
x=++cnt;
tree[x].lval=tree[x].rval=tree[x].val=v;
tree[x].minx=1e9;
tree[x].rnd=rand();
tree[x].size=1;
return;
}
void split(int now,int v,int &x,int &y){
if(!now){
x=y=0;
return;
}
// update(now);
if(tree[now].val<=v){
x=now;
split(rc(now),v,rc(x),y);
update(x);
}else{
y=now;
split(lc(now),v,x,lc(y));
update(y);
}
return;
}
void merge(int &now,int x,int y){
if(!x||!y){
now=x|y;
return;
}
// update(x),update(y);
if(tree[x].rnd<tree[y].rnd){
now=x;
merge(rc(now),rc(x),y);
update(now);
}else{
now=y;
merge(lc(now),x,lc(y));
update(now);
}
return;
}
inline void Insert(int &rt,int v){
int x,a,b;
NewNode(x,v);
split(rt,v,a,b);
merge(a,a,x);
merge(rt,a,b);
return;
}
inline void Delete(int &rt,int v){
int a,b,c,d;
split(rt,v-1,a,b);
split(b,v,c,d);
merge(c,lc(c),rc(c));
merge(b,c,d);
merge(rt,a,b);
return;
}
inline int getans(int x){
while(lc(x)){
x=lc(x);
}
return tree[x].val;
}
void prints(int x){
if(x<0)
putchar('-'),x=-x;
if(x>9)
prints(x/10);
putchar(x%10+'0');
return;
}
int main(void){
srand(114514);
tree[0].minx=1e9;
tree[0].lval=tree[0].rval=tree[0].val=1e9;
n=read(),m=read();
for(rr int i=1;i<=n;++i){
st[i]=en[i]=read();
if(i>1)
Insert(rta,abs(st[i]-st[i-1]));
Insert(rtv,st[i]);
}
/* puts("Seque a is");
print(rtv);
puts("");
puts("Seque b is");
print(rta);
puts("");*/
char opt[10];
int x,v;
while(m--){
scanf("%s",opt);
if(opt[0]=='I'){
x=read(),v=read();
if(x<n)
Delete(rta,abs(st[x+1]-en[x])),Insert(rta,abs(st[x+1]-v));
Insert(rta,abs(en[x]-v));
Insert(rtv,v);
en[x]=v;
}else if(opt[4]=='G'){
prints(getans(rta));
puts("");
}else{
prints(tree[rtv].minx);
puts("");
}
/* puts("Seque a is");
print(rtv);
puts("");
puts("Seque b is");
print(rta);
puts(""); */
}
return 0;
}
```
加 O2 85，不加 70 /kk
by Meatherm @ 2020-01-31 22:51:02
% Meatherm
by tiger0133 @ 2020-01-31 23:00:35
@[Meatherm](/user/108949) 太 草 了
帮您卡过了
```cpp
# include <bits/stdc++.h>
# define lc(x) tree[x].son[0]
# define rc(x) tree[x].son[1]
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
const int N=500010;
struct Node{
int val;
int lval,rval;
int minx;
int son[2];
int rnd;
int size;
}tree[N<<3];
int st[N],en[N];
int cnt;
int rta;
int rtv;
int n,m;
inline int min(register int a,register int b) {
return a<b?a:b;
}
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=(res<<3)+(res<<1)+(c^48);
return res*f;
}
inline int abs(register int x){
return x>0?x:-x;
}
/*inline int& lc(int x){
return tree[x].son[0];
}
inline int& rc(int x){
return tree[x].son[1];
}*/
inline void update(register int x){
tree[x].minx=1e9;
if(lc(x))
tree[x].lval=tree[lc(x)].lval,tree[x].minx=min(tree[x].minx,min(tree[lc(x)].minx,abs(tree[x].val-tree[lc(x)].rval)));
else
tree[x].lval=tree[x].val;
if(rc(x))
tree[x].rval=tree[rc(x)].rval,tree[x].minx=min(tree[x].minx,min(tree[rc(x)].minx,abs(tree[x].val-tree[rc(x)].lval)));
else
tree[x].rval=tree[x].val;
// tree[x].minx=std::min(std::min(tree[lc(x)].minx,tree[rc(x)].minx),std::min(abs(tree[x].val-tree[rc(x)].lval),abs(tree[x].val-tree[lc(x)].rval)));
tree[x].size=tree[lc(x)].size+tree[rc(x)].size+1;
return;
}
inline void NewNode(register int &x,register int v){
x=++cnt;
tree[x].lval=tree[x].rval=tree[x].val=v;
tree[x].minx=1e9;
tree[x].rnd=rand();
tree[x].size=1;
return;
}
void split(register int now,register int v,register int &x,register int &y){
if(!now){
x=y=0;
return;
}
// update(now);
if(tree[now].val<=v){
x=now;
split(rc(now),v,rc(x),y);
update(x);
}else{
y=now;
split(lc(now),v,x,lc(y));
update(y);
}
return;
}
void merge(register int &now,register int x,register int y){
if(!x||!y){
now=x|y;
return;
}
// update(x),update(y);
if(tree[x].rnd<tree[y].rnd){
now=x;
merge(rc(now),rc(x),y);
update(now);
}else{
now=y;
merge(lc(now),x,lc(y));
update(now);
}
return;
}
inline void Insert(register int &rt,register int v){
int x,a,b;
NewNode(x,v);
split(rt,v,a,b);
merge(a,a,x);
merge(rt,a,b);
return;
}
inline void Delete(register int &rt,register int v){
int a,b,c,d;
split(rt,v-1,a,b);
split(b,v,c,d);
merge(c,lc(c),rc(c));
merge(b,c,d);
merge(rt,a,b);
return;
}
inline int getans(register int x){
while(lc(x)){
x=lc(x);
}
return tree[x].val;
}
void prints(register int x){
if(x<0)
putchar('-'),x=-x;
if(x>9)
prints(x/10);
putchar(x%10+'0');
return;
}
int main(void){
srand(114514);
tree[0].minx=1e9;
tree[0].lval=tree[0].rval=tree[0].val=1e9;
n=read(),m=read();
for(register int i=1;i<=n;++i){
st[i]=en[i]=read();
if(i>1)
Insert(rta,abs(st[i]-st[i-1]));
Insert(rtv,st[i]);
}
/* puts("Seque a is");
print(rtv);
puts("");
puts("Seque b is");
print(rta);
puts("");*/
char opt[10];
register int x,v;
while(m--){
scanf("%s",opt);
if(opt[0]=='I'){
x=read(),v=read();
if(x<n)
Delete(rta,abs(st[x+1]-en[x])),Insert(rta,abs(st[x+1]-v));
Insert(rta,abs(en[x]-v));
Insert(rtv,v);
en[x]=v;
}else if(opt[4]=='G'){
prints(getans(rta));
putchar('\n');
}else{
prints(tree[rtv].minx);
putchar('\n');
}
/* puts("Seque a is");
print(rtv);
puts("");
puts("Seque b is");
print(rta);
puts(""); */
}
return 0;
}
```
by ⚡小林孑⚡ @ 2020-01-31 23:03:16
% $\rm M\color{red}eatherm$
by XeCtera @ 2020-01-31 23:14:30
@[脱发自动机](/user/119959) 太强了 %%%
by Meatherm @ 2020-02-01 09:11:15
@[Meatherm](/user/108949) fAKe
by ⚡小林孑⚡ @ 2020-02-01 21:38:52