题解 P6105 【[Ynoi2010]y-fast trie】

miaow · 2020-10-18 01:05:00 · 题解

这题思路挺简单的，就是代码写着有点麻烦 也可能是我太菜了

题解

首先很明显的，读进来的数字先mod C再操作对答案没有影响，这时候两个数相加是<2C的

然后分类讨论，一类是相加≥C的，这类就是直接取集合内最大的两个数相加即可（即使和比C小也无所谓）

对于和<C的，先把集合S内数字排成有序的（可以用set），然后每一个数字x维护与其相加最接近C的数字y，称为y是x的最佳匹配

具体来讲，对于每一个数字y用平衡树维护一个集合S_{y}，集合内存放最佳匹配是y的所有x，并设S中比x小的最大数字为z。在加入一个新的x时，将x放入S_{y}中，并将S_{z}中与x的和小于C的部分从S_{z}中取出放入S_{x}中。删除一个x时把x从S_{y}中删去，并将S_{x}并入S_{z}中。由于S_{x}中最大值必定比S_{z}中最小值要小，所以可以快速进行这些操作。再使用一个set储存每一个y与S_{y}中最大值的和，在每个S_{y}进行操作时动态维护这个set，这个set中的最大值即为和<C情况下的答案

有一个小细节就是数字不能重复取用，所以当x只加入了一次且其最佳匹配是其自身时，需要把x加入S_{z}中而不是S_{x}，当再次加入x时再把其取回来，其他相关的操作也要特判这种情况

每一次操作都操作了常数次的set和平衡树，总的复杂度是O(nlogn)的，空间复杂度是线性。

我用了两个set还用了一个splay为什么我的代码跑的这么快，完全没遇到过卡常

代码

很多地方可以写成函数来减少码量的，但是我懒得改了（于是就有了这个又臭又长的代码

理解思路就好代码不重要（雾

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
using namespace std;
const int N=5e5+5,M=1e5,INF=1073741824;
inline int read()
{
    int sum=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
        sum=sum*10+c-'0';
        c=getchar();
    }
    return sum;
}
inline void write(int x)
{
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

int n,m,c;
struct meow
{
    int sz;
    mutable int cs,root;
    inline bool operator < (const meow& qwe) const
    {
        return sz>qwe.sz;
    }
    meow(int sz=-INF,int cs=0,int root=0):sz(sz),cs(cs),root(root){}
};
set<meow> a;
#define smi set<meow>::iterator
set<meow> ans;

struct miaow
{
    int son[2],fa,sz;
    miaow(int ls=0,int rs=0,int fa=0,int sz=0):fa(fa),sz(sz)
    {
        son[0]=ls,son[1]=rs;
    }
}t[N];
int cou=1;
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define son(x,k) t[x].son[k]
#define fa(x) t[x].fa
#define sz(x) t[x].sz
inline int fx(int x)
{
    if(!fa(x))return -1;
    return rs(fa(x))==x;
}
inline void rt(int x)
{
    if(!fa(x))return;
    int y=fa(x),k=fx(x);
    if(fa(y))
    {
        son(fa(y),fx(y))=x;
    }
    fa(x)=fa(y);
    fa(y)=x;
    if(son(x,k^1))
    {
        fa(son(x,k^1))=y;
    }
    son(y,k)=son(x,k^1);
    son(x,k^1)=y;
}
inline void splay(int x,int md=0)
{
    int y=fa(x);
    while(y&&y!=md)
    {
        int z=fa(y);
        if(!z||z==md)
        {
            rt(x);
            return;
        }
        if(fx(y)==fx(x))rt(y);
        else rt(x);
        rt(x);
        y=fa(x);
    }
}

inline int findl(int x,int y)
{
    int o=x,fo=0;
    if(!o)return fo;
    while(1)
    {
        if(y==sz(o))
        {
            fo=o;
            break;
        }
        if(y>sz(o))
        {
            fo=o;
            if(!rs(o))break;
            o=rs(o);
        }
        else
        {
            if(!ls(o))break;
            o=ls(o);
        }
    }
    return fo;
}
inline int find(int x,int y)
{
    int o=x;
    if(!o)return o;
    while(1)
    {
        if(y==sz(o))break;
        else if(y>sz(o))
        {
            if(!rs(o))break;
            o=rs(o);
        }
        else
        {
            if(!ls(o))break;
            o=ls(o);
        }
    }
    return o;
}

inline void ansadd(int x)
{
    meow qwe=meow(x,1,0);
    smi o=ans.find(qwe);
    if(o==ans.end())
    {
        ans.insert(qwe);
    }
    else
    {
        o->cs+=1;
    }
}
inline void ansdel(int x)
{
    meow qwe=meow(x,1,0);
    smi o=ans.find(qwe);
    o->cs-=1;
    if(!o->cs)
    {
        ans.erase(o);
    }
}

inline void ins(smi o,int x)
{
    int zxc=find(o->root,x);
    if(!zxc)
    {
        t[cou]=miaow(0,0,0,x);
        o->root=cou;
        ansadd(o->sz+sz(cou));
        ++cou;
    }
    else
    {
        t[cou]=miaow(0,0,zxc,x);
        if(sz(zxc)<x)rs(zxc)=cou;
        else ls(zxc)=cou;
        splay(cou);
        if(!rs(cou))
        {
            while(rs(zxc))zxc=rs(zxc);
            ansdel(o->sz+sz(zxc));
            ansadd(o->sz+sz(cou));
        }
        o->root=cou;
        ++cou;
    }
}
inline void era(smi o,int x)
{
    int zxc=find(o->root,x);
    splay(zxc);
    if(!ls(zxc))
    {
        if(!rs(zxc))
        {
            o->root=0;
            ansdel(o->sz+sz(zxc));
        }
        else
        {
            int qwe=rs(zxc);
            while(ls(qwe))qwe=ls(qwe);
            splay(qwe);
            splay(zxc,qwe);
            fa(zxc)=0;
            ls(qwe)=0;
            o->root=qwe;
        }
    }
    else
    {
        if(!rs(zxc))
        {
            int qwe=ls(zxc);
            while(rs(qwe))qwe=rs(qwe);
            splay(qwe);
            splay(zxc,qwe);
            fa(zxc)=0;
            rs(qwe)=0;
            o->root=qwe;
            ansdel(o->sz+sz(zxc));
            ansadd(o->sz+sz(qwe));
        }
        else
        {
            int qwe=ls(zxc),asd=rs(zxc);
            while(rs(qwe))qwe=rs(qwe);
            while(ls(asd))asd=ls(asd);
            splay(qwe);
            splay(asd,qwe);
            fa(zxc)=0;
            ls(asd)=0;
            o->root=qwe;
        }
    }
}

inline void add(int x)
{
    meow qwe=meow(x,0,0);
    smi o=a.find(qwe),o2;
    if(o==a.end())
    {
        qwe.cs=1;
        o=a.insert(qwe).first;
        o2=o++;
        int asd=findl(o->root,c-x-1);
        if(asd)
        {
            splay(asd);
            if(!rs(asd))
            {
                o->root=0;
                ansdel(o->sz+sz(asd));
                o2->root=asd;
                ansadd(o2->sz+sz(asd));
            }
            else
            {
                int zxc=rs(asd);
                while(ls(zxc))zxc=ls(zxc);
                splay(zxc);
                splay(asd,zxc);
                fa(asd)=0,ls(zxc)=0;
                o->root=zxc;
                o2->root=asd;
                ansadd(o2->sz+sz(asd));
            }
        }
        if(o->cs==1)
        {
            smi o3=a.lower_bound(meow(c-o->sz-1,0,0));
            if(o3==o2)
            {
                smi o4=o;
                ++o4;
                era(o4,o->sz);
                ins(o3,o->sz);
            }
        }

        smi o3=a.lower_bound(meow(c-x-1,0,0));
        if(o3==o2)++o3;
        ins(o3,x);
    }
    else if(o->cs==1)
    {
        o->cs+=1;
        smi o3=a.lower_bound(meow(c-x-1,0,0));
        if(o3==o)
        {
            ++o3;
            era(o3,x);
            ins(o,x);
        }
    }
    else
    {
        o->cs+=1;
    }
}
inline void del(int x)
{
    meow qwe=meow(x,0,0);
    smi o=a.find(qwe),o2;
    if(o->cs>=3)
    {
        o->cs-=1;
    }
    else if(o->cs==2)
    {
        o->cs-=1;
        smi o3=a.lower_bound(meow(c-x-1,0,0));
        if(o3==o)
        {
            ++o3;
            era(o,x);
            ins(o3,x);
        }
    }
    else
    {
        o2=o++;
        if(o2->root)
        {
            if(o->root)
            {
                int asd=o->root,zxc=o2->root;
                while(ls(asd))asd=ls(asd);
                while(rs(zxc))zxc=rs(zxc);
                splay(asd);
                splay(zxc);
                ls(asd)=zxc;
                fa(zxc)=asd;
                o2->root=0;
                o->root=asd;
                ansdel(o2->sz+sz(zxc));
            }
            else
            {
                int asd=o2->root;
                while(rs(asd))asd=rs(asd);
                splay(asd);
                o->root=asd;
                o2->root=0;
                ansdel(o2->sz+sz(asd));
                ansadd(o->sz+sz(asd));
            }
            smi o3=a.lower_bound(meow(c-o->sz-1,0,0));
            if(o3==o2&&o->cs==1)
            {
                int ss=o->sz;
                era(o,ss);
                ++o;
                ins(o,ss);
            }
        }
        smi o3=a.lower_bound(meow(c-x-1,0,0));
        if(o3==o2)++o3;
        era(o3,x);
        a.erase(o2);
    }
}
inline void solve()
{
    n=read(),c=read();
    int lastans=0,cou=0;
    a.insert(meow());
    for(int i=1;i<=n;++i)
    {
        int x=read(),y=(read()^lastans)%c;
        if(x==1)
        {
            add(y);
            cou+=1;
        }
        else
        {
            del(y);
            cou-=1;
        }
        if(cou<2)
        {
            puts("EE");
            lastans=0;
        }
        else
        {
            int imax,imax2;
            smi qwe=ans.begin();
            imax=qwe->sz;
            qwe=a.begin();
            if(qwe->cs>=2)imax2=qwe->sz*2;
            else
            {
                imax2=qwe->sz;
                ++qwe;
                imax2+=qwe->sz;
            }
            lastans=max(imax,imax2%c);
            write(lastans),putchar('\n');
        }
    }
}
int main()
{
    solve();
}