题解 P1110 【[ZJOI2007]报表统计】
HOOCCOOH
2015-10-08 19:32:30
**STL大法好，set把你保**
MIN\_SORT\_GAP用set维护，插入前lower\_bound找最接近的值，更新最小值，然后insert
MIN\_GAP用堆维护，在a,b之间插入c时，把abs(a-b)从堆中删除，然后插入abs(a-c)和abs(b-c)
(由于本蒟蒻只会用stl堆，不支持删除，所以用了两个堆来达到删除指定数值，具体见代码)
记得插入的时候，找到真正与当前相邻的节点，因为之前可能已经插入了一些节点，所以用链表来O(1)找到当前相邻。
代码比较丑，但比手写某树和某堆方便多了
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
using namespace std;
typedef long long ll;
int iRead()
{
int ret = 0;
int ch;
while(!isdigit(ch = getchar()) && ch != '-');
bool bm = (ch == '-'); if(bm) ch = getchar();
while(ret = ret * 10 + (ch - '0'), isdigit(ch = getchar()));
return bm ? -ret : ret;
}
void iReadstr(char *p)
{
int ch;
while(isspace(ch = getchar()));
while(*p++ = ch, !isspace(ch = getchar()));
*p = '\0';
}
const int N = 1500003;
const int INF = 0x7FFFFFFF;
int n, m;
struct iT
{
int val;
iT *l, *r;
}ss[N], *sp = ss;
iT *arr[N];
int ss1[N], *pss1 = ss1;
int ss2[N], *pss2 = ss2;
set<int> s;
int ans2 = INF;
bool iCmp(int a, int b) {return a > b;}
void iUp(int val)
{
if(ans2)
{
pair<set<int>::iterator, bool> pr = s.insert(val);
if(pr.second)
{
set<int>::iterator it;
if(pr.first != s.begin())
{
it = pr.first;
ans2 = min(ans2, abs(*--it - val));
}
if(++pr.first != s.end())
ans2 = min(ans2, abs(*pr.first - val));
}
else
ans2 = 0;
}
}
int iAns1()
{
while(pss2 != ss2 && ss1[0] == ss2[0])
{
pop_heap(ss1, pss1--, iCmp);
pop_heap(ss2, pss2--, iCmp);
}
return ss1[0];
}
void iInsert(iT *c, int val)
{
iT *nc = sp++;
*nc = (iT){val, c, c->r};
if(c->r->val != INF)
{
*pss2++ = abs(c->val - c->r->val);
push_heap(ss2, pss2, iCmp);
}
c->r->l = nc;
c->r = nc;
*pss1++ = abs(c->val - c->r->val);
push_heap(ss1, pss1, iCmp);
if(c->r->r->val != INF)
{
*pss1++ = abs(c->r->val - c->r->r->val);
push_heap(ss1, pss1, iCmp);
}
}
int main()
{
n = iRead(), m = iRead();
for(int i = 0; i < n; ++i)
{
int c = iRead();
arr[i] = sp++;
arr[i]->val = c;
iUp(c);
if(i)
{
*pss1++ = abs(c - arr[i - 1]->val);
push_heap(ss1, pss1, iCmp);
}
}
*(arr[n] = sp++) = (iT){INF, arr[n - 1], NULL};
for(int i = 0; i < n; ++i)
{
if(i)
arr[i]->l = arr[i - 1];
if(i != n - 1)
arr[i]->r = arr[i + 1];
}
char str[20];
while(m--)
{
int a, b;
iReadstr(str);
switch(str[4])
{
case 'R':
a = iRead(), b = iRead();
iInsert(arr[a]->l, b);
iUp(b);
break;
case 'G':
printf("%d\n", iAns1());
break;
default:
printf("%d\n", ans2);
}
}
return 0;
}
```