题解 P6105 【[Ynoi2010]iepsmCmq】

· · 题解

比赛时 T2 忘开 long long 自闭了好长时间，这是赛后写的。

好像这题还蛮套路的？

首先我们先分类讨论（加入集合 S 时已取模）：

若此题离线，那么考虑线段树分治，每次加进去的时候把这个数的最佳匹配找出来，对答案取个 \max。时间 O(n\log^2 n)。

现在考虑在线。若删除的话，有可能这个数是多个数的最佳匹配，那么一次删除涉及最多 O(|S|) 次重新匹配，显然不可取。

那么我们换个角度考虑，只维护双向匹配的对数，这样每次修改只涉及 O(1) 对，时间就对了。

为什么呢？

一般这种最优化数对的题，都是先弄出个 O(n^2) 的解法，再看看这些对数是否满足什么限制，使得某个数对 (i,j) 一定比 (j,k) 优，这些数对一定很少且一次修改涉及的对数不多，所以我们只需要维护这些数对。

假设 i 的最优匹配是 j，j 的最优匹配是 k。若 i<k，那么只需考虑 (j,k) 这一数对。

这样的数对显然最多 O(n) 个，用 \text{multiset} 维护最优匹配，时间 O(n\log n)。

不过你一次修改需要找出这个数的最优匹配，最优匹配的最优匹配，最优匹配的最优匹配的最优匹配，常数比较大，细节有一点。建议画个图把细节理清楚再写。还有，\text{stl} 的边界要格外小心。

最短代码 \text{1.13k}：

#include <bits/stdc++.h>
using namespace std;
int n,c,sz;
multiset<int> a,b;
multiset<int>::iterator it;
inline int best(int x,int op)
{
    if(x==-1) return -1;
    it=a.upper_bound(c-1-x);
    if(it==a.begin()) return -1;
    it--;
    if(op==1 && *it==x && a.count(x)==1)
        return (it==a.begin())?-1:*--it;
    else
        return *it;
}
inline void insert(int x)
{
    sz++;
    if(sz==1) { a.insert(x); return; }
    int y=best(x,0),z=best(y,1),w=best(z,1);
    if(y!=-1 && z<x)
    {
        if(z!=-1 && y==w) b.erase(b.find(y+z));
        b.insert(x+y);
    }
    a.insert(x);
}
inline void erase(int x)
{
    a.erase(a.find(x)),sz--;
    if(!sz) return;
    int y=best(x,0),z=best(y,1),w=best(z,1);
    if(y!=-1 && z<x)
    {
        if(z!=-1 && y==w) b.insert(y+z);
        b.erase(b.find(x+y));
    }
}
inline int query()
{
    it=--a.end();
    if(a.count(*it)>=2) return *it*2%c;
    else return (*it+*--it)%c;
}
int main()
{
    scanf("%d%d",&n,&c);
    int op,x,lastans=0;
    while(n--)
    {
        scanf("%d%d",&op,&x); x^=lastans;
        if(op==1) insert(x%c);
        else erase(x%c);
        if(sz<2) puts("EE"),lastans=0;
        else printf("%d\n",lastans=max(query(),b.empty()?0:*--b.end()));
    }
    return 0;
}

（估计我大括号不换行会更短）

题出得好！难度适中，覆盖知识点广，码量不大，解法比较自然，给出题人点赞！

就是没啥 gal 的背景，差评

upd: 好像不能每次都过？