整体二分是一个离线的做法 目前可以解决求区间第k大问题
当然划分树主席树都可以的样子.. 为什么我老学一些解决同种问题的算法..
主要思想大概是这样的:
如果要求[l,r]的区间第K大 而这个区间内如果有多于K个数字 那么多出来的数字其实是不会影响到什么的
所以我们整体二分一下答案 即 把二分值对于每一个操作 都尝试一发 于是会发现 如果当前我们二分答案是x 那么大于x的数字是没有意义的 算出来小于x的数字有多少 然后做一个类似于划分树思想的操作 分出lq rq两个队列 把<=x的相关操作强制堆到lq里面 >x的堆到rq里面 被扔到rq里面的query询问会出现 q[i].k -= (小于当前二分值x的个数)
于是 每一次二分 都会分出lq rq 而rq里面的操作 是不会影响到lq的 因为rq操作的数字 要么在询问之后 要么已经>k了
当l==r的时候 对当前消息队列筛选出所有query 记录答案 = l
每次处理出lq rq之后 让q = lq 和 rq 然后去处理这两个部分 因为把<=x的强制扔到lq里面了 也就保证了lq里面如果有询问 ans一定在l mid 这个区间里面
这样一直down下去 不需要up
在这个求区间k大的做法里面 记录区间内数字的做法是:
由于我们已经确定这个伪ans(二分值)了 我们就只算<=x的 数字的个数
我们假想这个a数列一开始是空的 每一个赋值都是对一个位置插入一个数字
并且我们保证了处理的当前操作队列[ql , qr] 里面的数字操作都是 [l , r]里面的 于是 小于伪ans的增删操作 对其做一下树状数组的add
如何查询当前的询问 应该被归类到哪个队列:
看[q[i].l , q[i].r] 这个区间内 有 多少个值 由于增删的时候只对<=x做操作 所以求出来的sum是这个区间内<=x的值 就可以决定把这个操作扔到哪个队列
由于每次都是对当前[ql,qr]操作队列进行 所以开始面对的总是一个空的树状数组c[] 所以最后需要对add(x,val)的操作进行一个add(x,-val)的操作 可以省去memset的时间
如果要做更改的操作 就可以拆分成增加与减少两个操作
支持在二维的区间上查询第k大 需要使用二维树状数组
在拆分成两个队列后 两个队列里的操作互相不影响 但是 每个队列里面 操作的相对前后是不变的 两个队列的相对前后可能因为分到不同队列发生改变 改变的都是无关的
二维区间查询第k大 Tsinsen A1333
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
using namespace std;
#define L long long
#define pb push_back
const int N = 505 * 505 + 60050 ;
struct node {
int x1 , y1 , x2 , y2 , z , id , tp ;
}q[N] , lq[N] , rq[N] ;
int n , m ;
int c[505][505] ;
int ans[60050] ;
int lowbit(int x) {return (x&(-x)) ; }
void add(int x,int y,int val) {
for(int i=x;i<=n;i+=lowbit(i)){
for(int j=y;j<=n;j+=lowbit(j)) {
c[i][j]+=val;
}
}
}
int sum(int x,int y) {
int val = 0 ;
for(int i=x;i>0;i-=lowbit(i)){
for(int j=y;j>0;j-=lowbit(j)){
val+=c[i][j];
}
}
return val;
}
int sum(int x1,int y1,int x2,int y2) {
return sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
}
void solve(int ql , int qr , int l , int r) {
if(ql > qr || l > r) return ;
if(l == r) {
for(int i = ql ; i <= qr ; i ++ ) {
if(q[i].tp == 2) {
ans[q[i].id] = l ;
}
}
return ;
}
int lcnt = 0 , rcnt = 0 ;
int mid = (l + r) / 2 ;
for(int i = ql ; i <= qr ; i ++ ){
if(q[i].tp == 1) {
if(q[i].z <= mid) {
lq[++lcnt] = q[i] ;
add(q[i].x1,q[i].y1,q[i].id) ;
}
else {
rq[++rcnt] = q[i] ;
}
}
else {
int small = sum(q[i].x1,q[i].y1,q[i].x2,q[i].y2) ;
if(q[i].z <= small) {
lq[++lcnt] = q[i] ;
}
else {
q[i].z -= small ;
rq[++rcnt] = q[i] ;
}
}
}
for(int i = 1 ; i <= lcnt ; i ++) {
if(lq[i].tp == 1) {
add(lq[i].x1,lq[i].y1,-lq[i].id) ;
}
}
for(int i = 1 ; i <= lcnt ; i ++ ) q[i + ql - 1] = lq[i] ;
for(int i = 1 ; i <= rcnt ; i ++ ) q[i + ql + lcnt - 1] = rq[i] ;
solve(ql,ql+lcnt-1,l,mid);
solve(ql+lcnt,qr,mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
int cnt = 0 ;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int x;
scanf("%d",&x);
cnt ++ ;
q[cnt].x1=i,q[cnt].y1=j,q[cnt].z=x,q[cnt].tp=1,q[cnt].id=1;
}
for(int i=1;i<=m;i++){
int x1,y1,x2,y2,k;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
cnt ++ ;
q[cnt].x1=x1,q[cnt].x2=x2,q[cnt].y1=y1,q[cnt].y2=y2,q[cnt].z=k,q[cnt].id=i,q[cnt].tp=2;
}
solve(1,cnt,0,1000000000);
for(int i=1;i<=m;i++)
printf("%d
",ans[i]);
}
-------------
又进行了一些学习 发现不止可以解决求k大
可以解决一些满足“二分性”和“无后效性”的问题
是一个把所有询问(和操作)一起读入 最后一起二分的做法
比如poi2011meteors 就是一个整体二分的例子
其实操作队列中只有询问某个国家 l r 代表当前答案的可能范围 先做出[l,mid]的流星雨的结果 然后check操作队列中的每一个国家 足够的lq以寻求最小
不足够的扔到rq 并且减去[l,mid]得到的流星 于是 关注点就只在它能在[mid+1,r]中得到多少流星了
(五角星) 因为过去的流星 这个国家已经收集到了 当我们考虑这个国家的ans在[mid+1,r]的哪里时 过去的事情无需考虑 直接减去那段时光造成的所有影响就可以了