[补档][ZJOI2007] 报表统计

[ZJOI2007] 报表统计

题目

传送门

小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

输入文件form.in第一行包含两个整数N，M，分别表示原数列的长度以及操作的次数。

第二行为N个整数，为初始序列。

接下来的M行每行一个操作，即“INSERT i k”，“MIN_GAP”，“MIN_SORT_GAP”中的一种（无多余空格或者空行）。

OUTPUT

对于每一个“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

OUTPUT

2

2

1

数据规模

对于30%的数据，N≤ 1000 , M ≤ 5000

对于100%的数据，N , M ≤500000

对于所有的数据，序列内的整数不超过5×10^8。

解题报告

考试题的加强版，数据大了十倍

考试打了个暴力，骗了20分= =

正解：

STL三件套——vec,que,还有set

vector用来存每个位置后面加的元素

priority_queue用来存相邻的差值，要用两个，一个存答案，一个用来垃圾回收（为什么要垃圾回收？当我们插入一个数时，我们将两个原本相连的数分开了，那么他们不再相连，所以我们要清理掉它）

set用来处理全局最小差，我们可以用set找到一个数的前驱与后驱，而且显然的是，最小差一定存在于排完序后的相邻的数，所以我们可以进行预处理，边插入边更新

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<vector>
  5 #include<queue>
  6 #include<set>
  7 using namespace std;
  8 inline int read(){
  9     int sum(0),f(1);
 10     char ch(getchar());
 11     for(;ch<'0'||ch>'9';ch=getchar())
 12         if(ch=='-')
 13             f=-1;
 14     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
 15     return sum*f;
 16 }
 17 priority_queue<int,vector<int>,greater<int> >dust;
 18 priority_queue<int,vector<int>,greater<int> >ans1;
 19 vector<int>v[500002];
 20 multiset<int>st;
 21 multiset<int>::iterator it;
 22 int n,m;
 23 int w[500002];
 24 int ans2(0x7fffffff);
 25 char op[20];
 26 inline int my_max(int a,int b){
 27     return a>b?a:b;
 28 }
 29 inline int my_min(int a,int b){
 30     return a<b?a:b;
 31 }
 32 inline int jdz(int x){
 33     return x>=0?x:-x;
 34 }
 35 inline void insert(int x,int y){
 36     int size(v[x].size());
 37     if(x<n)
 38         dust.push(jdz(v[x][size-1]-v[x+1][0]));
 39     ans1.push(jdz(y-v[x][size-1]));
 40     if(x<n)
 41         ans1.push(jdz(y-v[x+1][0]));
 42     v[x].push_back(y);
 43     st.insert(y);
 44     it=st.find(y);
 45     if(it!=st.begin()){
 46         it--;
 47         int tmp(*it);
 48         ans2=my_min(jdz(y-tmp),ans2);
 49         it++;
 50     }
 51     if(it!=st.end()){
 52         it++;
 53         int tmp(*it);
 54         ans2=my_min(jdz(y-tmp),ans2);
 55     }
 56 }
 57 inline int query(){
 58     while(1){
 59         if(dust.empty()||dust.top()!=ans1.top())
 60             break;
 61         dust.pop();
 62         ans1.pop();
 63     }
 64     return ans1.top();
 65 }
 66 int main(){
 67   freopen("form.in","r",stdin);
 68   freopen("form.out","w",stdout);
 69     n=read(),m=read();
 70     for(int i=1;i<=n;i++){
 71         w[i]=read();
 72         st.insert(w[i]);
 73         it=st.find(w[i]);
 74         if(it!=st.begin()){
 75             it--;
 76             int tmp(*it);
 77             ans2=my_min(ans2,jdz(tmp-w[i]));
 78             it++;
 79         }
 80         if(it!=st.end()){
 81             it++;
 82             int tmp(*it);//cout<<tmp<<endl;
 83             ans2=my_min(ans2,jdz(tmp-w[i]));
 84         }
 85         if(i^1)
 86             ans1.push(jdz(w[i]-w[i-1]));
 87         v[i].push_back(w[i]);
 88 //      cout<<i<<' '<<w[i]<<' '<<ans2<<endl;
 89     }
 90     while(m--){
 91         scanf("%s",op);
 92         if(op[0]=='I'){
 93             int x(read()),y(read());
 94             insert(x,y);
 95         }
 96         else{
 97             if(strlen(op)<9)
 98                 printf("%d
",query());
 99             else
100                 printf("%d
",ans2);
101         }
102     }
103 }

View Code

好强大的STL啊= =