題目描述

Q的媽媽是一個(gè)出納，經(jīng)常需要做一些統(tǒng)計(jì)報(bào)表的工作。今天是媽媽的生日，小Q希望可以幫媽媽分擔(dān)一些工作，作為她的生日禮物之一。

經(jīng)過仔細(xì)觀察，小Q發(fā)現(xiàn)統(tǒng)計(jì)一張報(bào)表實(shí)際上是維護(hù)一個(gè)非負(fù)整數(shù)數(shù)列，并且進(jìn)行一些查詢操作。

在最開始的時(shí)候，有一個(gè)長(zhǎng)度為N的整數(shù)序列，并且有以下三種操作：

• INSERT i k：在原數(shù)列的第i個(gè)元素后面添加一個(gè)新元素k；如果原數(shù)列的第i個(gè)元素已經(jīng)添加了若干元素，則添加在這些元素的最后（見下面的例子）
• MIN_GAP：查詢相鄰兩個(gè)元素的之間差值（絕對(duì)值）的最小值
• MIN_SORT_GAP：查詢所有元素中最接近的兩個(gè)元素的差值（絕對(duì)值）

例如一開始的序列為5, 3, 1。

執(zhí)行操作INSERT 2 9將得到：5, 3, 9, 1，此時(shí)MIN_GAP為22，MIN_SORT_GAP為22。

再執(zhí)行操作INSERT 2 6將得到：5, 3, 9, 6, 1

注意這個(gè)時(shí)候原序列的第2個(gè)元素后面已經(jīng)添加了一個(gè)9，此時(shí)添加的6應(yīng)加在9的后面。這個(gè)時(shí)候MIN_GAP為2，MIN_SORT_GAP為1。

于是小Q寫了一個(gè)程序，使得程序可以自動(dòng)完成這些操作，但是他發(fā)現(xiàn)對(duì)于一些大的報(bào)表他的程序運(yùn)行得很慢，你能幫助他改進(jìn)程序么？

輸入輸出格式

輸入格式：

?

第一行包含兩個(gè)整數(shù)N，M，分別表示原數(shù)列的長(zhǎng)度以及操作的次數(shù)。

第二行為N個(gè)整數(shù)，為初始序列。

接下來的M行每行一個(gè)操作，即INSERT i k，MIN_GAP，MIN_SORT_GAP?中的一種（無多余空格或者空行）。

?

輸出格式：

?

對(duì)于每一個(gè)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

說明

對(duì)于30%的數(shù)據(jù)，N ≤ 1000?,M ≤ 5000
對(duì)于100%的數(shù)據(jù)，N ,M ≤500000
對(duì)于所有的數(shù)據(jù)，序列內(nèi)的整數(shù)不超過5×10⁸。

時(shí)限2s

?

Solution：

　　本題splay+堆（好水啊，亂打的代碼都能AC~）。

　　分析題目：

　　　　操作1，加入一個(gè)數(shù)，只會(huì)改變相鄰的關(guān)系，所以數(shù)組模擬隨便亂搞維護(hù)下相鄰關(guān)系。

　　　　操作2，加入一個(gè)數(shù)，改變的是兩對(duì)相鄰的差值，所以可以直接用帶修改的堆去維護(hù)（pbds大法好！）。

　　　　操作3，由于是維護(hù)全局最小值，那么只需要在加入數(shù)時(shí)，在其插入二叉搜索樹的遍歷過程中，與訪問過的節(jié)點(diǎn)更新下答案，當(dāng)然為了保證樹的平衡，選用平衡樹寫寫就行了。

代碼：

/*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=1000005; int n,m,a[N<<1][2],tot,val[N<<1]; int root,ch[N][2],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=0;char x=getchar();bool f=0;while((x<'0'||x>'9')&&x!='-') x=getchar();if(x=='-') x=getchar(),f=1;while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),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=0;return;}if(x<date[rt])insert(ch[rt][0],x),fa[ch[rt][0]]=rt,minn=min(minn,abs(date[rt]-x));else insert(ch[rt][1],x),fa[ch[rt][1]]=rt,minn=min(minn,abs(date[rt]-x)); }int main(){int pos,x; char s[10];n=gi(),m=gi(),tot=n;For(i,1,n) {val[i]=gi(),insert(root,val[i]),splay(cnt,0);if(i!=1) a[i][0]=i;if(i!=n) a[i][1]=i;}For(i,2,n) id[i]=q.push(node{i,i+1,abs(val[i]-val[i-1])});while(m--){scanf("%s",s);if(s[0]=='I') {pos=gi(),val[++tot]=gi(),insert(root,val[tot]),splay(cnt,0);int tp=a[pos][1];id[tot]=q.push(node{tot,tp,abs(val[tp]-val[tot])});if(pos!=n) q.modify(id[pos+1],node{pos+1,tot,abs(val[pos+1]-val[tot])});a[pos+1][0]=tot,a[pos][1]=tot;}else if(strlen(s)==7) printf("%d\n",q.top().val);else printf("%d\n",minn);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/five20/p/9665522.html

總結(jié)

以上是生活随笔為你收集整理的P1110 [ZJOI2007]报表统计的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。