_皎月半洒花 的博客

_皎月半洒花 的博客

反抗命运的镇魂曲停歇之前,你绝对不可以说我懦弱,绝对不可以说我没有殊死一搏。

P1110 [ZJOI2007]报表统计

posted on 2018-05-10 21:32:07 | under 平时做题+数据结构 |

这个题是真毒瘤……我足足调试了19个小时,换了四种不同的写法,跑去问了机房里炒鸡厉害的大佬 $qyf$ 3次才把它在 $TLE$ 的条件下开 $O_2AC$ 了 $ORZZZZ$ .

代码量 $7k$ (由于不会写成员函数所以代码长的很)

所以我是真的菜。

哦,这道题的难度在我这个不会写成员函数的蒟蒻看来,应该算是一道好题了,因为它并没有其他的紫题那样水。

哦,您觉得简单,那您强好了。

那么其实很显然,这个题我们可以用堆(失败),可以用 $STL$ 里的 $set$ ,也可以用两棵平衡树。而在这里我由于不想手写堆,所以用的 $STL$ 结果炸了。

那么,一棵平衡树维护最小不相邻差值,一棵平衡树维护最小相邻差值,前者不带删除,后者带删除。

维护不相邻最小差值:

每次插入一个数时,找它的前驱后继,然后更新答案变量 $minn$ .

维护相邻最小差值:

我们记录一下原序列每个元素之后插入的元素中最后插入的数。然后每次 $insert$ 之后删除一次插入两次即可。

$Code$ :

我辣鸡,凑合着看吧。

当然,我不会写成员函数(其实是一开始没用成员函数之后,写了一半懒得用了)。

#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.$