有毒啊这splay!!!!!

回复帖子

@DOTA第一人 2018-12-21 13:33 回复
#include<iostream>
#include<cstdio>
#include<algorithm>
#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))
#define is(ch) (ch>='0'&&ch<='9')
#define iabs(a)     ( ( (a)<0 )?(-(a)):(a) )
#define LL long long

using namespace std;

inline void read(int &x)
{
    x=0;char ch=getchar();bool f=0;
    for (;!is(ch);ch=getchar()) f|=(ch=='-');
    for (; is(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    x=f?-x:x;
}
inline void read(LL &x)
{
    x=0;char ch=getchar();bool f=0;
    for (;!is(ch);ch=getchar()) f|=(ch=='-');
    for (; is(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    x=f?-x:x;
}
const int N=5e5+50;
int n,m,root,tot;
LL tr[N<<2],Min=1e10,Mina=1e10,d[N],he[N];
struct data{int fa,ch[2];LL s;}t[N<<1];
inline bool get(int x){return t[t[x].fa].ch[1]==x;}
inline void sc(int fa,int ro,bool ft){t[ro].fa=fa;t[fa].ch[ft]=ro;}
inline void rotate(int ro)
{
    int fa=t[ro].fa;bool ft=get(ro);
    if (fa!=root)   sc(t[fa].fa,ro,get(fa));    
                else {root=ro;t[ro].fa=0;}
    sc(fa,t[ro].ch[ft^1],ft);sc(ro,fa,ft^1);
}
void splay(int u,int v)
{
    if (u==v)   return;
    for (int fa;(fa=t[u].fa)!=v;rotate(u))
    {
        if (t[fa].fa==v){rotate(u);break;}
        rotate(get(fa)==get(u)?fa:u);   
    }
}
void insert(LL x)
{
    if (root==0)    {root=++tot;t[tot].s=x;return;}
    int ro=0,i=root;
    for (;i&&t[i].s!=x;i=t[i].ch[x>t[i].s]) ro=i;
    if (i==0)   t[++tot].s=x,sc(ro,tot,x>t[ro].s),i=tot;
    splay(i,0);
}
void updates()
{
    int ro=t[root].ch[0];
    while (t[ro].ch[1]) ro=t[ro].ch[1];
    Min=imin(Min,iabs(t[ro].s-t[root].s));
    ro=t[root].ch[1];
    while (t[ro].ch[0]) ro=t[ro].ch[0];
    Min=imin(Min,iabs(t[ro].s-t[root].s));
}
void update(int ro,int L,int R,int li,LL val)
{
    if (L>li||R<li) return;
    if (L==R)   
    {
        tr[ro]=val;
        return;
    }
    int Mid=(L+R)>>1;
    update(ro<<1,L,Mid,li,val);
    update(ro<<1|1,Mid+1,R,li,val);
    tr[ro]=imin(tr[ro<<1],tr[ro<<1|1]);
}
int main()
{
    read(n);read(m);
    d[0]=d[n+1]=1e10;
    insert(1e10);insert(-1e10);
    for (int i=1;i<=n;++i)
    {
        read(d[i]);he[i]=d[i];
        update(1,1,n,i,iabs(d[i-1]-d[i]));
        insert(d[i]);updates();
    }
    char A[200];LL x,y;
    for (int i=1;i<=m;++i)  
    {
        scanf("%s",A);
        if (A[0]=='I')
        {
            read(x);read(y);
            Mina=imin(Mina,iabs(he[x]-y));he[x]=y;
            update(1,1,n,x+1,iabs(d[x+1]-y));
            insert(y);updates();
        }else
        if (A[4]=='G')  printf("%lld\n",imin(tr[1],Mina));
        else printf("%lld\n",Min);
    }
    return 0;
}

有毒啊,为什么一直只对一个点

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。