P1110 [ZJOI2007]报表统计

时间：2023-03-09 15:17:10
P1110 [ZJOI2007]报表统计

题目描述

Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。

经过仔细观察，小Q发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。

在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作：

  • INSERT i k：在原数列的第i个元素后面添加一个新元素k；如果原数列的第i个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子）
  • MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值
  • MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）

例如一开始的序列为5, 3, 1。

执行操作INSERT 2 9将得到：5, 3, 9, 1，此时MIN_GAP为22，MIN_SORT_GAP为22。

再执行操作INSERT 2 6将得到：5, 3, 9, 6, 1

注意这个时候原序列的第2个元素后面已经添加了一个9，此时添加的6应加在9的后面。这个时候MIN_GAP为2，MIN_SORT_GAP为1。

于是小Q写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？

输入输出格式

输入格式：

第一行包含两个整数N，M，分别表示原数列的长度以及操作的次数。

第二行为N个整数，为初始序列。

接下来的M行每行一个操作，即INSERT i k，MIN_GAP，MIN_SORT_GAP 中的一种（无多余空格或者空行）。


输出格式：

对于每一个MIN_GAP和MIN_SORT_GAP命令，输出一行答案即可。

输入输出样例

输入样例#1： 
3 5

5 3 1

INSERT 2 9

MIN_SORT_GAP

INSERT 2 6

MIN_GAP

MIN_SORT_GAP
输出样例#1： 
2

2

1

说明

对于30%的数据，N ≤ 1000 ,M ≤ 5000
对于100%的数据，N ,M ≤500000
对于所有的数据，序列内的整数不超过5×108。

时限2s

Solution：

　　本题splay+堆（好水啊，乱打的代码都能AC~）。

　　分析题目：

　　　　操作1，加入一个数，只会改变相邻的关系，所以数组模拟随便乱搞维护下相邻关系。

　　　　操作2，加入一个数，改变的是两对相邻的差值，所以可以直接用带修改的堆去维护（pbds大法好！）。

　　　　操作3，由于是维护全局最小值，那么只需要在加入数时，在其插入二叉搜索树的遍历过程中，与访问过的节点更新下答案，当然为了保证树的平衡，选用平衡树写写就行了。

代码：

/*Code by 520 -- 9.17*/

#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>

#include<ext/pb_ds/priority_queue.hpp>

#define il inline

#define ll long long

#define RE register

#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)

#define son(x) (x==ch[fa[x]][1])

using namespace std;

using namespace __gnu_pbds;

const int N=;

int n,m,a[N<<][],tot,val[N<<];

int root,ch[N][],fa[N],cnt,date[N];

int minn=0x7fffffff;

struct node{

    int ls,rs,val;

    bool operator < (const node &a) const {return val>a.val;}

};

typedef __gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag> heap;

heap q;

heap::point_iterator id[N];

int gi(){

    int a=;char x=getchar();bool f=;

    while((x<''||x>'')&&x!='-') x=getchar();

    if(x=='-') x=getchar(),f=;

    while(x>=''&&x<='') a=(a<<)+(a<<)+(x^),x=getchar();

    return f?-a:a;

}

il void rotate(int x){

    int y=fa[x],z=fa[y],b=son(x),c=son(y),a=ch[x][!b];

    z?ch[z][c]=x:root=x; fa[x]=z;

    if(a) fa[a]=y; ch[y][b]=a;

    ch[x][!b]=y,fa[y]=x;

}

il void splay(int x,int i){

    while(fa[x]!=i){

        RE int y=fa[x],z=fa[y];

        if(z==i) rotate(x);

        else {

            if(son(x)==son(y)) rotate(y),rotate(x);

            else rotate(x),rotate(x);

        }

    }

}

void insert(int &rt,int x){

    if(!rt) {rt=++cnt,date[cnt]=x;return;}

    if(date[rt]==x) {minn=;return;}

    if(x<date[rt])

        insert(ch[rt][],x),fa[ch[rt][]]=rt,minn=min(minn,abs(date[rt]-x));

    else

        insert(ch[rt][],x),fa[ch[rt][]]=rt,minn=min(minn,abs(date[rt]-x));

}

int main(){

    int pos,x; char s[];

    n=gi(),m=gi(),tot=n;

    For(i,,n) {

        val[i]=gi(),insert(root,val[i]),splay(cnt,);

        if(i!=) a[i][]=i;

        if(i!=n) a[i][]=i;

    }

    For(i,,n) id[i]=q.push(node{i,i+,abs(val[i]-val[i-])});

    while(m--){

        scanf("%s",s);

        if(s[]=='I') {

            pos=gi(),val[++tot]=gi(),insert(root,val[tot]),splay(cnt,);

            int tp=a[pos][];

            id[tot]=q.push(node{tot,tp,abs(val[tp]-val[tot])});

            if(pos!=n) q.modify(id[pos+],node{pos+,tot,abs(val[pos+]-val[tot])});

            a[pos+][]=tot,a[pos][]=tot;

        }

        else if(strlen(s)==) printf("%d\n",q.top().val);

        else printf("%d\n",minn);

    }

    return ;

}

相关文章