魔法逝

原题链接

$\quad $ 先考虑如何处理 \(max(a_p + a_q ,b_p + b_q)\) ，当 \(a_p +a_q \ge b_p +b_q\) 时，\(a_p -b_p \ge b_q -a_q\) 。

$\quad $ 那我们记法杖的 \(\delta _{p}=a_p -b_p\) ，咒语的 \(\delta_{q}=b_q -a_q\) ，那么 \(max(a_p + a_q ,b_p + b_q)\) 的取值就只和 \(\delta_{p}\) 和 \(\delta_{q}\) 的大小有关。

$\quad $ 可以发现 \(\delta \in [-2.5 \times 10^5,2.5 \times 10^5]\) ，这个数据范围建一棵线段树的话内存是可以接受的（当然动态开点最好，但是我学得不好）。
$\quad $ 对于每一个特定的 \(\delta\) ，我们开两个 \(multiset\) 来分别记录该点的所有法杖和咒语。
$\quad $ 细节都在注释里了。

#define yhl 0
#include<bits/stdc++.h>
using namespace std;
#define ld (x<<1)
#define rd (x<<1|1)
#define IN_MA (1e8)
const int N=1e6+10,res=2.5e5+1;
int m,flag,lan;
struct stu{
    int l,r,a,al,b,bl,ans;
}s[N<<2];
multiset<pair<int,int> >q[N][2];
//只给叶子节点开即可。
inline int min(int x,int y){return x<y?x:y;}
void push_up(int x){
    s[x].ans=min({s[ld].ans,s[rd].ans,s[rd].a+s[ld].al,s[ld].b+s[rd].bl});
    //这里不仅要算上左右子树的答案，还要找出跨左右子树的答案进行更新。
    s[x].a=min(s[ld].a,s[rd].a);
    s[x].al=min(s[ld].al,s[rd].al);
    s[x].b=min(s[ld].b,s[rd].b);
    s[x].bl=min(s[ld].bl,s[rd].bl);
}
void build(int x,int l,int r){
    s[x].l=l,s[x].r=r;
    if(l==r){
        s[x].ans=IN_MA;
        s[x].a=IN_MA;
        s[x].b=IN_MA;
        s[x].al=IN_MA;
        s[x].bl=IN_MA;
        q[s[x].l][yhl].insert(make_pair(IN_MA,IN_MA));
        q[s[x].l][1].insert(make_pair(IN_MA,IN_MA));
        //全初始化成极大值，在两个set里插入极大值，这样就不用判空了。
        return;
    }
    int mid=l+r>>1;
    build(ld,l,mid);
    build(rd,mid+1,r);
    push_up(x);
}
void add(int x,int pos,pair<int,int> op,bool is_a){
    if(s[x].l==s[x].r){
        q[s[x].l][is_a].insert(op);
        if(is_a){
            s[x].a=min(s[x].a,op.first);
            s[x].b=min(s[x].b,op.second);
        }else{
            s[x].al=min(s[x].al,op.first);
            s[x].bl=min(s[x].bl,op.second);
        }
        if(q[s[x].l][is_a].size()&&q[s[x].l][is_a^1].size())
            s[x].ans=(*q[s[x].l][is_a].begin()).first+(*q[s[x].l][is_a^1].begin()).first;
        //在同一位置，对于法杖或咒语来说，a、b之间的差值是一定的，当a最小时，b也最小。
        return;
    }
    int mid=s[x].l+s[x].r>>1;
    if(pos<=mid)add(ld,pos,op,is_a);
    else add(rd,pos,op,is_a);
    push_up(x);
}
void del(int x,int pos,pair<int,int>op,bool is_a){
    if(s[x].l==s[x].r){
        q[s[x].l][is_a].erase(q[s[x].l][is_a].find(op));
        if(is_a){
            s[x].a=(*q[s[x].l][1].begin()).first;
            s[x].b=(*q[s[x].l][1].begin()).second;
        }else{
            s[x].al=s[x].bl=IN_MA;
            s[x].al=(*q[s[x].l][yhl].begin()).first;
            s[x].bl=(*q[s[x].l][yhl].begin()).second;
        }
        s[x].ans=(*q[s[x].l][is_a].begin()).first+(*q[s[x].l][is_a^1].begin()).first;
        return;
    }
    int mid=s[x].l+s[x].r>>1;
    if(pos<=mid)del(ld,pos,op,is_a);
    else del(rd,pos,op,is_a);
    push_up(x);
}
int main(){
    scanf("%d%d",&m,&flag);
    build(1,1,500001);
    //偏移量最小设置为2.5e5+1。
    while(m--){
        int op,fl,a,b;
        scanf("%d%d%d%d",&op,&fl,&a,&b);
        if(flag)a^=lan,b^=lan;
        if(op==1){
            if(fl)add(1,res+b-a,make_pair(a,b),yhl);
            else add(1,res+a-b,make_pair(a,b),1);
        }else{
            if(fl)del(1,res+b-a,make_pair(a,b),yhl);
            else del(1,res+a-b,make_pair(a,b),1);
        }
        lan=s[1].ans>=1e8?yhl:s[1].ans;;
        printf("%d\n",lan);
    }
    return yhl;
}