P1110 [ZJOI2007]报表统计 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 罗进瑶
    能否问下set为什么要加INF和-INF 不加的话会出什么错误?
  • cmd2001
    不加的话会在迭代器++--的时候出现莫名其妙的RE。话说这还是我退役之前的题解呢QAQ(我当时这么强的吗)。
  • 镉八君
    还有大牛分站的时候的远古题解QWQ 手写平衡树发现题意理解错了然后开始学习stl党路过
  • wuzhaoxin
    multiset好像是红黑树(平衡树的一种)
  • maoxiangui
    qwq 太神了
  • bjxdw
    666
  • 董鲤鱼烧
    stl大佬,顶一下
  • duyi
    STL大佬!!!
  • duyi
    思路很清楚,注意点也提的很好
  • EndSaH
    花了两小时想出来准备写题解 发现一个一模一样的- -
作者: cmd2001 更新时间: 2017-11-02 16:53  在Ta的博客查看 举报    30  
首先这题不用手写平衡树,不用堆,只用两个数组,两个multiset和一个变量就好了......
然而语文神题不好看懂......
首先理解题意:我们无非就是把这个序列分成n段,在每一段结尾插入新元素。
比如说样例,我们可以理解为:
[5][3,9,6][1]。
其中括号括起来的为每一段所含的元素。
我们首先维护两个数组,st[]和ed[]表示每一段开头的元素和结尾的元素。我们在更新相邻差值的时候只用考虑新插入的值和原结尾的差以及和下一段开头的差就好了。
这样,我们维护两个 multiset<int> ,一个叫 full ,表示全部 元素(存在的数值)。另一个叫 delta ,表示全部 差值 。
插入新元素的时候,我们把他在 full 中找到前驱后继分别作差,更新 排序后最小差 。
然后在 delta 中删除 现在本段结尾与下一段开头的差 ,插入 新值与当前本段结尾的差 和 新值与下一段开头的差 。
注意必须用 multiset , 因为同样的键值可能出现多次。
另外删除时要 erase 掉 find 后的 iterator ,不能直接 erase 数值,否则就把出现多次的同一个数值全删了......
最后上代码。大牛分站O2信仰跑。
#include<cstdio>
#include<set>
#include<cstdlib>
#include<cctype>
using namespace std;
const int maxn=5e5+1e2;
const int inf=0x3f3f3f3f;

multiset<int> delta,full;
int st[maxn],ed[maxn];
int srt=inf;
int n,m;

inline void update_srt(int x)
{
    multiset<int>::iterator it = full.lower_bound(x);
    int nw = *it - x;
    --it;
    nw = min( nw , x - *it );
    srt = min( srt , nw );
    full.insert(x);
}

inline void replac(int pos,int x)
{
    delta.insert( abs( x - ed[pos] ) );
    if( pos != n )
        delta.erase( delta.find( abs( st[pos+1] - ed[pos] ) ) ),
        delta.insert( abs( st[pos+1] - x ) );
    ed[pos] = x;
}

inline int getint()
{
    int ret = 0 , fix = 1;
    char ch = getchar();
    while( !isdigit(ch) )
    {
        if( ch == '-' )
            fix = -1;
        ch = getchar();
    }
    while( isdigit(ch) )
        ret = ret * 10 + ( ch - '0' ),
        ch = getchar();
    return ret * fix;
}

int main()
{
    static char str[1<<5];
    n = getint() , m = getint();
    for(int i=1;i<=n;i++)
        st[i] = ed[i] = getint();

    full.insert(inf),
    full.insert(-inf);
    for(int i=1;i<n;i++)
        delta.insert( abs( st[i+1] - ed[i] ) );
    for(int i=1;i<=n;i++)
        update_srt(st[i]);
    for(int i=1,pos,x;i<=m;i++)
    {
        scanf("%s",str);
        if( *str == 'I' )
        {
            pos = getint() , x = getint();
            update_srt(x);
            replac(pos,x);
        }
        else if( str[4] == 'S' )
            printf("%d\n",srt);
        else
            printf("%d\n",*delta.begin());
    }
    return 0;
}

评论

  • Victorique
    就凭那个卡常小技巧,你也该上去。
  • gigo_64
    活捉巨佬
作者: onglu 更新时间: 2019-01-11 12:51  在Ta的博客查看 举报    14  

看了半天怎么就没有Splay+堆的题解呢。。
题意是很简单的。。
就是一开始有$n$个元素,每个元素相当于一个队列,总的序列是所有队列按顺序拼接起来的序列,有下面三种操作。
操作一:在原序列第$k$个队列插入一个$x$
操作二:查询总序列里面相邻元素的差值的绝对值的最小值。
操作三:查询总序列里面所有元素差值的绝对值的最小值。

第一个操作应该是建立在二,三操作的基础上进行的。。
我们先对二,三操作进行讨论。

第三个操作比较简单,我们只要建立一个平衡树,每次插入元素之后,查询这个元素和排名相邻的元素的差值,然后统计出最小值就可以了。

重点是第二个操作。
发现如果我们插入一个元素,这个元素会打破一对元素的相邻关系,并且建立两队相邻关系,每次的答案就是所有的相邻关系中差值最小的一对。
差值最小的一对很容易用堆来维护,我们的问题就变成了维护一个可以删除的堆。

这个堆也很容易实现。。
我们开两个堆,第一个堆储存已经插入的数,第二个堆储存已经删除的数,每次弹出时我们只需要判断两堆的堆顶是不是一样,如果一样就同时弹掉,直到堆顶不一样。

那么第一个操作就是这两个操作的结合了吧。。不讲了。。
注意平衡树判断前驱,后继的时候要注意判断当前元素是否有多个,如果有多个的话说明最小值是零。

同时有一个卡常小技巧。。
最小值是一直向着$0$贴近的,不会变成负数也不会变大,所以当我们发现最小值变成$0$的时候,我们就不需要再进行平衡树操作了(卡了这个之后我代码快了700ms)。
当然最开始的时候我们要对所有的数据进行初始化,确定每个数据在最终的数组中的位置。(不然用vector好像也是可以的,没试过,你们可以去试试)

下面就直接贴代码(常熟巨大不开氧气2336ms,开了氧气也是830ms)

#include <bits/stdc++.h>
#define fa(x) tree[x].fa
#define son(x,k) tree[x].ch[k]
#define cnt(x) tree[x].cnt
#define val(x) tree[x].val
#define siz(x) tree[x].siz
using namespace std;
const int N=5e6+1009;
const int inf=(1<<31)-1;
struct Hp{
    priority_queue<int>q1,q2;
    Hp(){
        while(!q1.empty())q1.pop();
        while(!q2.empty())q2.pop();
    }
    void Insert(int x){
        q1.push(-x);
    }
    void Delete(int x){
        q2.push(-x);
    }
    int Top(){
        while(!q2.empty()&&!q1.empty()){
            if(q1.top()!=q2.top())return -q1.top();
            q1.pop();q2.pop();
        }
    }
}Heap;
int read(){
    char c;int num,f=1;
    while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
    while(c=getchar(), isdigit(c))num=num*10+c-'0';
    return f*num;
}
int abs(int x){return x<0?-x:x;}
int rt,tot;
int n,m,pos[N],minn=(1<<31)-1;
int ord[N][10],a[N],b[N];

struct Node{
    int fa,ch[2],siz,cnt,val;
}tree[N];
bool chk(int x){return son(fa(x),1)==x;}
void update(int x){siz(x)=siz(son(x,0))+siz(son(x,1))+cnt(x);}
int New(int x,int pre){
    tot++;
    if(pre)son(pre,x>val(pre))=tot;
    son(tot,0)=son(tot,1)=0;
    cnt(tot)=siz(tot)=1;
    val(tot)=x;fa(tot)=pre;
    return tot;
}
void rotate(int x){
    int y=fa(x),z=fa(y),k=chk(x);
    son(z,chk(y))=x;fa(x)=z;
    son(y,k)=son(x,k^1);fa(son(x,k^1))=y;
    son(x,k^1)=y;fa(y)=x;
    update(y);update(x);
}
void splay(int x,int goal=0){
    while(fa(x)!=goal){
        int y=fa(x),z=fa(y);
        if(z!=goal){
            if(chk(y)==chk(x))rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if(!goal)rt=x;
}
void Insert(int x){
    int cur=rt,p=0;
    while(cur&&val(cur)!=x)
        p=cur,cur=son(cur,x>val(cur));
    if(cur)cnt(cur)++;
    else cur=New(x,p);
    splay(cur);
}
void Find(int x){
    if(!rt)return ;
    int cur=rt;
    while(son(cur,x>val(cur))&&val(cur)!=x)
        cur=son(cur,x>val(cur));
    splay(cur);
}
int Pre(int x){
    Find(x);
    if(val(rt)<x||(val(rt)==x&&cnt(rt)>1))return rt;
    int cur=son(rt,0);
    while(son(cur,1))cur=son(cur,1);
    return cur;
}
int Succ(int x){
    Find(x);
    if(val(rt)>x||(val(rt)==x&&cnt(rt)>1))return rt;
    int cur=son(rt,1);
    while(son(cur,0))cur=son(cur,0);
    return cur;
}
int main()
{
    n=read();m=read();
    Insert(inf);Insert(-inf);
    for(int i=1;i<=n;i++){
        int x=read();
        pos[i]=x;
        b[i]++;
    }
    for(int i=1;i<=m;i++){
        char c[19];
        scanf("%s",c);
        int len=strlen(c);
        if(len==6){
            ord[i][0]=1;
            ord[i][1]=read();
            ord[i][2]=read();
            b[ord[i][1]]++;
            ord[i][3]=b[ord[i][1]];
        }else if(len==7)ord[i][0]=2;
        else ord[i][0]=3;
    }
    for(int i=1;i<=n;i++){
        if(i!=1)Heap.Insert(abs(pos[i]-pos[i-1]));
        if(minn!=0){
            Insert(pos[i]);
            int xx=val(Succ(pos[i])),yy=val(Pre(pos[i]));
            if(xx!=inf&&xx!=-inf)minn=min(minn,xx-pos[i]);
            if(yy!=inf&&yy!=-inf)minn=min(minn,pos[i]-yy);
        }
        a[b[i-1]+1]=pos[i];
        b[i]+=b[i-1];
    }
    for(int i=1;i<=m;i++){
        if(ord[i][0]==1){
            if(minn!=0) Insert(ord[i][2]);
            a[b[ord[i][1]-1]+ord[i][3]]=ord[i][2];

            Heap.Insert(abs(a[b[ord[i][1]-1]+ord[i][3]]-a[b[ord[i][1]-1]+ord[i][3]-1]));
            Heap.Insert(abs(a[b[ord[i][1]-1]+ord[i][3]]-a[b[ord[i][1]]+1]));
            Heap.Delete(abs(a[b[ord[i][1]]+1]-a[b[ord[i][1]-1]+ord[i][3]-1]));
            if(minn!=0){
                int xx=val(Succ(ord[i][2])),yy=val(Pre(ord[i][2]));
                if(xx!=inf&&xx!=-inf)minn=min(minn,xx-ord[i][2]);
                if(yy!=inf&&yy!=-inf)minn=min(minn,ord[i][2]-yy);
            }
        }else if(ord[i][0]==2)
            printf("%d\n",Heap.Top());
        else printf("%d\n",minn);
    }
    return 0;
}

评论

  • cplusplus
    %%%%2
  • cplusplus
    %%%%2
  • cplusplus
    jican
  • Fading
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  • skicean
    没必要搞一颗splay?
  • Juan_feng
    舒老师tql!
  • 千年之狐_天才
    真香
作者: Treeloveswater 更新时间: 2017-05-06 19:30  在Ta的博客查看 举报    8  

超级大水题。竟然是省选难度的?

一棵无比简单的连update都不用写的splay+一个带删除的堆,完美搞定。

操作一:没必要搞一棵splay。我们只用开一个lq[500001][2]的数组记录这个点的前面和后面就行。

操作二:带修改的小根堆

操作三:把所有数扔到splay里,按大小为关键字,再插入的时候取个max的差值就好了。

完美解决,特别好写~

完结,撒花~

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int tot,n,m,a,k,minans=1e7;
struct node
{
    int data;
    node *son[2],*pre;
    bool judge();
    void setson(node *child,int lr);
}pool[1000001],*null,*root;
int heap1[1500001],delheap[1000001],lq[500001][3];
char s[25];
bool node::judge(){return pre->son[1]==this;}
void node::setson(node *child,int lr){son[lr]=child;if(child!=null)child->pre=this;}
node *getnew(int value)
{
    node *now=pool+ ++tot;
    now->data=value;
    now->pre=now->son[1]=now->son[0]=null;
    return now;
}
int ab(int x)
{
    return x<0?-x:x;
}
void rotate(node *&now)
{
    node *dad=now->pre,*grandfa=now->pre->pre;
    int lr=now->judge();
    dad->setson(now->son[lr^1],lr);
    now->setson(dad,lr^1);
    now->pre=grandfa;
    if(grandfa!=null) grandfa->son[grandfa->son[1]==dad?1:0]=now;
}
void splay(node *now,node *tar)
{
    for(;now->pre!=null;rotate(now))
    if(now->pre->pre!=tar)
    now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
    if(tar==null)root=now;
}
void in(int *heap,int value)
{
    heap[++heap[0]]=value;
    int now=heap[0],nxt;
    while(now>1)
    {
        nxt=now>>1;
        if(heap[nxt]<heap[now])break;
        swap(heap[nxt],heap[now]);
        now=nxt;
    }
}
void del(int *heap)
{
    heap[1]=heap[heap[0]--];
    int now=1,nxt;
    while(now*2<=heap[0])
    {
        nxt=now<<1;
        if(heap[nxt]>heap[nxt+1]&&nxt<heap[0])nxt++;
        if(heap[now]<heap[nxt])break;
        swap(heap[now],heap[nxt]);
        now=nxt;
    }
}
void insert(int value)
{
    node *newone=getnew(value);
    node *now=root,*last=null;
    while(now!=null)
    {
        last=now;
        if(ab(newone->data-now->data)<minans)minans=ab(newone->data-now->data);
        if(now->data>=newone->data) now=now->son[0];
        else now=now->son[1];
    }
    if(last==null) root=newone;
    else
    {
        if(ab(newone->data-last->data)<minans)minans=ab(newone->data-last->data);
        if(last->data>=newone->data) last->setson(newone,0);
        else last->setson(newone,1);
    }
}
int main()
{
    null=pool;
    null->data=0;
    null->pre=null->son[1]=null->son[0]=null;
    root=null;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&lq[i][1]);
        lq[i][2]=lq[i][1];
        if(i>1)in(heap1,ab(lq[i][1]-lq[i-1][2]));
        insert(lq[i][1]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        if(s[0]=='I')
        {
            scanf("%d%d",&a,&k);
            if(a<n)
            {
                in(delheap,ab(lq[a][2]-lq[a+1][1]));
                in(heap1,ab(k-lq[a+1][1]));
            }
            in(heap1,ab(k-lq[a][2]));
            lq[a][2]=k;
            insert(k);
        }
        else
        {
            int length=strlen(s);
            if(length<10)
            {
                while(heap1[1]==delheap[1])
                {
                    del(heap1);
                    del(delheap);
                }
                printf("%d\n",heap1[1]);
            }
            else
                printf("%d\n",minans);
        }
    }
}

评论

  • 还没有评论
作者: LinkedIn 更新时间: 2019-01-02 17:23  在Ta的博客查看 举报    4  

这是一份可以卡过去的纯$STL$

两个$multiset$,一个$adjoin$记录相邻的差值,一个$al$记录所有的元素

一个优先队列存所有元素的最小差值

一个$map$存$adjoin$中元素的出现个数

这题的插入比较奇怪

插入多次之后一个数后面的序列中中间的数就没有作用了,对答案起到影响的只有头尾元素,所以两个数组记录每个点后方序列的头和尾

每次插入操作都要更新,注意细节就好

由于$STL$用的很多

读优输优$O_2$一个都不能少

第一次$A$卡到了$2493ms$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <ctime>
#include <set>
#include <vector>
#include <iomanip>
#define A 1000010
#define B 2010

using namespace std;
typedef long long ll;
const int inf = 2000000000;
map<ll, ll> df;
multiset<ll> adjoin, al;
priority_queue<ll, vector<ll>, greater<ll> > q;
int n, m, s[A], e[A], x, y;
template<class T> void read(T &x) {
    x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
}
void operate1() {
    read(x); read(y);
    //更新相邻元素最小差值
    if (x != n) {
        int tmp = abs(e[x] - s[x + 1]);
        if (!--df[tmp]) adjoin.erase(tmp);
    }
    if (++df[abs(y - e[x])] == 1) adjoin.insert(abs(y - e[x]));
    if (++df[abs(y - s[x + 1])] == 1) adjoin.insert(abs(y - s[x + 1]));
    e[x] = y;
    //更新那个优先队列
    q.push(min(y - *--al.lower_bound(y), *al.lower_bound(y) - y));
    al.insert(y);
}
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main(int argc, char *argv[]) {
    read(n); read(m);
    al.insert(inf); al.insert(-inf);
    for (int i = 1; i <= n; i++) {
        read(x);
        q.push(min(x - *--al.lower_bound(x), *al.lower_bound(x) - x));
        al.insert(x);
        s[i] = e[i] = x;
        if (i == 1) continue;
        if (++df[abs(s[i] - s[i - 1])] == 1) adjoin.insert(abs(s[i] - s[i - 1]));
    }
    for (int i = 1; i <= m; i++) {
        char opt[12];
        scanf("%s", opt);
        switch (opt[4]) {
            case 'R' : operate1(); break;
            case 'S' : write(q.top()); puts(""); break;
            case 'G' : write(*adjoin.begin()); puts(""); break;
            default : break;
        }
    }
}

评论

  • 蒟蒻的蒋文轩
    好长
  • 汪锦程
    好长
作者: _皎月半洒花 更新时间: 2018-05-10 21:32  在Ta的博客查看 举报    5  

这个题是真毒瘤……我足足调试了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.$

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



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