整体二分learning

整体二分是一个离线的做法目前可以解决求区间第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\n",ans[i]);

}

-------------

又进行了一些学习发现不止可以解决求k大

可以解决一些满足“二分性”和“无后效性”的问题

是一个把所有询问(和操作)一起读入最后一起二分的做法

比如poi2011meteors 就是一个整体二分的例子

其实操作队列中只有询问某个国家 l r 代表当前答案的可能范围先做出[l,mid]的流星雨的结果然后check操作队列中的每一个国家足够的lq以寻求最小

不足够的扔到rq 并且减去[l,mid]得到的流星于是关注点就只在它能在[mid+1,r]中得到多少流星了

(五角星) 因为过去的流星这个国家已经收集到了当我们考虑这个国家的ans在[mid+1,r]的哪里时过去的事情无需考虑直接减去那段时光造成的所有影响就可以了

巴特西

整体二分learning

最新文章

热门文章