KDT大常数选手求卡常

command_block @ 2020-10-25 14:09:49

by command_block @ 2020-10-25 14:10:02

#include<algorithm>
#include<cstdio>
#define MaxN 200500
using namespace std;
int read(){
  int X=0;char ch=0,w=0;
  while(ch<48||ch>57)ch=getchar(),w|=(ch=='-');
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return w?-X:X;
}
struct Point{int x,y,v;}p[MaxN];
int tot;
bool cmpX(const Point &A,const Point &B)
{return A.x<B.x;}
bool cmpY(const Point &A,const Point &B)
{return A.y<B.y;}
struct Node{
  int xl,yl,xr,yr,l,r,s,c;
  void leaf(Point &P){
    xl=xr=P.x;yl=yr=P.y;
    s=P.v;c=1;
  }
}a[MaxN<<1];
int tn,rt,rub[MaxN<<1],tb;
int cre(){
  if (!tb)return ++tn;
  int u=rub[tb--];
  a[u]=(Node){0,0,0,0,0,0};
  return u;
}
void pia(int u)
{
  if (a[u].l==a[u].r){
    p[++tot]=(Point){a[u].xl,a[u].yl,a[u].s};
    rub[++tb]=u;return ;
  }pia(a[u].l);pia(a[u].r);
  rub[++tb]=u;
}
bool chk(int u)
{return a[u].c>3&&max(a[a[u].l].c,a[a[u].r].c)*5>a[u].c*3;}
inline void up(int u)
{
  int l=a[u].l,r=a[u].r;
  a[u].s=a[l].s+a[r].s;
  a[u].c=a[l].c+a[r].c;
  a[u].xl=min(a[l].xl,a[r].xl);
  a[u].yl=min(a[l].yl,a[r].yl);
  a[u].xr=max(a[l].xr,a[r].xr);
  a[u].yr=max(a[l].yr,a[r].yr);
}
void build(int l,int r,int &u,bool kd)
{
  u=cre();
  if (l==r){a[u].leaf(p[l]);return ;}
  int mid=(l+r)>>1;
  nth_element(p+l,p+mid,p+r+1,kd ? cmpX : cmpY);
  build(l,mid,a[u].l,!kd);
  build(mid+1,r,a[u].r,!kd);
  up(u);
}
Point wfp,reb;
void ins(int u,bool kd)
{
  if (a[u].l==a[u].r){
    int v0=cre(),v1=cre();
    a[v0]=a[u];a[v1].leaf(wfp);
    a[u].l=v0;a[u].r=v1;up(u);
    return ;
  }int ls=a[u].l;
  if (a[ls].xl<=wfp.x&&wfp.x<=a[ls].xr
    &&a[ls].yl<=wfp.y&&wfp.y<=a[ls].yr)
    ins(ls,!kd);
  else ins(a[u].r,!kd);
  up(u);
  if (chk(u)){reb.x=u;reb.y=kd;}
}
void insert()
{
  if (!tn){a[tn=1].leaf(wfp);return ;}
  reb.x=0;ins(1,0);
  if (reb.x){
    tot=0;pia(reb.x);
    int tmp;build(1,tot,tmp,reb.y);
  }
}
Node wf;
void qry(int u=1)
{ 
  if (wf.xr<a[u].xl||a[u].xr<wf.xl||wf.yr<a[u].yl|a[u].yr<wf.yl)return ;
  if (wf.xl<=a[u].xl&&a[u].xr<=wf.xr&&wf.yl<=a[u].yl&&a[u].yr<=wf.yr)
    {wf.s+=a[u].s;return ;}
  qry(a[u].l);qry(a[u].r);
}
int n,las;
int main()
{
  while(1){
    int op=read();
    if (op==1){
      wfp.x=read()^las;
      wfp.y=read()^las;
      wfp.v=read()^las;
      insert();
    }if (op==2){
      wf.xl=read()^las;wf.yl=read()^las;
      wf.xr=read()^las;wf.yr=read()^las;
      wf.s=0;qry();
      printf("%d\n",las=wf.s);
    }if (op==3)break;
  }return 0;
}

by AThousandSuns @ 2020-10-25 14:13:42

定期重构好（

by command_block @ 2020-10-25 14:52:54

一般的定期重构复杂度是 O(n\sqrt{n\log n}) 的啊，O(n\sqrt{n}) 太难写了……

by command_block @ 2020-10-25 15:03:39

定期重构常数确实小，跑到接近 4s 了。

by command_block @ 2020-10-25 18:59:02

by panyf @ 2020-10-25 19:01:40

@command_block 定期重构怎么做到 O(n\sqrt n) 啊

by command_block @ 2020-10-26 18:26:44

@panyf https://www.luogu.com.cn/blog/command-block/kdt-xiao-ji

by Uzumaki @ 2021-05-31 20:09:29

pia!