Description

　　小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ù)數(shù)列，并
且進(jìn)行一些查詢操作。在最開始的時(shí)候，有一個(gè)長度為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
為2，MIN_SORT_GAP為2。 再執(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)程序么？

solution

正解：堆+平衡樹
又墮落了QwQ，說好的平衡樹呢？
對(duì)于第一個(gè)操作，我們鏈表維護(hù)一下即可
對(duì)于第二個(gè)詢問，我們維護(hù)一個(gè)堆，我們每加入一個(gè)元素就把與前后差值加入堆中，堆中記錄后繼，便于刪除.
對(duì)于第三個(gè)詢問，答案單調(diào)不升，直接平衡樹維護(hù)全局變量，插入時(shí)取min即可

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #include <cmath> #include <set> #define RG register #define il inline #define iter iterator #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const int N=1000005,inf=2e9; int n,m,nxt[N],cnt=0,pre[N],val[N],last[N],b[N]; char S[41]; struct node{int x,y,val;bool operator <(const node &pr)const{return val>pr.val;} }; priority_queue<node>q; multiset<int>G; multiset<int>::iter it; void work() {int x,y,z,ans=inf;node k;scanf("%d%d",&n,&m);cnt=n;for(int i=1;i<=n;i++){scanf("%d",&val[i]);b[i]=val[i];last[i]=i;pre[i]=i-1;nxt[i]=i+1;if(i!=1)q.push((node){i-1,i,abs(val[i]-val[i-1])});G.insert(val[i]);}sort(b+1,b+n+1);for(int i=2;i<=n;i++)ans=min(ans,b[i]-b[i-1]);G.insert(-inf);G.insert(inf);while(m--){scanf("%s",S);if(S[0]=='I'){scanf("%d%d",&x,&z);y=last[x];cnt++;val[cnt]=z;if(x<n)pre[x+1]=cnt,nxt[cnt]=x+1;last[x]=cnt;nxt[y]=cnt;pre[cnt]=y;q.push((node){y,cnt,abs(val[y]-z)});if(x<n)q.push((node){cnt,x+1,abs(val[x+1]-z)});it=G.lower_bound(z);if(*it!=-inf){ans=min(ans,abs(*it-z));--it;if(*it!=-inf)ans=min(ans,abs(*it-z));}it=G.upper_bound(z);if(*it!=inf)ans=min(ans,abs(*it-z));G.insert(z);}else if(S[4]=='G'){while(!q.empty()){k=q.top();if(nxt[k.x]!=k.y)q.pop();else {printf("%d\n",k.val);break;}}}else printf("%d\n",ans);} }int main() {freopen("pp.in","r",stdin);freopen("pp.out","w",stdout);work();return 0; }

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

總結(jié)

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

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