蒟蒻求助

WA #2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define alpha 0.75
#define INF 1000000007
using namespace std;
const int N=2e6;
int cnt,root,D,nn;
struct Node{int w,l[2],r[2],d[2],size,ch[2],s;}a[N];
struct Point{int d[2];int w;bool operator <(const Point &a)const{return d[D]<a.d[D];}}tmp[N];
void pushup(int root)
{
    a[root].s=a[a[root].ch[0]].s+a[a[root].ch[1]].s+a[root].w;
    a[root].size=a[a[root].ch[0]].size+a[a[root].ch[1]].size+1;
    a[root].l[0]=min(a[root].d[0],min(a[a[root].ch[0]].l[0],a[a[root].ch[1]].l[0]));
    a[root].l[1]=min(a[root].d[1],min(a[a[root].ch[0]].l[1],a[a[root].ch[1]].l[1]));
    a[root].r[0]=max(a[root].d[0],max(a[a[root].ch[0]].r[0],a[a[root].ch[1]].r[0]));
    a[root].r[1]=max(a[root].d[1],max(a[a[root].ch[0]].r[1],a[a[root].ch[1]].r[1]));
}
void build(int &root,int l,int r,int d)
{
    if(l>r)return;
    int mid=(l+r)>>1;root=++cnt;
    D=d;nth_element(tmp+l,tmp+mid+1,tmp+r+1);
    a[root].d[0]=tmp[mid].d[0],a[root].d[1]=tmp[mid].d[1];
    a[root].w=tmp[mid].w;
    build(a[root].ch[0],l,mid-1,d^1),build(a[root].ch[1],mid+1,r,d^1);
    pushup(root);
}
void split(int root)
{
    if(a[root].ch[0])split(a[root].ch[0]);
    tmp[++nn]=(Point){{a[root].d[0],a[root].d[1]},a[root].w};
    if(a[root].ch[1])split(a[root].ch[1]);
}
void ins(int &root,int D,Point p)
{
    if(!root)
    {
        root=++cnt;
        a[cnt].l[0]=a[cnt].r[0]=a[cnt].d[0]=p.d[0];
        a[cnt].l[1]=a[cnt].r[1]=a[cnt].d[1]=p.d[1];
        a[cnt].s=a[cnt].w=p.w;a[cnt].size=1;
        a[cnt].ch[0]=a[cnt].ch[1]=0;
        return;
    }
    int d=p.d[D]>=a[root].d[D];
    ins(a[root].ch[d],D^1,p);
    pushup(root);
    if(a[a[root].ch[d]].size>a[root].size*alpha)
        nn=0,split(root),build(root,1,nn,D);
}
bool in(int xa1,int ya1,int xa2,int ya2,int xb1,int yb1,int xb2,int yb2)
{
    return xb1>=xa1&&xb2<=xa2&&yb1>=ya1&&yb2<=ya2;
}
bool out(int xa1,int ya1,int xa2,int ya2,int xb1,int yb1,int xb2,int yb2)
{
    return xb1>xa2||xb2<xa1||yb1>ya2||yb2<ya1;
}
int query(int root,int x1,int y1,int x2,int y2)
{
    if(!root)return 0;
    if(in(x1,y1,x2,y2,a[root].l[0],a[root].l[1],a[root].r[0],a[root].r[1]))return a[root].s;
    if(out(x1,y1,x2,y2,a[root].l[0],a[root].l[1],a[root].r[0],a[root].r[1]))return 0;
    int ans=0;
    if(in(x1,y1,x2,y2,a[root].d[0],a[root].d[1],a[root].d[0],a[root].d[1]))ans+=a[root].w;
    ans+=query(a[root].ch[0],x1,y1,x2,y2)+query(a[root].ch[1],x1,y1,x2,y2);
    return ans;
}
int getin()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
int n;
int main()
{
    n=getin();int lstans=0;
    a[0].l[0]=a[0].l[1]=INF;
    a[0].r[0]=a[0].r[1]=-INF;
    for(int i=1;i<=n;i++)
    {
        int opt=getin();
        if(opt==1)
        {
            int x=getin()^lstans,y=getin()^lstans,A=getin()^lstans;
            ins(root,0,(Point){{x,y},A});
        }
        else if(opt==2)
        {
            int x1=getin()^lstans,y1=getin()^lstans,x2=getin()^lstans,y2=getin()^lstans;
            printf("%d\n",lstans=query(root,x1,y1,x2,y2));
        }
        else break;
    }
}