BZOJ1058:[ZJOI2007]报表统计STL维护全局和局部最优值

Description
　　小Q的妈妈是一个出纳&＃xff0c;经常需要做一些统计报表的工作。今天是妈妈的生日&＃xff0c;小Q希望可以帮妈妈分担一些工
作&＃xff0c;作为她的生日礼物之一。经过仔细观察&＃xff0c;小Q发现统计一张报表实际上是维护一个可能为负数的整数数列&＃xff0c;并
且进行一些查询操作。在最开始的时候&＃xff0c;有一个长度为N的整数序列&＃xff0c;并且有以下三种操作&＃xff1a; INSERT i k 在原数
列的第i个元素后面添加一个新元素k&＃xff1b; 如果原数列的第i个元素已经添加了若干元素&＃xff0c;则添加在这些元素的最后&＃xff08;
见下面的例子&＃xff09; MIN_GAP 查询相邻两个元素的之间差值&＃xff08;绝对值&＃xff09;的最小值 MIN_SORT_GAP 查询所有元素中最接
近的两个元素的差值&＃xff08;绝对值&＃xff09; 例如一开始的序列为 5 3 1 执行操作INSERT 2 9将得到&＃xff1a; 5 3 9 1 此时MIN_GAP
为2&＃xff0c;MIN_SORT_GAP为2。 再执行操作INSERT 2 6将得到&＃xff1a; 5 3 9 6 1 注意这个时候原序列的第2个元素后面已经
添加了一个9&＃xff0c;此时添加的6应加在9的后面。这个时候MIN_GAP为2&＃xff0c;MIN_SORT_GAP为1。于是小Q写了一个程序&＃xff0c;使
得程序可以自动完成这些操作&＃xff0c;但是他发现对于一些大的报表他的程序运行得很慢&＃xff0c;你能帮助他改进程序么&＃xff1f;
Input
　　第一行包含两个整数N&＃xff0c;M&＃xff0c;分别表示原数列的长度以及操作的次数。第二行为N个整数&＃xff0c;为初始序列。接下来
的M行每行一个操作&＃xff0c;即“INSERT i k”&＃xff0c;“MIN_GAP”&＃xff0c;“MIN_SORT_GAP”中的一种&＃xff08;无多余空格或者空行&＃xff09;。
Output

　　对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令&＃xff0c;输出一行答案即可。
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 对于所有的数据&＃xff0c;序列内的整数不超过5*10^8。

解题方法&＃xff1a; 开两个STL的set就可以了。记一下每个数被添加一些数以后最左面的是多少&＃xff0c;
最右面的是多少。为了防止超时&＃xff0c;如果 MIN_SORT_GAP 已经为 0&＃xff0c;那么就不更新它了。
STL暴力大法好。。。

代码如下&＃xff1a;

#include
using namespace std;
const int maxn &＃61; 1000010;
const int inf &＃61; 0x3f3f3f3f;
struct FastIO {static const int S &＃61; 1310720;int wpos; char wbuf[S];FastIO() : wpos(0) {}inline int xchar() {static char buf[S];static int len &＃61; 0, pos &＃61; 0;if (pos &＃61;&＃61; len)pos &＃61; 0, len &＃61; fread(buf, 1, S, stdin);if (pos &＃61;&＃61; len) return -1;return buf[pos &＃43;&＃43;];}inline int xuint() {int c &＃61; xchar(), x &＃61; 0;while (c <&＃61; 32) c &＃61; xchar();for (;&＃39;0&＃39; <&＃61; c && c <&＃61; &＃39;9&＃39;; c &＃61; xchar()) x &＃61; x * 10 &＃43; c - &＃39;0&＃39;;return x;}inline int xint() {int s &＃61; 1, c &＃61; xchar(), x &＃61; 0;while (c <&＃61; 32) c &＃61; xchar();if (c &＃61;&＃61; &＃39;-&＃39;) s &＃61; -1, c &＃61; xchar();for (; &＃39;0&＃39; <&＃61; c && c <&＃61; &＃39;9&＃39;; c &＃61; xchar()) x &＃61; x * 10 &＃43; c - &＃39;0&＃39;;return x * s;}inline void xstring(char *s) {int c &＃61; xchar();while (c <&＃61; 32) c &＃61; xchar();for(; c > 32; c &＃61; xchar()) *s&＃43;&＃43; &＃61; c;*s &＃61; 0;}inline void wchar(int x) {if (wpos &＃61;&＃61; S) fwrite(wbuf, 1, S, stdout), wpos &＃61; 0;wbuf[wpos &＃43;&＃43;] &＃61; x;}inline void wint(int x) {if (x <0) wchar(&＃39;-&＃39;), x &＃61; -x;char s[24];int n &＃61; 0;while (x || !n) s[n &＃43;&＃43;] &＃61; &＃39;0&＃39; &＃43; x % 10, x /&＃61; 10;while (n--) wchar(s[n]);}inline void wstring(const char *s) {while (*s) wchar(*s&＃43;&＃43;);}~FastIO() {if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos &＃61; 0;}
} io;
int n, m;
int st[maxn], en[maxn];
map <int, int> mp;
multiset <int> a, b;
//a维护相邻差最优值, q 维护全局最优值
priority_queue <int, vector <int>, greater<int> > q;
void ins1(int x){mp[x]&＃43;&＃43;;if(mp[x] &＃61;&＃61; 1) a.insert(x);
}
void ins2(int x){int l &＃61; *--b.lower_bound(x), r &＃61; *b.lower_bound(x);q.push(min(x - l, r - x));b.insert(x);
}
char cmd[20];
int main(){n &＃61; io.xint(); m &＃61; io.xint();b.insert(inf); b.insert(-inf);for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){int x &＃61; io.xint();st[i] &＃61; en[i] &＃61; x;ins2(x);}int p, x, y;for(int i &＃61; 2; i <&＃61; n; i&＃43;&＃43;) ins1(abs(st[i] - st[i-1]));for(int i &＃61; 1; i <&＃61; m; i&＃43;&＃43;){//scanf("%s", cmd);io.xstring(cmd);if(cmd[0] &＃61;&＃61; &＃39;I&＃39;){//scanf("%d%d", &p, &x);p &＃61; io.xint(), x &＃61; io.xint();if(p !&＃61; n){y &＃61; abs(en[p] - st[p &＃43; 1]);mp[y]--;if(!mp[y]) a.erase(y);}ins1(abs(en[p] - x));ins1(abs(x - st[p&＃43;1]));en[p] &＃61; x;if(q.top() &＃61;&＃61; 0) continue;ins2(x);}else if(cmd[4] &＃61;&＃61; &＃39;S&＃39;){printf("%d\n", q.top());}else{printf("%d\n", *a.begin());}}return 0;
}