20pts 其余 MLE 求助

rt

#include <algorithm>
#define LL long long
inline LL read(){LL x=0,f=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if (c=='-')f=-1;for (;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);return x*f;}
inline void write(LL x,char c='\n'){if (x){if (x<0)x=-x,putchar('-');char a[30];short l;for (l=0;x;x/=10)a[l++]=x%10^48;for (l--;l>=0;l--)putchar(a[l]);}else putchar('0');putchar(c);}
using namespace std;

const double alpha = 0.75;
const int N = 5e5+10;
struct Point{int x,y,val;}point[N];
int idx[N],tot,root,cnt,n,lastans;
int ls[N],rs[N],d[N],mx[N][2],mn[N][2],siz[N],sum[N];
inline bool cmpx(int x,int y){return point[x].x<point[y].y;}
inline bool cmpy(int x,int y){return point[x].y<point[y].y;}
void save(int u){if (!u)return ;save(ls[u]);idx[++tot]=u;save(rs[u]);}
inline void pushup(int u){
    siz[u]=siz[ls[u]]+siz[rs[u]]+1;
    sum[u]=sum[ls[u]]+sum[rs[u]]+point[u].val;
    mx[u][0]=mn[u][0]=point[u].x;
    mx[u][1]=mn[u][1]=point[u].y;
    if (ls[u])
        mx[u][0]=max(mx[u][0],mx[ls[u]][0]),
        mn[u][0]=min(mn[u][0],mn[ls[u]][0]),
        mx[u][1]=max(mx[u][1],mx[ls[u]][1]),
        mn[u][1]=min(mn[u][1],mn[ls[u]][1]);
    if (rs[u])
        mx[u][0]=max(mx[u][0],mx[rs[u]][0]),
        mn[u][0]=min(mn[u][0],mn[rs[u]][0]),
        mx[u][1]=max(mx[u][1],mx[rs[u]][1]),
        mn[u][1]=min(mn[u][1],mn[rs[u]][1]);
}
int build(int l,int r){
    if (l>r)return 0;
    int mid=(l+r)>>1;
    double ave1=0,ave2=0,sum1=0,sum2=0;
    for (int i=l;i<=r;i++)ave1+=point[idx[i]].x,ave2+=point[idx[i]].y;
    ave1/=(r-l+1),ave2/=(r-l+1);
    for (int i=l;i<=r;i++)
        sum1+=(ave1-point[idx[i]].x)*(ave1-point[idx[i]].x),
        sum2+=(ave2-point[idx[i]].y)*(ave2-point[idx[i]].y);
    if (sum1>sum2)nth_element(idx+l,idx+mid,idx+r+1,cmpx),d[mid]=1;
    else nth_element(idx+l,idx+mid,idx+r+1,cmpy),d[mid]=2;
    ls[mid]=build(l,mid-1);
    rs[mid]=build(mid+1,r);
    pushup(mid);
    return mid;
}
inline void rebuild(int &u){tot=0;save(u);u=build(1,tot);}
inline bool notbalance(int u){return alpha*siz[u]<=(double)max(siz[ls[u]],siz[rs[u]]);}
void Insert(int &u,int pos){
    if (!u){u=pos;pushup(u);return ;}
    if (d[u]==1)
        if (point[pos].x<=point[u].x)
            Insert(ls[u],pos);
        else
            Insert(rs[u],pos);
    else
        if (point[pos].y<=point[u].y)
            Insert(ls[u],pos);
        else
            Insert(rs[u],pos);
    pushup(u);
    if (notbalance(u))rebuild(u);
}
int query(int u,int x1,int y1,int x2,int y2){
    if (!u||x2<mn[u][0]||x1>mx[u][0]||y2<mn[u][1]||y1>mx[u][1])return 0;
    if (x1<=mn[u][0]&&x2>=mx[u][0]&&y1<=mn[u][1]&&y2>=mx[u][1])return sum[u];
    int in_or_out=0;//判断当前点是否在所求矩形(x1,y1)(x2,y2)中 
    if (x1<=point[u].x&&x2>=point[u].x&&y1<=point[u].y&&y2>=point[u].y)in_or_out+=point[u].val;
    return query(ls[u],x1,y1,x2,y2)+query(rs[u],x1,y1,x2,y2)+in_or_out;
}
int main(){
    n=read();
    while (1){
        int opt=read();
        if (opt==3)break;
        if (opt==1){
            cnt++;
            point[cnt].x=read()^lastans;
            point[cnt].y=read()^lastans;
            point[cnt].val=read()^lastans;
            Insert(root,cnt);
        }
        if (opt==2){
            int x1=read()^lastans,y1=read()^lastans;
            int x2=read()^lastans,y2=read()^lastans;
            write(lastans=query(root,x1,y1,x2,y2));
        }
    }
    return 0;
}