题解 P1110 【[ZJOI2007]报表统计】
题解

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)找到当前相邻。

代码比较丑,但比手写某树和某堆方便多了


#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;
}
评论