[ZJOI 2007] 报表统计

知识点

有序集合、相邻差维护、多重集合

解题思路

每个原位置保存其插入链的尾值。插入时，仅删除尾值到下一原值的旧相邻差，加入两个新差；最后一段只加一个差。用multiset维护相邻差；另一个有序集合查询新值的前驱后继，维护只会减小的全局最小排序差。

正确性说明

追加元素只改变所在原位置链尾附近的相邻关系，其余差值不动，局部替换保持全部相邻差多重集合准确。全局排序最近对若因插入而变小，必含新值，且其搭档只可能是前驱或后继；重复值使答案为0。两类查询因此正确。

易错点

INSERT i的i始终指原数列位置；同位置连续插入要接在已插入元素后；相等差值要只删除一个。

复杂度

时间O((n+m)log(n+m))，空间O(n+m)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<int>a(n+2),tail(n+1);multiset<int>gap;set<int>values;int sortedGap=INT_MAX;auto add=[&](int x){auto it=values.lower_bound(x);if(it!=values.end())sortedGap=min(sortedGap,*it-x);if(it!=values.begin())sortedGap=min(sortedGap,x-*prev(it));values.insert(x);};for(int i=1;i<=n;i++){cin>>a[i];tail[i]=a[i];add(a[i]);if(i>1)gap.insert(abs(a[i]-a[i-1]));}while(m--){string op;cin>>op;if(op=="INSERT"){int i,k;cin>>i>>k;if(i<n){auto it=gap.find(abs(tail[i]-a[i+1]));gap.erase(it);gap.insert(abs(k-a[i+1]));}gap.insert(abs(tail[i]-k));tail[i]=k;add(k);}else if(op=="MIN_GAP")cout<<*gap.begin()<<'\n';else cout<<sortedGap<<'\n';}}