点分治还能这么用，感觉好妙啊
然而我不到200行的程序居然错了10多个地方，调了一晚上，简直zz
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #define R register using namespace std; typedef long long LL; inline int read() { int x=0;bool f=0;char c=getchar(); for (;c<'0'||c>'9';c=getchar()) f=c=='-'?1:0; for (;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0'; return f?-x:x; } const int N=500005,P=998244353,S=10; int n,m,p,q,sn[N],br[N],fa[N],dis[N],xi[N],yi[N],seq[N],sq, hd[N],nxt[N],xq[N],yq[N],lim[N], rt,siz,sz[N],s2[N],pth[N],pc; LL ans[N]; bool vis[N],inp[N]; struct na {int a,x,y,id;}e[N],e2[N],*pt,*pt2; inline bool cmp(const na &a,const na &b){ return (LL)a.x*b.y<(LL)a.y*b.x;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! } inline bool cmp2(const na &a,const na &b){ if (a.x==b.x) return a.y<b.y; return a.x<b.x; } //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! struct cvx{ int n,p,x[N],y[N]; inline bool cal(int x,int y,int x1,int y1,int x2,int y2){ x1-=x,x2-=x,y1-=y,y2-=y; return (LL)x1*y2-(LL)x2*y1>=0;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! } inline void insert(int a,int b){ while (n>1&&cal(x[n-1],y[n-1],x[n],y[n],a,b)) n--; x[++n]=a,y[n]=b; } inline LL calc(int a,int b){ LL rec=(LL)x[p]*a+(LL)y[p]*b,r2;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! while (p<n){ r2=(LL)x[p+1]*a+(LL)y[p+1]*b; if (r2>rec) rec=r2,p++; else break; } return rec; } }cv; void solve(int l,int r,int a,int b) { if (r-l<S||b-a<S) { for (R int i=a;i<=b;i++) for (R int j=l;j<=r;j++) if (pt[j].a<=e[i].a)//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ans[e[i].id]=max(ans[e[i].id],(LL)e[i].x*pt[j].x +(LL)e[i].y*pt[j].y); return; } cv.n=0;cv.p=1; int mid=l+r>>1,l1=a,l2=0,p1=l,p2=0; for (R int i=l;i<=r;i++) if (pt[i].a<=mid) cv.insert(pt[i].x,pt[i].y); for (R int i=a;i<=b;i++) if (e[i].a>mid) ans[e[i].id]=max(ans[e[i].id],cv.calc(e[i].x,e[i].y)); for (R int i=a;i<=b;i++) (e[i].a<=mid)?e[l1++]=e[i]:e2[++l2]=e[i]; for (R int i=1;i<=l2;i++) e[l1++]=e2[i]; for (R int i=l;i<=r;i++) (pt[i].a<=mid)?pt[p1++]=pt[i]:pt2[++p2]=pt[i]; for (R int i=1;i<=p2;i++) pt[p1++]=pt2[i]; solve(l,r-p2,a,b-l2); solve(r-p2+1,r,b-l2+1,b); } void dfs_root(int u,int f) { sz[u]=1;s2[u]=0; for (int v=sn[u];v;v=br[v]) if (v!=f&&!vis[v]) dfs_root(v,u),sz[u]+=sz[v],s2[u]=max(s2[u],sz[v]); if (fa[u]!=f&&!vis[fa[u]]) dfs_root(fa[u],u),sz[u]+=sz[fa[u]],s2[u]=max(s2[u],sz[fa[u]]); s2[u]=max(s2[u],siz-sz[u]); if (s2[u]<s2[rt]) rt=u; } inline void dfs_add(int u) { sz[u]=1; //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! if (u!=rt) seq[++sq]=u,inp[u]=1; for (int i=hd[u];i;i=nxt[i]) if (!inp[lim[i]]) e[++m]=(na){min(pc,dis[rt]-dis[lim[i]]+1),xq[i],yq[i],i}; for (int v=sn[u];v;v=br[v]) if (!vis[v]) dfs_add(v),sz[u]+=sz[v]; //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! } void dfs(int u,int pr_siz) { m=pc=sq=0; for (int p=u;!vis[p];p=fa[p]) pth[++pc]=p; if (pth[pc]==1) pc--; for (int i=1;i<=pc;i++) pt[i]=(na){i,xi[pth[i]],yi[pth[i]],0}; vis[u]=1; dfs_add(u); for (int i=1;i<=sq;i++) inp[seq[i]]=0;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! if (m>S&&pc>S) { sort(e+1,e+m+1,cmp); sort(pt+1,pt+pc+1,cmp2); //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! solve(1,pc,1,m); } else { for (int i=1;i<=m;i++) for (int j=1;j<=e[i].a;j++)//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ans[e[i].id]=max(ans[e[i].id],(LL)e[i].x*pt[j].x +(LL)e[i].y*pt[j].y); } for (int v=sn[u];v;v=br[v]) if (!vis[v]) { rt=0;siz=s2[0]=sz[v]; dfs_root(v,0); dfs(rt,siz); } if (!vis[fa[u]]) { rt=0;siz=s2[0]=pr_siz-sz[u]; dfs_root(fa[u],0); dfs(rt,siz); } } int main() { // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); read(); while (m=read()) { memset(sn,0,sizeof sn); memset(hd,0,sizeof hd); n=p=1;q=0; sq=0; //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! for (int i=1;i<=m;i++) { int op=read(),l,r; if (op==1) { br[++n]=sn[p],sn[p]=n,fa[n]=p,dis[n]=dis[p]+1,p=n; seq[++sq]=p; xi[p]=read(),yi[p]=read(); } else if (op==2) sq--,p=fa[p]; else { l=read(),r=read(); lim[++q]=seq[l]; yq[q]=read(),xq[q]=-read(); nxt[q]=hd[seq[r]];hd[seq[r]]=q; ans[q]=-5*1e18; } } // pt=e+n+1,pt2=e2+n+1;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! pt=e+q+2,pt2=e2+q+2; memset(vis,0,sizeof vis); rt=0;s2[0]=siz=n;vis[0]=1; dfs_root(1,0); dfs(rt,n); int rec=0; for (int i=1;i<=q;i++) rec^=(int)((ans[i]%P+P)%P); // for (int i=1;i<=q;i++) printf("%d\n",(int)((ans[i]%P+P)%P)); printf("%d\n",rec); } return 0; }