题意：支持修改的矩形第 \(k\) 大。
题解：动态开点权值线段树 套 Kd-tree。
然后也没什么难的但就是写不对。。。调了两天才调出来然后发现跑的巨慢，于是又%了一发Claris'题解，跑的真快QAQ。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=100010,B=40,Inf=1e9; const double A=0.71;
int n,D,T;
struct P {int d[2],w;
inline bool operator < (const P& that) const
{return d[D]<that.d[D];}
}p[N];
struct node {
int mx[2],mn[2],fa,sz,dim,sum,lc,rc; P p;
#define ls (t[tr].lc)
#define rs (t[tr].rc)
#define fa(tr) (t[tr].fa)
#define dim(tr) (t[tr].dim)
#define mx(tr,i) (t[tr].mx[i])
#define mn(tr,i) (t[tr].mn[i])
#define P(tr,i) (t[tr].p.d[i])
#define sum(tr) (t[tr].sum)
#define sz(tr) (t[tr].sz)
#define vl(tr) (t[tr].p.w)
}t[N*B];
namespace KD {
int buf[N],cnt,tot,top;
inline void upd(int tr,int dim) {
for(R i=0;i<2;++i) {
mn(tr,i)=mx(tr,i)=P(tr,i);
if(ls) mx(tr,i)=max(mx(tr,i),mx(ls,i)),mn(tr,i)=min(mn(tr,i),mn(ls,i)),fa(ls)=tr;
if(rs) mx(tr,i)=max(mx(tr,i),mx(rs,i)),mn(tr,i)=min(mn(tr,i),mn(rs,i)),fa(rs)=tr;
} sz(tr)=sz(ls)+sz(rs)+1; sum(tr)=sum(ls)+sum(rs)+vl(tr); dim(tr)=dim;
}
inline void flat(int tr) {
if(ls) flat(ls); p[++cnt]=t[tr].p,buf[++top]=tr;
if(rs) flat(rs);
}
inline int cre() {return top?buf[top--]:++tot;}
inline int build(int l,int r,int dim) {
if(l>r) return 0; R tr=cre(),md=l+r>>1;
D=dim,nth_element(p+l,p+md,p+r+1);
t[tr].p=p[md]; ls=build(l,md-1,dim^1),rs=build(md+1,r,dim^1);
upd(tr,dim); return tr;
}
inline void ins(int& tr,int fa,int dim,const P& p) {
if(!tr) return tr=cre(),t[tr].p=p,vl(tr)=1,ls=rs=0,upd(tr,dim),void();
if(P(tr,0)==p.d[0]&&P(tr,1)==p.d[1]) ++vl(tr);
else P(tr,dim)>p.d[dim]?ins(ls,tr,dim^1,p):ins(rs,tr,dim^1,p);
upd(tr,dim); if(sz(tr)*A<max(sz(ls),sz(rs))) T=tr;
}
inline bool in(const node& p,const node& U) {
return U.mn[0]<=p.mn[0]&&p.mx[0]<=U.mx[0]
&&U.mn[1]<=p.mn[1]&&p.mx[1]<=U.mx[1];
}
inline bool nin(const node& p,const node& U) {
return U.mn[0]>p.mx[0]||U.mx[0]<p.mn[0]
||U.mn[1]>p.mx[1]||U.mx[1]<p.mn[1];
}
inline int query(int tr,const node& dst) {
if(!tr||nin(t[tr],dst)) return 0; if(in(t[tr],dst)) return sum(tr);
R ret=1; for(R i=0;i<=1;++i) ret=ret&&(P(tr,i)<=dst.mx[i]&&P(tr,i)>=dst.mn[i]);
return ret*vl(tr)+query(ls,dst)+query(rs,dst);
}
}
#undef ls
#undef rs
int rt[N*B],ls[N*B],rs[N*B],cnt,RT;
inline void change(int& tr,int l,int r,const P& p) {
if(!tr) tr=++cnt; KD::ins(rt[tr],0,0,p);
if(T) { KD::flat(T);
if(T==rt[tr]) rt[tr]=KD::build(1,KD::cnt,0);
else if(t[fa(T)].lc==T) t[fa(T)].lc=KD::build(1,KD::cnt,dim(T));
else if(t[fa(T)].rc==T) t[fa(T)].rc=KD::build(1,KD::cnt,dim(T));
T=KD::cnt=0;
}
if(l==r) return ; R md=l+r>>1;
p.w<=md?change(ls[tr],l,md,p):change(rs[tr],md+1,r,p);
}
inline int query(int& tr,int l,int r,int k,const node& d) {
if(l==r) return l; R md=l+r>>1,sz=KD::query(rt[rs[tr]],d);// cout<<sz<<endl;
return k<=sz?query(rs[tr],md+1,r,k,d):query(ls[tr],l,md,k-sz,d);
}
inline void main() {
g(),n=g();
for(R i=1,op,x,y,k,ans=0;i<=n;++i) {
op=g(),x=g()^ans,y=g()^ans;
if(op&1) {
register P p; p.d[0]=x,p.d[1]=y,p.w=g()^ans;
change(RT,1,Inf,p);
} else { register node p;
p.mn[0]=x,p.mn[1]=y,p.mx[0]=g()^ans,p.mx[1]=g()^ans,k=g()^ans;
R tmp=KD::query(rt[RT],p);
if(tmp<k) puts("NAIVE!ORZzyz."),ans=0;
else printf("%d\n",ans=query(RT,1,1e9,k,p));
}
}
}
} signed main() {Luitaryi::main(); return 0;}
#include<iostream>
#include<cstdio>
#include<algorithm>
#define R register int
using namespace std;
namespace Luitaryi {
static char b[1<<15],*S=b,*T=b;
#define getchar() (S==T&&(T=(S=b)+fread(b,1,1<<15,stdin),S==T)?EOF:*S++)
inline int g() { R x=0,f=1;
register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=100010,B=16,Inf=1e9; const double A=0.8;
int n,D,cnt,tot=1,ans,k,p[N],ct;
struct node {int d[2],lc,rc,mx[2],mn[2],sz;
#define ls (t[x].lc)
#define rs (t[x].rc)
#define sz(x) (t[x].sz)
#define mx(x,i) (t[x].mx[i])
#define mn(x,i) (t[x].mn[i])
#define p(x,i) (t[x].d[i])
}t[N*B],s;
inline bool cmp(const int& a,const int& b) {return p(a,D)<p(b,D);}
#define cmx(x,y) ((x)<(y)?(x)=(y):0)
#define cmn(x,y) ((x)>(y)?(x)=(y):0)
inline void upd(int x) {
if(ls)
cmx(mx(x,0),mx(ls,0)),cmn(mn(x,0),mn(ls,0)),
cmx(mx(x,1),mx(ls,1)),cmn(mn(x,1),mn(ls,1));
if(rs)
cmx(mx(x,0),mx(rs,0)),cmn(mn(x,0),mn(rs,0)),
cmx(mx(x,1),mx(rs,1)),cmn(mn(x,1),mn(rs,1));
sz(x)=sz(ls)+sz(rs)+1;
}
inline void flat(int x) {if(ls) flat(ls); p[++cnt]=x; if(rs) flat(rs);}
int buf[N];
inline int build(int l,int r,int dim) {
R md=l+r>>1,x; D=dim;
nth_element(p+l,p+md,p+r+1,cmp),x=p[md];
mx(x,0)=mn(x,0)=p(x,0),mx(x,1)=mn(x,1)=p(x,1);
ls=l<md?build(l,md-1,dim^1):0;
rs=r>md?build(md+1,r,dim^1):0; upd(x); return x;
}
inline void ins(int& rt,int c) {
if(!rt) return rt=c,void(); R top=0;
for(R dim=0,x=rt;;dim^=1) {
buf[++top]=x;
cmx(mx(x,0),mx(c,0)),cmx(mx(x,1),mx(c,1)),
cmn(mn(x,0),mn(c,0)),cmn(mn(x,1),mn(c,1));
++sz(x);
if(p(c,dim)<p(x,dim)) {
if(!ls) {ls=c; break;}
else x=ls;
} else {
if(!rs) {rs=c; break;}
else x=rs;
}
} buf[++top]=c;
while(sz(t[c].lc)<A*sz(c)&&sz(t[c].rc)<A*sz(c)) c=buf[--top];
if(!c) return;
if(c==rt) return cnt=0,flat(rt),rt=build(1,cnt,0),cnt=0,void();
R fa=buf[--top],crt;
flat(c),crt=build(1,cnt,top&1),cnt=0;
if(t[fa].lc==c) t[fa].lc=crt;
else t[fa].rc=crt;
}
inline void query(int x) {
if(!x||mx(x,0)<s.mn[0]||mx(x,1)<s.mn[1]||mn(x,0)>s.mx[0]||mn(x,1)>s.mx[1]||ans>=k) return ;
if(s.mn[0]<=mn(x,0)&&mx(x,0)<=s.mx[0]&&s.mn[1]<=mn(x,1)&&mx(x,1)<=s.mx[1]) return ans+=sz(x),void();
if(s.mn[0]<=p(x,0)&&p(x,0)<=s.mx[0]&&s.mn[1]<=p(x,1)&&p(x,1)<=s.mx[1]) ++ans;
query(ls),query(rs);
}
#undef ls
#undef rs
int rt[N*B],ls[N*B],rs[N*B];
inline void change() {
R tr=1,l=1,r=Inf,md,flg=1;
while(20040109) {
if(flg) { ++ct;
mx(ct,0)=mn(ct,0)=p(ct,0)=s.d[0];
mx(ct,1)=mn(ct,1)=p(ct,1)=s.d[1];
sz(ct)=1;
ins(rt[tr],ct);
} if(l==r) return ;
md=l+r>>1;
if(k<=md) {
if(!ls[tr]) ls[tr]=++tot;
tr=ls[tr],r=md,flg=0;
}
if(k>md) {
if(!rs[tr]) rs[tr]=++tot;
tr=rs[tr],l=md+1,flg=1;
}
}
}
inline void query() {
ans=0,query(rt[1]);
if(ans<k) return puts("NAIVE!ORZzyz."),ans=0,void();
R tr=1,l=1,r=Inf,md;
while(l<r) { md=l+r>>1;
ans=0,query(rt[rs[tr]]);
if(k<=ans) tr=rs[tr],l=md+1;
else k-=ans,tr=ls[tr],r=md;
} printf("%d\n",ans=l);
}
inline void main() {
g(),n=g(); for(R i=1,op,x,y;i<=n;++i) {
op=g(),x=g()^ans,y=g()^ans;
if(op&1) s.d[0]=x,s.d[1]=y,k=g()^ans,change();
else s.mn[0]=x,s.mn[1]=y,s.mx[0]=g()^ans,s.mx[1]=g()^ans,k=g()^ans,query();
}
}
} signed main() {Luitaryi::main(); return 0;}
2019.12.21