[ZJOI2007]报表统计

[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生成,查看详情

2 thoughts on “[ZJOI2007]报表统计

  1. 回复SMCamila:囧。。我也不知道这两个到底有什么区别。。我只知道似乎G++是可以用typeof的。。。就是拿出一个变量的类型。。还有C++要快一点。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>