Description 小Q的媽媽是一個出納，經常需要做一些統計報表的工作。今天是媽媽的生日，小Q希望可以幫媽媽分擔一些工 作，作為她的生日禮物之一。經過仔細觀察，小Q發現統計一張報表實際上是維護一個可能為負數的整數數列，並 且進行一些查詢操作。在最開始的時候，有一個長度為N的整數序列，並且有以下三 ...
Submit: 4190 Solved: 1420
[Submit][Status][Discuss]
Description
小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 為2，MIN_SORT_GAP為2。 再執行操作INSERT 2 6將得到： 5 3 9 6 1 註意這個時候原序列的第2個元素後面已經 添加了一個9，此時添加的6應加在9的後面。這個時候MIN_GAP為2，MIN_SORT_GAP為1。於是小Q寫了一個程式，使 得程式可以自動完成這些操作，但是他發現對於一些大的報表他的程式運行得很慢，你能幫助他改進程式麽？Input
第一行包含兩個整數N，M，分別表示原數列的長度以及操作的次數。第二行為N個整數，為初始序列。接下來 的M行每行一個操作，即“INSERT i k”，“MIN_GAP”，“MIN_SORT_GAP”中的一種（無多餘空格或者空行）。Output
對於每一個“MIN_GAP”和“MIN_SORT_GAP”命令，輸出一行答案即可。
Sample Input
3 55 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
Sample Output
22
1
HINT
N , M ≤500000 對於所有的數據，序列內的整數不超過5*10^8。
Source
時隔19260817年後再一次在BZOJ上A題&&1A
沒有修改操作，這是本題最大的突破口
這樣的話每個位置我們只需要維護原始的值和加入的最後一個值
相鄰的差值用multiset維護
同時用一個set維護加入的數
再用一個set維護加入的數的差值
然後就可以搞了
插入的時候有很多細節要處理
#include<cstdio> #include<set> #include<algorithm> #define msit multiset<int>::iterator #define sit set<int>::iterator using namespace std; const int MAXN=1e6+10; multiset<int>sp;//相鄰元素的差值 set<int>sv;//相近元素的差值 set<int>s;//維護已經加入的元素的值 struct node { int up,down; }a[MAXN]; int date[MAXN]; char opt[25]; int main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif int N,M; scanf("%d%d",&N,&M); for(int i=1;i<=N;i++) scanf("%d",&a[i].up), date[i]=a[i].down=a[i].up, s.insert(a[i].up); for(int i=1;i<=N-1;i++) sp.insert(abs(a[i].up-a[i+1].up)); sort(date+1,date+N+1); for(int i=1;i<=N-1;i++) sv.insert(abs(date[i]-date[i+1])); while(M--) { scanf("%s",opt); if(opt[4]=='R')//insert { int pos,val; scanf("%d%d",&pos,&val); msit it=sp.find(abs(a[pos].down-a[pos+1].up)); if(it!=sp.end()) sp.erase(it); sp.insert(abs(val-a[pos].down)); sp.insert(abs(val-a[pos+1].up)); a[pos].down=val; sit st=s.lower_bound(val); if(st!=s.end()) sv.insert(abs(val-*st)); if(st!=s.begin()) --st, sv.insert(abs(val-*st)); s.insert(val); } else if(opt[4]=='S')//val min printf("%d\n",*sv.begin()); else if(opt[4]=='G')//neighbor min printf("%d\n",*sp.begin()); } return 0; }
