【学习笔记】我的生命已如风中残烛

题意：有一个初始为空集的集合$S$，进行$n$次操作：

1. 向集合$S$中插入一个数$w$
2. 选择区间$[0,w]$中的一个数$x$，以及集合中两个不同的数$i,j$，使得$(x+i)\oplus (x+j)$最大。

$n\le 10^5,w\in [0,2^V)$。

不要一上来就瞎转化。

考虑给定$i,j$，最优的$x\in [0,w]$的取值可能是什么。

首先，当$x=0$时，答案是$i\oplus j$。因此答案一定不会比$i\oplus j$大。因此，一定存在一个$i,j$在二进制下的第$k$位（从低到高），在之前异或的结果是$1$，加上$x$过后异或的结果是$0$。不妨取出这样的最大的$k$，则$>k$的二进制位异或结果没有变化，因此我们将$i,j$的后$k$位截取出来，不妨假设$i$的这一位$0$，$j$的这一位是$1$，则$i<j$。

我们钦定$x\in [0,2^k)$，因为将$x$减去$2^k$并不会使$i,j$的后$k$位发生变化。显然$i,j$至多只会进一次位，如果只有$j$进位显然不优，因此要么$i,j$都不进位，要么$i,j$都进位。 前者对应的是$i,j$，后者对应的是$i+x?2^k,j+x?2^k$。但是无论如何，这两个数异或后的结果都至少为$j?i$。

现在，考虑当$i$的最高位第一次变成$1$时，如果此时$j$的最高位是$0$，则说明$j$发生了进位，因此$i$也要发生进位，并且我们要求最终$i,j$的最高位为$0$。前者告诉我们$2^{k?1}?i+j\ge 2^k$，后者告诉我们$2^k?i+j?2^k<2^{k?1}$，两者恰好矛盾。因此此时$j$的最高位只能是$1$（并且没有发生进位），那么我们发现此时$i\oplus j$恰好取到了最小值$j?i$，并且$x$也取到了最小值。

因此，对于一对$(i,j)$，有用的$x$只有$\log V$个，用$\text{set}$维护即可。

显然$i,j$只能是相邻的两个数。（这个结论我之前模拟赛的时候就推过。。。）

复杂度$O(n\log n\log V)$。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,m;
set<ll>s0;
set<pair<ll,ll>>s;
void ins1(ll w,ll z){
    auto it=s.lower_bound({w+1,0}),it0=it;
    if(it!=s.begin()){
        it0--;
        if(it0->se<=z)return;
    }
    it=s.lower_bound({w,0});
    while(it!=s.end()&&it->se>=z){
        s.erase(it),it=s.lower_bound({w,0});
    }
    s.insert({w,z});
}
void ins0(ll i,ll j){
    ins1(0,i^j);
    for(int k=0;k<m;k++){
        if((i>>k&1)^(j>>k&1)){
            if(i>>k&1)swap(i,j);
            ll x=i&((1ll<<k+1)-1),y=j&((1ll<<k+1)-1),z=((i^x)^(j^y))+y-x,w=(1ll<<k)-x;
            if(y+w<(1ll<<k+1)){
                ins1(w,z);
            }
        }
    }
}
void ins(ll w){
    auto it=s0.lower_bound(w),it0=it;
    if(it!=s0.begin())it0--,ins0(w,*it0);
    if(it!=s0.end())ins0(w,*it);
    s0.insert(w);
}
signed main(){
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int op;ll w;
        cin>>op>>w;
        if(op==1)ins(w);
        else{
            cout<<(--s.upper_bound({w,inf}))->se<<"\n";
        }
    }
}