鏈接：https://www.lydsy.com/JudgeOnline/problem.php?id=1058

題面;

1058: [ZJOI2007]報(bào)表統(tǒng)計(jì)

Time Limit:?15 Sec??Memory Limit:?162 MB
Submit:?4740??Solved:?1568
[Submit][Status][Discuss]

Description

小Q的媽媽是一個(gè)出納，經(jīng)常需要做一些統(tǒng)計(jì)報(bào)表的工作。今天是媽媽的生日，小Q希望可以幫媽媽分擔(dān)一些工 作，作為她的生日禮物之一。經(jīng)過(guò)仔細(xì)觀察，小Q發(fā)現(xiàn)統(tǒng)計(jì)一張報(bào)表實(shí)際上是維護(hù)一個(gè)可能為負(fù)數(shù)的整數(shù)數(shù)列，并 且進(jìn)行一些查詢操作。在最開(kāi)始的時(shí)候，有一個(gè)長(zhǎng)度為N的整數(shù)序列，并且有以下三種操作： INSERT i k 在原數(shù) 列的第i個(gè)元素后面添加一個(gè)新元素k； 如果原數(shù)列的第i個(gè)元素已經(jīng)添加了若干元素，則添加在這些元素的最后（ 見(jiàn)下面的例子） MIN_GAP 查詢相鄰兩個(gè)元素的之間差值（絕對(duì)值）的最小值 MIN_SORT_GAP 查詢所有元素中最接 近的兩個(gè)元素的差值（絕對(duì)值） 例如一開(kāi)始的序列為 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寫(xiě)了一個(gè)程序，使 得程序可以自動(dòng)完成這些操作，但是他發(fā)現(xiàn)對(duì)于一些大的報(bào)表他的程序運(yùn)行得很慢，你能幫助他改進(jìn)程序么？

Input

第一行包含兩個(gè)整數(shù)N，M，分別表示原數(shù)列的長(zhǎng)度以及操作的次數(shù)。第二行為N個(gè)整數(shù)，為初始序列。接下來(lái) 的M行每行一個(gè)操作，即“INSERT i k”，“MIN_GAP”，“MIN_SORT_GAP”中的一種（無(wú)多余空格或者空行）。

Output

　　對(duì)于每一個(gè)“MIN_GAP”和“MIN_SORT_GAP”命令，輸出一行答案即可。

Sample Input

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

Sample Output

2
2
1

HINT

?

N , M ≤500000 對(duì)于所有的數(shù)據(jù)，序列內(nèi)的整數(shù)不超過(guò)5*10^8。

思路很容易想，寫(xiě)起來(lái)有點(diǎn)麻煩 實(shí)現(xiàn)代碼： #include<bits/stdc++.h> using namespace std; #define ll long long #define ls t[x].ch[0] #define rs t[x].ch[1] const int M = 1e6 + 10; const int inf = 1e9; int idx,rt,n,m,a[M]; vector<int>g[M]; priority_queue<int,vector<int>,greater<int> > q; map<int,int>vis; struct node{int ch[2],cnt,siz,val,rd; }t[M];void up(int x){t[x].siz = t[ls].siz + t[rs].siz + t[x].cnt; }void rotate(int &x,int d){int son = t[x].ch[d];t[x].ch[d] = t[son].ch[d^1];t[son].ch[d^1] = x; up(x); up(x = son); }void ins(int &x,int val){if(!x){x = ++idx;t[x].cnt = t[x].siz = 1;t[x].val = val; t[x].rd = rand();return ;}t[x].siz ++;if(t[x].val == val){t[x].cnt ++; return ;}int d = t[x].val < val;ins(t[x].ch[d],val);if(t[x].rd > t[t[x].ch[d]].rd) rotate(x,d); }int pre(int x,int val){if(!x) return -inf;if(t[x].val >= val) return pre(ls,val);return max(pre(rs,val),t[x].val); }int nex(int x,int val){if(!x) return inf;if(t[x].val <= val) return nex(rs,val);return min(nex(ls,val),t[x].val); }int main() {int x,y; char op[100];int mn = inf;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i ++){scanf("%d",&a[i]);g[i].push_back(a[i]);if(i!=1){int x = pre(rt,a[i]+1);int y = nex(rt,a[i]);mn = min(mn,min(abs(x-a[i]),abs(y-a[i])));}ins(rt,a[i]);}for(int i = 2;i <= n;i ++){q.push(abs(a[i]-a[i-1]));}while(m --){scanf("%s",op);if(op[0] == 'I'){scanf("%d%d",&x,&y);g[x].push_back(y);int len = g[x].size();int a = pre(rt,y+1);int b = nex(rt,y);mn = min(mn,min(abs(a-y),abs(b-y)));ins(rt,y);q.push(abs(g[x][len-2]-y));if(x != n){vis[abs(g[x][len-2]-g[x+1][0])]++;q.push(abs(y-g[x+1][0]));}}else if(op[4]=='G'){while(!q.empty()){int num = q.top();if(!vis[num]) break;vis[num]--; q.pop();}printf("%d\n",q.top());}else if(op[4]=='S'){printf("%d\n",mn);}} }

?

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

總結(jié)

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

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