https://www.luogu.org/problemnew/show/P4848

我的数据结构大概已经废了。

外层权值线段树内层kdtree，外层线段树上二分答案。

码数据结构一时爽，码完debug火葬场。

要rebuild时少写了个else什么的

插入不upd下去的时候没把值更新完比如sz什么的

比较Int的时候把外层数组套多套少什么的

拿什么拯救你，我的数据结构

吸氧才能过的代码，据说没人能不吸氧过。

 

//Achen#include
     
      #define For(i,a,b) for(int i=(a);i<=(b);i++)#define Rep(i,a,b) for(int i=(a);i>=(b);i--)#define Formylove return 0const int N=100007,UP=1e9;typedef long long LL; typedef double db;using namespace std;int n,q,lastans;int xl,yl,xr,yr,Qrs;template
      
        void read(T &x) {    char ch=getchar(); x=0; T f=1;    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();    if(ch=='-') f=-1,ch=getchar();    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}#define lc ch[x][0]#define rc ch[x][1]#define mid ((l+r)>>1)struct pt {	int d[2],v;}p[N*33];int rt[N*33],cnt,dt[N*33][2][2],ch[N*33][2],sz[N*33],f[N*33],D;void upd(int x) {	dt[x][0][0]=dt[x][0][1]=p[x].d[0];	dt[x][1][0]=dt[x][1][1]=p[x].d[1];	if(lc) {		dt[x][0][0]=min(dt[x][0][0],dt[lc][0][0]);		dt[x][0][1]=max(dt[x][0][1],dt[lc][0][1]);		dt[x][1][0]=min(dt[x][1][0],dt[lc][1][0]);		dt[x][1][1]=max(dt[x][1][1],dt[lc][1][1]);	}	if(rc) {		dt[x][0][0]=min(dt[x][0][0],dt[rc][0][0]);		dt[x][0][1]=max(dt[x][0][1],dt[rc][0][1]);		dt[x][1][0]=min(dt[x][1][0],dt[rc][1][0]);		dt[x][1][1]=max(dt[x][1][1],dt[rc][1][1]);	}	sz[x]=sz[lc]+sz[rc]+1;}	int sta[N],top;void tra(int x) {	if(lc) tra(lc);	sta[++top]=x;	if(rc) tra(rc);}	bool cmp(const int &A,const int &B) { return p[A].d[D]
       
        r) return 0;	nth_element(sta+l,sta+mid,sta+r+1,cmp);	int x=sta[mid];	lc=build(l,mid-1,dd^1); if(lc) f[lc]=x; 	rc=build(mid+1,r,dd^1); if(rc) f[rc]=x;	upd(x); return x;}	int rebuild(int x,int F,int dd) {	top=0; tra(x);	int rs=build(1,top,dd); 	f[rs]=F; return rs;}	int bal(int x) { return sz[x]*0.85>=max(sz[lc],sz[rc]); }	void insert(int &RT,pt A) {	int x=RT;	for(int fa=0,l=0,dd=0;;dd^=1) {		if(!x) {			x=++cnt; p[x]=A; 			upd(x);			f[x]=fa;			if(fa) ch[fa][l]=x;			else RT=x;			break ;		}		dt[x][0][0]=min(dt[x][0][0],A.d[0]);		dt[x][0][1]=max(dt[x][0][1],A.d[0]);		dt[x][1][0]=min(dt[x][1][0],A.d[1]);		dt[x][1][1]=max(dt[x][1][1],A.d[1]); sz[x]++;		if(A.d[dd]
        
         xr||dt[x][0][1]
         
          yr||dt[x][1][1]
          
           =xl&&dt[x][0][1]<=xr&&dt[x][1][0]>=yl&&dt[x][1][1]<=yr) { Qrs+=sz[x]; return ; } if(p[x].d[0]>=xl&&p[x].d[0]<=xr&&p[x].d[1]>=yl&&p[x].d[1]<=yr) Qrs++; if(lc) qry(lc); if(rc) qry(rc);}int sgrt,tot,lson[N*33],rson[N*33];void upd(int &x,int l,int r,int pos,pt A) { if(!x) x=++tot; insert(rt[x],A); if(l==r) return ; if(pos<=mid) upd(lson[x],l,mid,pos,A); else upd(rson[x],mid+1,r,pos,A);}int qry(int x,int l,int r,int k) { Qrs=0; if(l==r) { qry(rt[x]); if(Qrs>=k) return l; else return 0; } qry(rt[rson[x]]); if(Qrs>=k) return qry(rson[x],mid+1,r,k); else return qry(lson[x],l,mid,k-Qrs);}int main() { //freopen("4605.in","r",stdin); //freopen("4605.out","w",stdout); read(n); read(q); For(i,1,q) { int o; read(o); if(o==1) { int x,y,v; read(x); read(y); read(v); x^=lastans; y^=lastans; v^=lastans; upd(sgrt,1,UP,v,(pt){x,y,v}); } else { int k; read(xl); read(yl); read(xr); read(yr); xl^=lastans; yl^=lastans; xr^=lastans; yr^=lastans; read(k); k^=lastans; lastans=qry(sgrt,1,UP,k); if(!lastans) puts("NAIVE!ORZzyz."); else printf("%d\n",lastans); } } Formylove;}
          
         
        
       
      
     

 

 

//Achen#include
      
       #define For(i,a,b) for(int i=(a);i<=(b);i++)#define Rep(i,a,b) for(int i=(a);i>=(b);i--)#define Formylove return 0const int N=5005;typedef long long LL;typedef double db;using namespace std;int a[N][N];template
       
         void read(T &x) {    char ch=getchar(); T f=1; x=0;    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();    if(ch=='-') f=-1,ch=getchar();    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int main() {    //freopen("1.in","w",stdout);    srand(time(0));    int n=10,m=rand()%100+1;    printf("%d %d\n",n,m);    For(i,1,m) {        int o;        o=rand()%2+1;        //if(i<=m/2) o=1; else o=2;        if(i<=5) {            int x=rand()%n+1,y=rand()%n+1,v=rand()%10+1;            printf("1 %d %d %d\n",x,y,v);        }            else {            int xl,yl,xr,yr,k;            xl=rand()%n+1,xr=rand()%n+1;            yl=rand()%n+1,yr=rand()%n+1;            if(xl>xr) swap(xl,xr);            if(yl>yr) swap(yl,yr);            k=rand()%n+1;            printf("2 %d %d %d %d %d\n",xl,yl,xr,yr,k);        }    }    Formylove;}