笔记

做带末尾插入删除的区间信息维护）的数据结构题的方法：

分块

思路：每次插删操作暴力重构最后一块。

支持插删操作，支持在线

二进制分组

思路：若每次添加一个元素进数据结构里的复杂度比较高，则每次将这个元素单独放在最后一组，若最后一组与上一组的大小相同，就将这两组合并为同一组，不难发现最后得到的每个组大小都是 2 的次幂，并且互不相同，复杂度会是 $\log$级的。

不支持删除操作，支持在线

时间倒流

思路：转删除为插入。

支持无插入操作的删除操作，必须离线

线段树

boshi：你们怎么都在做 Unknown，这题讲什么的啊？
我：（解释一遍题意）
boshi：哦，这不就是个玄学＋共点圆吗？

类似 bzoj3821 玄学的操作，没有删除操作时，对于线段树上一个代表区间 $[l,r]$的点，当插入的点一直插到了 $r$时，才合并左右端点的信息，因为这时这个区间才有可能被整个询问。

不支持删除操作，支持在线

CDQ 分治（套 CDQ 分治）

假设询问的每个区间都是 $[1,r]$，那么一定存在一个时间，使得序列长度正好为 $r$且前 $r$个元素的状态与这个询问时一样。离线，将询问挂在 $r$位置。

CDQ 分治处理，每次分治区间 $[l,r]$，将 $[l,mid]$处理好（本题是建出凸包）后，用 $[mid+1,r]$上的询问来查询，然后将询问分块，递归处理。

至于查询的区间是 $[l,r]$呢，那么每次右半边区间询问的是左半边区间的一个后缀，用类似的方法套一次即可。

不支持删除操作，必须离线

操作树上点分治

所谓操作树，就是每一次插入，就给当前节点加入一个儿子。删除，就回退到父亲。那么若查询的是区间 $[1,r]$，其实查询的就是一条到根节点的路径。

用点分治，记当前重心为 $G$，则把当前连通块深度最浅节点到 $G$的路径构成的这个区间给提出来处理（本题是建凸包），然后将 $G$的子树中的所有询问统一处理。

若查询的区间是 $[l,r]$，同样，查询的是一个后缀，再套一个 CDQ 分治即可。

支持插删操作，必须离线

再探二进制分组

没看懂，有生之年可能会补。

双端插入操作树

定义开头指针 $a$和结尾指针 $b$。

插入开头：新建节点 $x$，$fa_x=a,a=x$

插入结尾：新建节点 $x$，$fa_x=b,b=x$

删除开头：$a=fa_a$

删除结尾：$b=fa_b$

每次询问是一条路径，将其拆成两条自底向上的链。

题解

论文里讲的很详细，略。

代码

被 HACK 了若干回，问了万 U 群里的 dalao 才知道，HACK 的是建凸壳的时候排序若 x 相同要按照 y 排序。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0,w=1;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q*w;
}
typedef double db;
typedef long long LL;
typedef pair<int,int> PR;
const int mod=998244353,N=300005,inf=0x3f3f3f3f;
int typ,m,n,tot,min_sz,rt,qjs;
int h[N],ne[N<<1],to[N<<1],fa[N],seq[N],sz[N],vis[N];LL ans[N];
PR qq[N],kqq1[N],kqq2[N];
struct point{int x,y;}p[N],qp[N];
vector<PR>question[N];

bool cmpp(point A,point B) {return A.x==B.x?A.y<B.y:A.x<B.x;}
LL operator * (point A,point B) {return 1LL*A.x*B.x+1LL*A.y*B.y;}
LL operator / (point A,point B) {return 1LL*A.x*B.y-1LL*A.y*B.x;}
point operator - (point A,point B) {return (point){A.x-B.x,A.y-B.y};}

void init() {
    for(RI i=0;i<=n;++i) h[i]=vis[i]=fa[i]=0,question[i].clear();
    n=tot=0;
}

void dfs_question(int x,int d,int las) {
    for(RI i=0;i<question[x].size();++i) {
        int kl=d-question[x][i].first;
        if(kl<=0) qq[++qjs]=question[x][i],qq[qjs].first=-kl+1;
    }
    for(RI i=h[x];i;i=ne[i])
        if(to[i]!=las&&!vis[to[i]]) dfs_question(to[i],d+1,x);
}
void work_cov(int l,int r,int js2) {
    static point cov[N],st[N];
    for(RI i=l;i<=r;++i) cov[i]=p[seq[i]];
    sort(cov+l,cov+r+1,cmpp);
    int top=0;
    for(RI i=l;i<=r;++i) {
        while(top>1&&(cov[i]-st[top-1])/(st[top]-st[top-1])<=0LL) --top;
        st[++top]=cov[i];
    }
    for(RI i=1;i<=js2;++i) {
        int L=1,R=top,res=0;
        db K=-(db)qp[kqq2[i].second].x/(db)qp[kqq2[i].second].y;
        while(L<=R) {
            int mid=(L+R)>>1;
            if(mid==1||(db)(st[mid].y-st[mid-1].y)/(db)(st[mid].x-st[mid-1].x)>=K)
                res=mid,L=mid+1;
            else R=mid-1;
        }
        ans[kqq2[i].second]=max(ans[kqq2[i].second],qp[kqq2[i].second]*st[res]);
    }
}
void lzz_is_duliu(int l,int r,int ql,int qr) {
    if(ql>qr) return;
    if(l==r) {
        for(RI i=ql;i<=qr;++i)
            ans[qq[i].second]=max(ans[qq[i].second],qp[qq[i].second]*p[seq[l]]);
        return;
    }
    int mid=(l+r)>>1,js1=0,js2=0;
    for(RI i=ql;i<=qr;++i)
        if(qq[i].first<=mid) kqq1[++js1]=qq[i];
        else kqq2[++js2]=qq[i];
    work_cov(l,mid,js2);
    for(RI i=1;i<=js1;++i) qq[ql+i-1]=kqq1[i];
    for(RI i=1;i<=js2;++i) qq[ql+js1-1+i]=kqq2[i];
    lzz_is_duliu(l,mid,ql,ql+js1-1);
    lzz_is_duliu(mid+1,r,ql+js1,qr);
}

void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void getrt(int x,int las,int SZ) {
    sz[x]=1;int bl=0;
    for(RI i=h[x];i;i=ne[i])
        if(to[i]!=las&&!vis[to[i]])
            getrt(to[i],x,SZ),sz[x]+=sz[to[i]],bl=max(bl,sz[to[i]]);
    bl=max(bl,SZ-sz[x]);
    if(bl<min_sz) min_sz=bl,rt=x;
}
void division(int x,int SZ) {
    int y=x,js=0;
    while(y&&!vis[y]) seq[++js]=y,y=fa[y];
    qjs=0,dfs_question(x,0,fa[x]);
    sort(qq+1,qq+1+qjs);
    lzz_is_duliu(1,js,1,qjs);
    vis[x]=1;
    for(RI i=h[x];i;i=ne[i]) {
        if(vis[to[i]]) continue;
        min_sz=inf,getrt(to[i],x,(to[i]==fa[x]?SZ-sz[x]:sz[to[i]]));
        division(rt,sz[to[i]]);
    }
}
void work() {
    int op,now=0,nowjs=0,qid=0,res=0;
    for(RI i=1;i<=m;++i) {
        op=read();
        if(op==1) {
            ++n,p[n].x=read(),p[n].y=read();
            add(now,n),add(n,now),fa[n]=now,now=n,seq[++nowjs]=n;
        }
        else if(op==2) now=fa[now],--nowjs;
        else {
            int l=read(),r=read();
            ++qid,qp[qid].y=read(),qp[qid].x=-read();
            question[seq[r]].push_back((PR){r-l,qid});
        }
    }
    for(RI i=1;i<=qid;++i) ans[i]=LLONG_MIN;
    min_sz=inf,rt=0,getrt(0,-1,n),division(rt,n);
    for(RI i=1;i<=qid;++i) res^=(ans[i]%mod+mod)%mod;
    printf("%d\n",res);
}

int main()
{
    typ=read();
    while(m=read()) init(),work();
    return 0;
}