[ZJOI2007]报表统计
Time Limit:15000MS Memory Limit:165536K
Total Submit:154 Accepted:37
Case Time Limit:10000MS
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 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
Sample Output
2
2
1
Hint
对于30%的数据，N ≤ 1000 , M ≤ 5000
对于100%的数据，N , M ≤500000
对于所有的数据，序列内的整数不超过5*108。
Source
61.187.179.132:8080/JudgeOnline/showproblem
由于是中文的，题目大意就不用讲了
那么这道题怎么办呢？我是全用stl的，Code Length最短，速度就悲剧了。。
首先第一个操作的话用个vector数组模拟就可以了。。
由题目的特性，把第i个元素后面的数成为第i个列表。。
那么第二个操作，MIN_GAP呢？
有三个办法，一个是自己写一个heap。然后需要有删除操作，所以还要弄一个索引。。
麻烦额。。第二个是用一个multiset，然后删除就删除，最小就是begin()。。
我一开始就是这样。。TLE了。。
第三就是用stl里面priority_queue，那么删除的话可以用懒删除，
因为一个节点只要不是最小的就没有立马删除的必要，
那么可以发现如果造成这个差值的两个数在同一个列表里。。
那么这个值永远不会被删除，
只有是一个列表的最后一个和其后一个列表的第一个造成的差值，
才有可能在插了一个数后被删除，那么只需要对后一种记录当时的前一个列表的大小，
那么如果这个大小小于当前的大小，就说明在那之后有值插进来过，这个值就失效了。。
第二个就搞定了。。
第三个呢？首先注意到这个值只可能是在排序之后的相邻对，
那么只需要用一个set来维护当前所有数，并且在插入之后更新一下就可以了。。
按这个思路写成的Code差点就超时了。。
于是我又想了一会儿。。发现根本没必要用vector，
因为当前有效的项根本就只有第一项和最后一项！
所以只要弄个2维数组就可以了！
然后就快多了：
代码也短了。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<utility>
#include<set>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define For(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int inf=~0U>>2;
const int maxn=500000;int n;
int L[maxn][2];
int N[maxn];
inline int abs(int x){return x>0?x:-x;}
struct qset
{
multiset<int> S;
typedef set<int>::iterator it;
int Min;
qset(){Min=inf;}
void ins(int x)
{
it j=S.insert(x);
if(j!=S.begin())
Min=min(Min,x-*(–j)),++j;
++j;
if(j!=S.end())
Min=min(Min,*(j)-x);
}
}All;
struct state
{
bool in;
int i,x,val;
state(bool _in,int _val,int _i=0,int _x=0):
in(_in),i(_i),x(_x),val(_val){}
bool legal() const{return in||x==N[i];}
bool operator<(const state&o) const{return val>o.val;}
};
priority_queue<state> Q;
void ins(int i,int x)
{
All.ins(x);
Q.push(state(true,abs(x-L[i][1])));
L[i][1]=x;N[i]++;
if(i!=n-1) Q.push(state(false,abs(L[i+1][0]-x),i,N[i]));
}
int get()
{
while(!Q.top().legal()) Q.pop();
return Q.top().val;
}
int main()
{
char cmd[100];
int n,m,x,i;
scanf("%d %d",&n,&m);
rep(i,n) scanf("%d",&L[i][0]),L[i][1]=L[i][0],All.ins(L[i][0]),N[i]=1;
For(i,0,n-1)
{
Q.push(state(false,abs(L[i+1][0]-L[i][0]),i,1));
}
while(m–)
{
scanf("n");
scanf("%s",cmd);
if(cmd[0]==’I’)
scanf("%d %d",&i,&x),ins(i-1,x);
else if(cmd[4]==’G’) printf("%dn",get());
else printf("%dn",All.Min);
}
}
本高亮代码使用codeHl生成，查看详情
