bzoj1058: [ZJOI2007]报表统计

一看就知道是数据结构的题目，乍一看可以用STL水过去

题目中有几个细节要注意，这里不说看代码

const int N = 500010;
int n, m, Dat[N], Sort[N];
set<int> s1, s2;
map<int, int> Hash;
vector<int> g[N];
int Ans1, Ans2;

inline void Input() {
	scanf("%d%d", &n, &m);
	Ans2 = INF, Ans1 = INF;
	Rep(i, n) {
		scanf("%d", &Dat[i]), Sort[i] = Dat[i];
		s2.insert(Dat[i]);
		if(i) {
			int k = abs(Dat[i] - Dat[i - 1]);
			s1.insert(k);
			Hash[k]++;
		}
	}
}

inline void Solve() {
	sort(Sort, Sort + n);
	For(i, 1, n - 1) Ans1 = min(Ans1, Sort[i] - Sort[i - 1]);
	Ans2 = *s1.begin();
	char opt[33];
	while(m--) {
		scanf("%s", opt);
		if(opt[4] == 'R') {
			int pos, val;
			scanf("%d%d", &pos, &val);
			g[--pos].pub(val);
			if(Ans1) {
				set<int>::iterator it = s2.lower_bound(val);
				if(it != s2.begin()) {
					if(it == s2.end()) {
						*it--;
						Ans1 = min(Ans1, abs(val - *it));
					} else {
						int x = *it;
						it--;
						int y = *it;
						Ans1 = min(Ans1, min(abs(y - val), abs(x - val)));
					}
				} else Ans1 = min(Ans1, abs(val - *s2.begin()));
			}
			
			s2.insert(val);
			int x, y = INF;
			if(g[pos].size() == 1) x = Dat[pos];
			else x = g[pos][g[pos].size() - 2];
			if(pos + 1 < n) {
				y = Dat[pos + 1];
				int k = abs(x - y);
				if(--Hash[k] == 0) s1.erase(k);
				k = abs(x - val), s1.insert(k), Hash[k]++;
				k = abs(y - val), s1.insert(k), Hash[k]++;
				Ans2 = *s1.begin();
			} else {
				int k = abs(x - val);
				s1.insert(k);
				Hash[k]++;
				Ans2 = *s1.begin();
			}
		} else if(opt[4] == 'G') printf("%d\n", Ans2);
		else printf("%d\n", Ans1);
	}
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1058");
	#endif
	Input();
	Solve();
	return 0;
}