P7549 [BJWC2017] 神秘物质

· · 题解

\text{Solution}

插入一个新能源和合并成为一个新的就文艺平衡树基本操作，分裂出对应区间，合并就先删除掉以前的，之后再插入。 max 的话维护下子树最大值和最小值即可。但 min 怎么维护？

我们加入插进来数 x ,原来有 a , b 两数。

则原来: a-b ，现在 max(a,x)-min(b,x) ,我们发现这个式子单调不降，所以我们要答案区间长度越小越好，所以答案区间是2。意味着我们需要维护相邻两数的绝对值差（极差是非负数）

如何在 fhq 上维护相邻的数呢？ 只需要记录下子树向左/右能最远扩展到的值即可。 那么当前左边的数是不是左子树向右最远扩展的值，右边同理。

\text{Code}

#include <bits/stdc++.h>

#define N (int)(1e5+5)
#define int long long
#define inf (int)(2e18)

using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

struct FHQ {
    int ls,rs,val,rad,sz,lres,rres,mires,mx,mi;
    FHQ() {
        ls=rs=val=rad=sz=lres=rres=mires=mx=mi=0;
    }
}t[N<<2];
int tot,rt;
void push_up(int cur) {
    int ls=t[cur].ls,rs=t[cur].rs;
    t[cur].sz=t[ls].sz+t[rs].sz+1;
    t[cur].mx=t[cur].mi=t[cur].lres=t[cur].rres=t[cur].val;
    t[cur].mires=inf;
    if(ls) {
        t[cur].mi=min(t[cur].mi,t[ls].mi);
        t[cur].mx=max(t[cur].mx,t[ls].mx);
        t[cur].lres=t[ls].lres;
        t[cur].mires=min(t[cur].mires,min(abs(t[ls].rres-t[cur].val),t[ls].mires));
    }
    if(rs) {
        t[cur].mi=min(t[cur].mi,t[rs].mi);
        t[cur].mx=max(t[cur].mx,t[rs].mx);
        t[cur].rres=t[rs].rres;
        t[cur].mires=min(t[cur].mires,min(abs(t[rs].lres-t[cur].val),t[rs].mires)); 
    }
}

void split(int cur,int num,int &x,int &y) {
    if(!cur) return x=y=0,void();
    if(t[t[cur].ls].sz+1<=num) {
        x=cur;
        split(t[cur].rs,num-t[t[cur].ls].sz-1,t[cur].rs,y);
    } else {
        y=cur;
        split(t[cur].ls,num,x,t[cur].ls);
    }
    push_up(cur);
}

int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(t[x].rad<t[y].rad) {
        t[x].rs=merge(t[x].rs,y);
        push_up(x); return x;
    } else {
        t[y].ls=merge(x,t[y].ls);
        push_up(y); return y;
    }
}

int newp(int x) {
    ++tot; t[tot].rad=rand(); t[tot].val=x; t[tot].sz=1; t[tot].mires=inf;
    t[tot].mi=t[tot].mx=t[tot].rres=t[tot].lres=x;
    return tot;
}

void ins(int pos,int v) {
    int r1,r2;
    split(rt,pos,r1,r2);
    rt=merge(merge(r1,newp(v)),r2);
}

void remerge(int pos,int v) {
    int r1,r2,r3;
    split(rt,pos+1,r1,r2); split(r1,pos-1,r1,r3);
    rt=merge(merge(r1,newp(v)),r2);
}

int query1(int l,int r) {
    int r1,r2,r3,res;
    split(rt,r,r2,r1); split(r2,l-1,r3,r2);
    res=t[r2].mx-t[r2].mi;
    rt=merge(merge(r3,r2),r1);
    return res;
}

int query2(int l,int r) {
    int r1,r2,r3,res;
    split(rt,r,r2,r1); split(r2,l-1,r3,r2);
    res=t[r2].mires;
    rt=merge(merge(r3,r2),r1);
    return res;
}

void DEBUG(int cur) {
    if(t[cur].ls) DEBUG(t[cur].ls);
    cout<<t[cur].val<<endl;
    if(t[cur].rs) DEBUG(t[cur].rs);
}

signed main() {
    srand(998244353); //srand((rand()<<3)*(rand()<<2));
    ++tot; t[1].val=inf; t[1].mi=inf; t[1].mx=-1; t[1].mires=inf;
    int n,m,x,y; char op[10]; n=rd(); m=rd();
    for(int i=1;i<=n;i++) {
        x=rd(); ins(i-1,x);
    }
//  DEBUG(rt);
    while(m--) {
        scanf("%s",op); x=rd(); y=rd();
        if(op[1]=='e') {
            remerge(x,y);
        } else if(op[1]=='n') {
            ins(x,y);
        } else if(op[1]=='a') {
            printf("%lld\n",query1(x,y));
        } else if(op[1]=='i') {
            printf("%lld\n",query2(x,y));
        }
    }
    return 0;
}