题目大意：有m个操作，操作有两种类型：1是在x,y位置放一个值v,2是询问x1,y1 到x2,y2之间第k大的值是几。
解法：第K大可以用整体二分，问题是这里是矩形区间内的第k大，而不是线性序列上的第k大。
还是一样的，回忆整体二分：二分答案区间，将操作分开，递归处理左答案区间和右答案区间的操作。插入操作还是一样的，值小于等于mid 放左边，值大于mid 放右边，对于询问操作，我们要求出这个询问操作的矩形区间内值大于mid的个数，以此来判断这个询问操作该放左边还是右边，对于线性序列，只需要用树状数组搞一下就行了。
这里仔细分析一下：其实就是求当前这些操作序列中：时间在该操作前，值 > mid,且坐标在这个询问范围内的插入操作有多少个。把值 > mid的操作筛出来，可以发现这就是一个三维偏序问题，因此整体二分中操作序列的划分判断需要用到cdq分治，求出个数之后再将操作划分然后分别解决左边和右边。
然后注意一下可能不存在第k大，剩下的就和整体二分一样了
时间复杂度：因为每一个子问题要套cdq分治，时间复杂度为n * (log n) ^ 3，空间复杂度为o (n)
#include<iostream> using namespace std; const int maxn = 3e6 + 10; #include<stdio.h> #define lowbit(i) (i & (-i)) const int inf = 1e9; int n,m; struct node{ int op,x,y,val,id,type; bool operator < (const node & rhs) const { if(x == rhs.x) { if(y == rhs.y) return id < rhs.id; else return y < rhs.y; } else return x < rhs.x; } }q[maxn],lq[maxn],rq[maxn],tt[maxn],tmp[maxn]; int sum[maxn],k[maxn],ans[maxn],C[maxn],tim; void modify(int p,int v) { for(; p <= n; p += lowbit(p)) sum[p] += v; } int ask(int p) { int res = 0; for(; p > 0; p -= lowbit(p)) res += sum[p]; return res; } void cdq(int l,int r,int mx) { if(l == r) return; int mid = l + r >> 1; cdq(l,mid,mx);cdq(mid + 1,r,mx); int top = 0; for(int i = l,j = mid + 1; i <= mid || j <= r;) { if(i <= mid && (j > r || tt[i] < tt[j])) { if(tt[i].op == 0 && tt[i].val > mx) modify(tt[i].y,1); tmp[++top] = tt[i++]; } else { if(tt[j].op > 0) { if(tt[j].type == 2) k[tt[j].op] += ask(tt[j].y); if(tt[j].type == 3) k[tt[j].op] -= ask(tt[j].y); } tmp[++top] = tt[j++]; } } for(int i = l; i <= mid; i++) { if(tt[i].op == 0 && tt[i].val > mx) modify(tt[i].y,-1); } for(int i = 1; i <= top; i++) tt[i + l - 1] = tmp[i]; } void init(int l,int r) { for(; l <= r; l++) { k[q[l].op] = 0; tt[l] = q[l]; } } void solve(int vl,int vr,int st,int ed) { if(st > ed) return; if(vl == vr) { init(st,ed);cdq(st,ed,vl - 1); for(int i = st; i <= ed; i++) { if(q[i].op > 0 && q[i].val <= k[q[i].op]) //（注意）判断第K大存在的条件 ans[q[i].op] = vl; else ans[q[i].op] = -1; } return ; } int mid = vl + vr >> 1,lt = 0,rt = 0; init(st,ed); cdq(st,ed,mid); for(int i = st; i <= ed; i++) { if(q[i].op == 0) { if(q[i].val <= mid) lq[++lt] = q[i]; else rq[++rt] = q[i]; } else { if(k[q[i].op] >= q[i].val) rq[++rt] = q[i]; else { q[i].val -= k[q[i].op]; lq[++lt] = q[i]; } } } for(int i = 1; i <= lt; i++) { q[st + i - 1] = lq[i]; } for(int i = 1; i <= rt; i++) { q[st + lt + i - 1] = rq[i]; } solve(vl,mid,st,st + lt - 1); solve(mid + 1,vr,st + lt,ed); } int main() { scanf("%d%d",&n,&m); int x,y,a,b,op,v,tot = 0,cnt = 0; for(int i = 1; i <= m; i++) { scanf("%d%d%d",&op,&x,&y); if(op == 1) { scanf("%d",&v); q[++tot] = (node){0,x,y,v,i,0}; } if(op == 2) { scanf("%d%d%d",&a,&b,&v); cnt++; q[++tot] = (node){cnt,x - 1,y - 1,v,i,2}; q[++tot] = (node){cnt,x - 1,b,v,i,3}; q[++tot] = (node){cnt,a,b,v,i,2}; q[++tot] = (node){cnt,a,y - 1,v,i,3}; } } solve(1,inf,1,tot); for(int i = 1; i <= cnt; i++) { if(ans[i] != -1) printf("%d\n",ans[i]); else printf("NAIVE!ORZzyz.\n"); } return 0; }