bzoj 4605: 崂山白花蛇草水

Description

神犇Aleph在SDOI Round2前立了一个flag：如果进了省队，就现场直播喝崂山白花蛇草水。凭借着神犇Aleph的实 力，他轻松地进了山东省省队，现在便是他履行诺言的时候了。蒟蒻Bob特地为他准备了999,999,999,999,999,999 瓶崂山白花蛇草水，想要灌神犇Aleph。神犇Aleph求（跪着的）蒟蒻Bob不要灌他，由于神犇Aleph是神犇，蒟蒻Bo b最终答应了他的请求，但蒟蒻Bob决定将计就计，也让神犇Aleph回答一些问题。具体说来，蒟蒻Bob会在一个宽敞 的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇Aleph在矩形区域(x1, y1), ( x2, y2)(x1≤x2且y1≤y2，包括边界)中，崂山白花蛇草水瓶数第k多的是多少。为了避免麻烦，蒟蒻Bob不会在同 一个位置放置两次或两次以上的崂山白花蛇草水，但蒟蒻Bob想为难一下神犇Aleph，希望他能在每次询问时立刻回 答出答案。神犇Aleph不屑于做这种问题，所以把这个问题交给了你。

Input

输入的第一行为两个正整数N, Q，表示横纵坐标的范围和蒟蒻Bob的操作次数（包括放置次数和询问次数）。 接下来Q行，每行代表蒟蒻Bob的一个操作，操作格式如下： 首先第一个数字type，表示操作种类。type=1表示放置，type=2表示询问。 若type=1，接下来会有三个正整数x, y, v，表示在坐标整点(x, y)放置v瓶崂山白花蛇草水。(1≤x, y≤N, 1≤v≤10^9) 若type=2，接下来会有五个正整数x1, y1, x2, y2, k，表示询问矩形区域(x1, y1), (x2, y2)中，崂山白花蛇草水瓶数第k多的是多少。 (1≤x1≤x2≤N，1≤y1≤y2≤N，1≤k≤Q) 为了体现程序的在线性，你需要将每次读入的数据（除了type值）都异或lastans，其中lastans表示上次询问的答 案。如果上次询问的答案为"NAIVE!ORZzyz."（见样例输出），则将lastans置为0。初始时的lastans为0。 初始时平面上不存在崂山白花蛇草水。 本题共有12组测试数据。对于所有的数据，N≤500,000。 Q的范围见下表： 测试点1-2 Q=1,000 测试点3-7 Q=50,000 测试点8-12 Q=100,000

Output

对于每个询问(type=2的操作)，回答崂山白花蛇草水瓶数第k多的是多少。若不存在第k多的瓶数， 请输出"NAIVE!ORZzyz."（输出不含双引号）。

Sample Input

10 7

1 1 1 1

1 2 2 3

1 4 1 2

1 3 4 4

2 1 1 4 1 3

2 2 2 3 5 4

2 2 1 4 4 2

Sample Output

NAIVE!ORZzyz.

NAIVE!ORZzyz.

3这名字……线段树套k-d树，重构的话就把点全部拿出来建树再放回去。

#include<cstdio>#include<algorithm>#define MN 1400010#define M 2000using namespace std;int n,m,X,ro[MN],L[MN],R[MN],x,y,num=0,nm=0,x1,x2,y1,y2,root=0,xx,o,MMH=0,mmh[MN],st[MN],l,r;struct tr{int x,y;friend bool operator<(tr a,tr b){if (X) return a.x<b.x;else return a.y<b.y;}}a[MN],A[MN];struct tree{int xa,xi,ya,yi,l,r,si;}t[MN],T[MN];char cs;inline int read(){cs=getchar();xx=0;while(cs<'0'||cs>'9') cs=getchar();while(cs>='0'&&cs<='9') xx=xx*10+cs-48,cs=getchar();return xx;}inline void in(int &p,bool b){if (!p){p=num;t[p].l=t[p].r=0;t[p].xa=t[p].xi=a[num].x;t[p].ya=t[p].yi=a[num].y;t[p].si=1;return;}X=b;t[p].si++;if (a[num]<a[p]) in(t[p].l,b^1);else in(t[p].r,b^1);t[p].xa=max(t[p].xa,a[num].x);t[p].xi=min(t[p].xi,a[num].x);t[p].ya=max(t[p].ya,a[num].y);t[p].yi=min(t[p].yi,a[num].y);}inline int build(int l,int r,int now){X=now;int mid=(l+r)>>1;nth_element(A+l,A+mid,A+r+1);T[mid].si=r-l+1;T[mid].xa=T[mid].xi=A[mid].x;T[mid].ya=T[mid].yi=A[mid].y;if (l<mid) T[mid].l=build(l,mid-1,now^1),T[mid].xa=max(T[T[mid].l].xa,T[mid].xa),T[mid].xi=min(T[T[mid].l].xi,T[mid].xi),T[mid].ya=max(T[T[mid].l].ya,T[mid].ya),T[mid].yi=min(T[T[mid].l].yi,T[mid].yi);else T[mid].l=0;if (mid<r) T[mid].r=build(mid+1,r,now^1),T[mid].xa=max(T[T[mid].r].xa,T[mid].xa),T[mid].xi=min(T[T[mid].r].xi,T[mid].xi),T[mid].ya=max(T[T[mid].r].ya,T[mid].ya),T[mid].yi=min(T[T[mid].r].yi,T[mid].yi);else T[mid].r=0;return mid;}inline int wout(int p){st[l=r=1]=p;while(l<=r){A[l]=a[st[l]];if (t[st[l]].l) st[++r]=t[st[l]].l;if (t[st[l]].r) st[++r]=t[st[l]].r;l++;}l=build(1,r,0);for (register int i=1;i<=r;i++) t[st[i]]=T[i],a[st[i]]=A[i],t[st[i]].l=st[t[st[i]].l],t[st[i]].r=st[t[st[i]].r];return st[l];return p;}inline void insert(int &p,int l,int r,int v,bool b){if (!p) p=++nm,mmh[p]=M;if (b){a[++num].x=x;a[num].y=y;in(ro[p],0);if (t[ro[p]].si==mmh[p]) mmh[p]+=M,ro[p]=wout(ro[p]);}if (l==r) return;int mid=l+r>>1;if (v<=mid) insert(L[p],l,mid,v,0);else insert(R[p],mid+1,r,v,1);}inline int ask(int p){if (t[p].xa<=x2&&t[p].xi>=x1&&t[p].ya<=y2&&t[p].yi>=y1) return 1;if (t[p].xi>x2||t[p].xa<x1||t[p].yi>y2||t[p].ya<y1) return 0;return 2;}inline bool inl(int p){if (a[p].x>=x1&&a[p].x<=x2&&a[p].y>=y1&&a[p].y<=y2) return 1;return 0;}inline int QUE(int p){int mmh=ask(p);if (!mmh) return 0;if (mmh==1) return t[p].si;else{if (inl(p)) mmh=1;else mmh=0;if (t[p].l) mmh+=QUE(t[p].l);if (t[p].r) mmh+=QUE(t[p].r);}return mmh;}inline int que(int p,int l,int r,int k){if (l==r) return l;int u=0;if (R[p]) u=QUE(ro[R[p]]);int mid=l+r>>1;if (u<k) return que(L[p],l,mid,k-u);else return que(R[p],mid+1,r,k);}int main(){register int i,k;n=read();m=read();for (i=1;i<=m;i++){o=read();if (o==1) x=MMH^read(),y=MMH^read(),insert(root,1,1e9,MMH^read(),1);else{x1=MMH^read();y1=MMH^read();x2=MMH^read();y2=MMH^read();k=MMH^read();if (QUE(ro[root])<k) printf("NAIVE!ORZzyz.\n",MMH=0);elseprintf("%d\n",MMH=que(root,1,1e9,k));}}}

126604 kb 24240 ms C++/Edit 3738 B

如果觉得《bzoj 4605: 崂山白花蛇草水》对你有帮助，请点赞、收藏，并留下你的观点哦！