本文主要是介绍BZOJ 1058 [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写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
这道题看起来很麻烦的样子。
按理来说是一个高级的数据结构题。
不过被我用STL水过去了。不过时间上惨不忍睹，用了16s多，题目要求是15s，但是还是过了。
先说任意元素之间的差值的绝对值。
无非是用一个set存入所有的数，然后每次插入某个数后，二分查找到插入的位置，然后能影响到的就是相邻的两个数，更新一下答案好了。
当然注意一个边界问题
然后就是相邻的元素的差值的绝对值。
我用了一个set和一个map。
set就是存各种差值，map则存每种差值有几个。
然后每次插入，会产生的改变就是原来相邻的数不相邻了，然后插入的数会有两个相邻的数。
更新一下map和set即可
当然，边界问题也是很重要的，比如说插入到了最后一个数后边。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <map>
#include <set>
#define MAXN 500005
#define INF 1000000007
using namespace std;
int n, m;
set<int>s, ss;
map<int, int>mp;
vector<int>g[MAXN];
int a[MAXN], b[MAXN];
int main()
{scanf("%d%d", &n, &m);int mg = INF, ms = INF, pos, val;for(int i = 0; i < n; i++){scanf("%d", &a[i]);ss.insert(a[i]);b[i] = a[i];if(i){int k = abs(a[i] - a[i - 1]);s.insert(k);mp[k]++;}}sort(b, b + n);for(int i = 1; i < n; i++)ms = min(ms, b[i] - b[i - 1]);mg = *s.begin();char op[33];while(m--){scanf("%s", op);if(op[4] == 'R'){scanf("%d%d", &pos, &val);pos--;g[pos].push_back(val);if(ms){set<int>::iterator it = ss.lower_bound(val);if(it != ss.begin()){if(it == ss.end()){it--;ms = min(ms, abs(val - *it));}else{int x = *it;it--;int y = *it;ms = min(ms, abs(x - val));ms = min(ms, abs(y - val));}}else ms = min(ms, abs(val - *ss.begin()));}ss.insert(val);int x, y = INF;if(g[pos].size() == 1) x = a[pos];else x = g[pos][g[pos].size() - 2];if(pos + 1 < n){y = a[pos + 1];int k = abs(x - y);mp[k]--;if(mp[k] == 0) s.erase(k);k = abs(x - val);s.insert(k);mp[k]++;k = abs(y - val);s.insert(k);mp[k]++;mg = *s.begin();}else{int k = abs(x - val);s.insert(k);mp[k]++;mg = *s.begin();}}else if(op[4] == 'G') printf("%d\n", mg);else printf("%d\n", ms);}return 0;
}这篇关于BZOJ 1058 [ZJOI2007]报表统计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
