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的博客查看 举报    40  
首先这题不用手写平衡树,不用堆,只用两个数组,两个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
    活捉巨佬
  • 小跳蛙
    %T%%%%%
  • 小跳蛙
    QwQ
  • cmy962085349
    9 5 78 75 42 23 19 28 4 73 40 MIN_GAP INSERT 9 2 MIN_GAP INSERT 2 49 MIN_SORT_GAP 您的程序跑出来是0 2 2? 应该是3 3 2吧。
  • _Garbage
    忍不住喷射出我的评论(嗯 嗯 啊啊 爽)
  • 风随逐影
    @_Garbage 我怀疑你在开车,可惜没有证据
  • 神风OI队
    不是我为啥随手一个随机数据你就没了啊
作者: onglu 更新时间: 2019-01-11 12:51  在Ta的博客查看 举报    19  

看了半天怎么就没有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;
}

评论

  • 哥就是拽
    ORZ
  • zbtzbt
    666
  • Carl233
    %%%
  • cmy962085349
    2 3 79 41 INSERT 2 15 MIN_SORT_GAP MIN_GAP 您的答案是26 15 正确应该是26 26?
  • _Garbage
    忍不住喷射出我的评论(嗯 嗯 啊啊 爽)
作者: 一叶知秋。 更新时间: 2019-07-21 13:09  在Ta的博客查看 举报    7  

感谢 @cmy962085349 提供的hack数据,已经改对了。


先声明,我好像是题解里写双fhq treap里唯一能过的...(最后两个点啊)


思路:首先看题目,MIN_GAP_SORT明显是求它的前驱与后继(可能有相同的),所以就用平衡树,但是又要求两个相邻的数的差,就可以有再开一个平衡树存放差值

实现:抛开奇奇怪怪的的题面,主要考虑这三个操作:

1、INSERT i k:

这个很简单,用链表就行了(数组模拟的),但是要注意,插入的时候,要接着上一个在这插入的,还要做双向链表,数组要记得开两倍

最重要的是,插入了以后,这个数的前一个数与后一个数的差要在存放相邻两个数的差的fhq treap里删除,并插入这个数与前一个数的差和这个数与后一个数的差要存进去

2、MIN_GAP:

做完插入,就在存差的fhq treap查rank1好了(最左边的那个节点)

3、MIN_SORT_GAP:

为了避免查前驱与后继时出现自己(不是另一个与自己相同的数),所以插入时(分裂后,合并前,这样正好符合查前驱与后继的标准)就比较取小,询问时直接输出就好了

P.S. 这道题写两个平衡树过后面两个点很关键的是卡常(O2也随你了)!原本T后面两个点的代码加上 与用 char而不用string 就过了,所以,卡常有的时候还是很重要的!(或者我人丑常数大吧)

再P.S. 似乎经过 @cmy962085349 的hack数据更正以后,似乎并不需要过于卡常了(说明题解里双平衡树还是因为写错了而T了后面两个点),似乎不用cin与cout就能过,不需要加什么 register 了(虽然我还是加了

附上AC代码:

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
using namespace std;

struct tree{//存每个值的数(不是差)
    int size,val,dat,l,r;
}tr[1000005];//数组记得开两倍

int s_tr,root,n,m,x,y,z,a[1000005],b[1000005],c[1000005];

int min_sort_gap;//MIN_SORT_GAP的答案

inline int abs(int a){
    return a<0?-a:a;
}

inline int min(int a,int b){
    return a<b?a:b;
}

//fhq treap常规操作

inline int new_tr(int val){
    tr[++s_tr].val=val;
    tr[s_tr].size=1;
    tr[s_tr].dat=rand();
    return s_tr;
}

inline void update(int p){
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
}

void split(int p,int k,int &x,int &y){
    if(!p){
        x=y=0;
        return;
    }
    if(tr[p].val<=k)x=p,split(tr[p].r,k,tr[p].r,y);
    else y=p,split(tr[p].l,k,x,tr[p].l);
    update(p);
}

int merge(int x,int y){
    if(!x||!y)return x+y;
    if(tr[x].dat>tr[y].dat){
        tr[x].r=merge(tr[x].r,y);
        update(x);
        return x;
    }
    else {
        tr[y].l=merge(x,tr[y].l);
        update(y);
        return y;
    }
}

inline int Max(int x){//一棵fhq(可能是分裂后)中最大的
    while(tr[x].r)x=tr[x].r;
    return tr[x].val;
}

inline int Min(int y){//一棵fhq(可能是分裂后)中最大的
    while(tr[y].l)y=tr[y].l;
    return tr[y].val;
}

inline void insert(int val){
    split(root,val,x,y);
    if(tr[x].size)//要有才行
        min_sort_gap=min(min_sort_gap,abs(val-Max(x)));
    if(tr[y].size)//要有才行
        min_sort_gap=min(min_sort_gap,abs(Min(y)-val));
    root=merge(merge(x,new_tr(val)),y);
}

//存差值的fhq treap

struct tree1{
    int size,val,dat,l,r;
}tr1[1000005];

int s_tr1,root1;

inline int new_tr1(int val){
    tr1[++s_tr1].val=val;
    tr1[s_tr1].size=1;
    tr1[s_tr1].dat=rand();
    return s_tr1;
}

inline void update1(int p){
    tr1[p].size=tr1[tr1[p].l].size+tr1[tr1[p].r].size+1;
}

void split1(int p,int k,int &x,int &y){
    if(!p){
        x=y=0;
        return;
    }
    if(tr1[p].val<=k)x=p,split1(tr1[p].r,k,tr1[p].r,y);
    else y=p,split1(tr1[p].l,k,x,tr1[p].l);
    update1(p);
}

int merge1(int x,int y){
    if(!x||!y)return x+y;
    if(tr1[x].dat>tr1[y].dat){
        tr1[x].r=merge1(tr1[x].r,y);
        update1(x);
        return x;
    }
    else {
        tr1[y].l=merge1(x,tr1[y].l);
        update1(y);
        return y;
    }
}

inline void insert1(int val){
    split1(root1,val,x,y);
    root1=merge1(merge1(x,new_tr1(val)),y);
}

inline void delete_val(int val){//这棵fhq要能支持删除
    split1(root1,val,x,z);
    split1(x,val-1,x,y);
    y=merge1(tr1[y].l,tr1[y].r);
    root1=merge1(merge1(x,y),z);
}

inline int Min1(int y){
    while(tr1[y].l)y=tr1[y].l;
    return tr1[y].val;
}

char s[101];//卡常

inline int read(){//卡常
    int r=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return r*f;
}

int main(){
    srand(time(0));
    n=read(),m=read();
    min_sort_gap=1e9+10;
    for(register int i=1;i<=n;i++){//卡常
        a[i]=read();
        insert(a[i]);
    }
    for(register int i=1;i<n;i++)//卡常减少if
        insert1(abs(a[i+1]-a[i])),c[i]=i+1;
    for(register int i=2;i<=n;i++)//卡常减少if,n+1是因为可能在第n个后面插入
        b[i]=i-1;
    b[n+1]=n;
    int cnt=n;
    for(register int i=1;i<=m;i++){//卡常
        scanf("%s",s);
        if(s[0]=='I'){
            int j=read(),k=read();
            delete_val(abs(a[j+1]-a[b[j+1]]));//因为插入后不在一起了,删除
            insert1(abs(a[b[j+1]]-k));//插入后多了两个差值(不算删除的)
            if(j<n)insert1(abs(k-a[j+1]));//可能插在第n个的后面
            a[++cnt]=k;//放进数组,这件事一定要在上述操作以后做,不然若连续插入在第n个数以后就挂了,因为第一次cnt+1后会直接取代n+1,b[n+1]也就没什么用了
            b[cnt]=b[j+1];//数组模拟链表
            c[cnt]=j+1;
            c[b[j+1]]=cnt;//记得修改前一个与后一个的指向
            b[j+1]=cnt;
            insert(k);
        }
        else {
            if(s[4]=='G')printf("%d\n",Min1(root1));//整棵fhq里最小的
            else printf("%d\n",min_sort_gap);
        }
    }
    return 0;
}

再次感谢 @cmy962085349

完结偷偷撒花!(✿✿ヽ(°▽°)ノ✿)

评论

  • 蒟蒻的蒋文轩
    好长
  • 汪锦程
    好长
  • 小跳蛙
    %%%%%%%
  • _Garbage
    忍不住喷射出我的评论(嗯 嗯 啊啊 爽)
作者: _皎月半洒花 更新时间: 2018-05-10 21:32  在Ta的博客查看 举报    7  

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

评论

  • cplusplus
    %%%%2
  • cplusplus
    %%%%2
  • cplusplus
    jican
  • Fading
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  • skicean
    没必要搞一颗splay?
  • Juan_feng
    舒老师tql!
  • 千年之狐_天才
    真香
  • cmy962085349
    7 1 7 18 92 55 55 6 8 MIN_GAP 您的代码跑出来是2 正确应该是0吧。。
作者: Treeloveswater 更新时间: 2017-05-06 19:30  在Ta的博客查看 举报    10  

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

一棵无比简单的连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);
        }
    }
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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