P1110 [ZJOI2007]报表统计
皎月半洒花
2018-05-10 21:32:07
这个题是真毒瘤……我足足调试了19个小时,换了四种不同的写法,跑去问了机房里炒鸡厉害的大佬$qyf$3次才把它在$TLE$的条件下开$O_2AC$了$ORZZZZ$.
代码量$7k$(由于不会写成员函数所以代码长的很)
所以我是真的菜。
哦,这道题的难度在我这个不会写成员函数的蒟蒻看来,应该算是一道好题了,因为它并没有其他的紫题那样水。
哦,您觉得简单,那您强好了。
那么其实很显然,这个题我们可以用堆(失败),可以用$STL$ 里的$set$,也可以用两棵平衡树。而在这里我由于不想手写堆,所以用的$STL$结果炸了。
那么,一棵平衡树维护最小不相邻差值,一棵平衡树维护最小相邻差值,前者不带删除,后者带删除。
## 维护不相邻最小差值:
每次插入一个数时,找它的前驱后继,然后更新答案变量$minn$.
## 维护相邻最小差值:
我们记录一下原序列每个元素之后插入的元素中最后插入的数。然后每次$insert$之后删除一次插入两次即可。
$Code$:
我辣鸡,凑合着看吧。
当然,我不会写成员函数(其实是一开始没用成员函数之后,写了一半懒得用了)。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 500001
#define Inf 2147483600
#define ll long long
using namespace std;
struct tree{
ll v,sub,son[2],f,cnt;
}s[MAXN<<1],S[MAXN<<1];
ll minn=Inf,root,wz,num[MAXN],base[MAXN],i,now,res,pre,suffix,fa;
ll _res,_wz,_root,_now,_fa,_rank,_old_root;
inline long long qread(){
long long num=0;
char ch=getchar();
while(!isdigit(ch)){
ch=getchar();
}
while(isdigit(ch)){
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num;
}
/*___________________________________________________________*/
inline ll my_abs(ll x){
return x>0?x:-x;
}
inline bool which(ll x){
return x==s[s[x].f].son[1];
}
inline void update(ll x){
if(x){
s[x].sub=s[x].cnt;
if(s[x].son[0])s[x].sub+=s[s[x].son[0]].sub;
if(s[x].son[1])s[x].sub+=s[s[x].son[1]].sub;
}
}
inline void rotate(ll x){
ll fnow=s[x].f,ffnow=s[fnow].f;
bool w=which(x);
s[fnow].son[w]=s[x].son[w^1];
s[s[fnow].son[w]].f=fnow;
s[fnow].f=x;
s[x].f=ffnow;
s[x].son[w^1]=fnow;
if(ffnow){
s[ffnow].son[s[ffnow].son[1]==fnow]=x;
}
update(fnow);
}
inline void splay(ll x,ll goal){
for(ll qwq;(qwq=s[x].f)!=goal;rotate(x)){
if(s[qwq].f!=goal){
rotate(which(x)==which(qwq)?qwq:x);
}
}
if(goal==0){
root=x;
}
}
inline void insert(ll x){
if(!root){
wz++;
s[wz].son[0]=s[wz].son[1]=s[wz].f=0;
root=wz;
s[wz].sub=s[wz].cnt++;
s[wz].v=x;
return ;
}
now=root,fa=0;
while(1){
if(x==s[now].v){
s[now].cnt++;
update(now);
update(fa);
splay(now,0);
break;
}
fa=now;
now=s[now].son[s[now].v<x];
if(!now){
wz++;
s[wz].son[0]=s[wz].son[1]=0;
s[wz].f=fa;
s[wz].sub=s[wz].cnt++;
s[fa].son[s[fa].v<x]=wz;
s[wz].v=x;
update(fa);
splay(wz,0);
break;
}
}
}
inline ll find_pre(){
res=s[s[root].son[0]].v,now=s[root].son[0];
if(s[root].cnt>1)
return s[root].v;
while(s[now].son[1]){
res=s[s[now].son[1]].v;
now=s[now].son[1];
}
return res;
}
inline ll find_suffix(){
res=s[s[root].son[1]].v,now=s[root].son[1];
if(s[root].cnt>1)
return s[root].v;
while(s[now].son[0]){
res=s[s[now].son[0]].v;
now=s[now].son[0];
}
return res;
}
inline void init_insert(ll now){
insert(now);
suffix=find_suffix();
pre=find_pre();
if(suffix!=Inf){
minn=min(minn,my_abs(suffix-now));
}
if(pre!=-Inf){
minn=min(minn,my_abs(pre-now));
}
}
/*___________________________________________________________*/
inline bool S_which(ll x){
return x==S[S[x].f].son[1];
}
inline void S_clear(ll x){
S[x].cnt=S[x].son[1]=S[x].son[0]=S[x].f=S[x].sub=S[x].v=0;
if(x==-wz)_wz--;
}
inline void S_update(ll x){
if(x){
S[x].sub=S[x].cnt;
if(S[x].son[0])S[x].sub+=S[S[x].son[0]].sub;
if(S[x].son[1])S[x].sub+=S[S[x].son[1]].sub;
}
}
inline void S_rotate(ll x){
ll fnow=S[x].f,ffnow=S[fnow].f;
bool w=S_which(x);
S[fnow].son[w]=S[x].son[w^1];
S[S[fnow].son[w]].f=fnow;
S[fnow].f=x;
S[x].f=ffnow;
S[x].son[w^1]=fnow;
if(ffnow){
S[ffnow].son[S[ffnow].son[1]==fnow]=x;
}
S_update(fnow);
}
inline void S_splay(ll x,ll goal){
for(ll qwq;(qwq=S[x].f)!=goal;S_rotate(x)){
if(S[qwq].f!=goal){
S_rotate(S_which(x)==S_which(qwq)?qwq:x);
}
}
if(goal==0){
_root=x;
}
}
inline void S_insert(ll x){
if(!_root){
_wz++;
S[_wz].son[0]=S[_wz].son[1]=S[_wz].f=0;
_root=_wz;
S[_wz].sub=S[_wz].cnt++;
S[_wz].v=x;
return ;
}
_now=_root,_fa=0;
while(1){
if(x==S[_now].v){
S[_now].cnt++;
S_update(_now);
S_update(_fa);
S_splay(_now,0);
break;
}
_fa=_now;
_now=S[_now].son[S[_now].v<x];
if(!_now){
_wz++;
S[_wz].son[0]=S[_wz].son[1]=0;
S[_wz].f=_fa;
S[_wz].sub=S[_wz].cnt++;
S[_fa].son[S[_fa].v<x]=_wz;
S[_wz].v=x;
S_update(_fa);
S_splay(_wz,0);
break;
}
}
}
inline ll S_find_pre(){
_now=S[_root].son[0];
while(S[_now].son[1]){
_now=S[_now].son[1];
}
return _now;
}
inline ll S_find_rank(ll x){
_now=_root,_rank=0;
while(1){
if(x<S[_now].v){
_now=S[_now].son[0];
}
else {
_rank+=(S[_now].son[0]?S[S[_now].son[0]].sub:0);
if(x==S[_now].v){
S_splay(_now,0);
return _rank+1;
}
_rank+=S[_now].cnt;
_now=S[_now].son[1];
}
}
}
inline ll S_find_num(ll x){
_now=_root;
while(1){
if(S[_now].son[0]&&x<=S[S[_now].son[0]].sub){
_now=S[_now].son[0];
}
else {
ll temp=(S[_now].son[0]?S[S[_now].son[0]].sub:0)+S[_now].cnt;
if(x<=temp)return S[_now].v;
x-=temp;
_now=S[_now].son[1];
}
}
}
inline void S_delete(ll x){
int hhh=S_find_rank(x);
if(S[_root].cnt>1){
S[_root].cnt--;
S_update(_root);
return ;
}
if(!S[_root].son[0]&&!S[_root].son[1]){
S_clear(_root);
_root=0;
return ;
}
if(!S[_root].son[0]){
_old_root=_root;
_root=S[_root].son[1];
S[_root].f=0;
S_clear(_old_root);
return ;
}
if(!S[_root].son[1]){
_old_root=_root;
_root=S[_root].son[0];
S[_root].f=0;
S_clear(_old_root);
return ;
}
int left_max=S_find_pre(),_old_root=_root;
S_splay(left_max,0);
S[_root].son[1]=S[_old_root].son[1];
S[S[_old_root].son[1]].f=_root;
S_clear(_old_root);
S_update(_root);
}
/*___________________________________________________________*/
int main(){
ll a,n,m,b;
char s[20];
cin>>n>>m;
insert(Inf);
insert(-Inf);
for(i=1;i<=n;i++){
base[i]=num[i]=qread();
if(i!=1)S_insert(my_abs(base[i-1]-base[i]));
init_insert(base[i]);
}
for(register int i=1;i<=m;i++){
scanf("%s",s);
int ss=strlen(s);
if(ss==7) {
printf("%d\n",S_find_num(1));
continue;
}
else if(ss==12){
printf("%d\n",minn);
continue;
}
else {
a=qread();
b=qread();
if(a<n){
S_delete(my_abs(num[a]-base[a+1]));
S_insert(my_abs(b-base[a+1]));
}
S_insert(my_abs(b-num[a]));
init_insert(b);
num[a]=b;
continue;
}
}
}
```
# $\color{gold}Think$ $~$ $\color{silver}Twice$ $,$ $\color{cyan}Code$ $~$ $\color{red}Once.$