POJ 2104：K-th Number 整体二分

感觉整体二分是个很有趣的东西。

在别人的博客上看到一句话

对于二分能够解决的询问，如果有多个，那么如果支持离线处理的话，那么就可以使用整体二分了

树套树写了一天还是WA着，调得焦头烂额，所以决定学cdq分治的写法，虽然不知道整体二分和cdq有什么不可不说的关系，就先写了这道主席树模板题（orz LLZ大佬）。

然后历史总是惊人的相似，和上午写cdq分治一样，又在同一个地方栽了跟头

两个cdq模板都是cmp写错，两个整体二分都是把que[i]写成了i QAQ

然后这个代码在洛谷上会T掉，在POJ可以A，就很难受了（vjudge上waiting了35分钟。。。）

//Twenty

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

#include<vector>

using namespace std;

const int maxn=++;

const int INF=1e9+;

int n,m,tot,sum[maxn],ans[maxn];

struct node{

    int op,id,l,r,v;

    node(){};

    node(int op,int id,int l,int r,int v):op(op),id(id),l(l),r(r),v(v){}

}p[maxn],tp[maxn];

void input() {

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) {

        int x;

        scanf("%d",&x);

        p[i]=node(,i,i,i,x);

    }

    for(int i=;i<=m;i++) {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        p[i+n]=node(,i,x,y,z);

    }

}

void add(int x,int y) {

    for(;x<=n+m;x+=(x&(-x)))

        sum[x]+=y;

}

int qry(int x) {

    int res=;

    for(;x;x-=(x&(-x)))

        res+=sum[x];

    return res;

}

#define mid ((l+r)>>1)

int lq[maxn],rq[maxn];

void solve(int ql,int qr,int l,int r) {

    if(l==&&r==) {

       int debug=;

    }

    //int mid=((l+r)>>1);

    if(r<l||qr<ql) return;

    if(l==r) {

        for(int i=ql;i<=qr;i++)

            if(p[i].op==)

                ans[p[i].id]=l;

        return;

    }

    int lcnt=,rcnt=;

    for(int i=ql;i<=qr;i++) {

        if(p[i].op) {   //insert

            if(p[i].v<=mid) {

                add(p[i].id,);

                lq[++lcnt]=i;

            }

            else rq[++rcnt]=i;

        }

        else {  //query

            int now=qry(p[i].r)-qry(p[i].l-);

            if(now>=p[i].v) lq[++lcnt]=i;

            else p[i].v-=now,rq[++rcnt]=i;

        }

    }

    for(int i=;i<=lcnt;i++)

        if(p[lq[i]].op&&p[lq[i]].v<=mid) add(p[lq[i]].id,-);

    for(int i=;i<lcnt;i++) tp[ql+i]=p[lq[i+]];

    for(int i=;i<rcnt;i++) tp[ql+lcnt+i]=p[rq[i+]];

    for(int i=ql;i<=qr;i++) p[i]=tp[i];

    solve(ql,ql+lcnt-,l,mid);

    solve(ql+lcnt,qr,mid+,r);

}

void print() {

    for(int i=;i<=m;i++)

        printf("%d\n",ans[i]);

}

int main()

{

    input();

    solve(,m+n,-INF,INF);

    print();

    return ;

}

K-th number

巴特西

POJ 2104：K-th Number 整体二分

最新文章

热门文章