基于值域的整体分治算法（整体二分）

ID: 361

客观题

尝试: 2

已通过: 2

难度: 10

上传者:

boya

例1：静态区间第k小/P3834可持久化线段树

参考代码：

//整体二分
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m;
struct node{
    int x,y,z,op;
}que[N*2],lq[N*2],rq[N*2];
int cnt,tr[N],ans[N];
void add(int x,int d)
{
    for(int i=x;i<=n;i+=i&(-i))tr[i]+=d;
}
int query(int x)
{
    int ret=0;
    for(int i=x;i;i-=i&(-i))ret+=tr[i];
    return ret;
}
void solve(int lval,int rval,int st,int ed)
{
    if(st>ed)return;   //操作序列为空
    if(lval==rval)
    {
        for(int i=st;i<=ed;i++)
            if(que[i].op>0)ans[que[i].op]=lval;
        return;
    }
    int mid=lval+rval>>1;
    int lt=0,rt=0;
    for(int i=st;i<=ed;i++)
        if(que[i].op==0)   //赋值操作
        {
            if(que[i].y<=mid)add(que[i].x,1),lq[++lt]=que[i];
            else rq[++rt]=que[i];
        }
        else  //询问
        {
            int num=query(que[i].y)-query(que[i].x-1);
            if(num>=que[i].z)lq[++lt]=que[i];
            else que[i].z-=num,rq[++rt]=que[i];
        }
    for(int i=ed;i>=st;i--)//还原
        if(que[i].op==0 && que[i].y<=mid)add(que[i].x,-1);
    
    for(int i=1;i<=lt;i++)que[st+i-1]=lq[i];
    for(int i=1;i<=rt;i++)que[st+lt+i-1]=rq[i];
    
    solve(lval,mid,st,st+lt-1);
    solve(mid+1,rval,st+lt,ed);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int val;
        cin>>val;
        que[++cnt].op=0;   //表示赋值 0表示增加一个值
        que[cnt].x=i;        //位置
        que[cnt].y=val;      //值
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k; cin>>l>>r>>k;
        que[++cnt].x=l;  que[cnt].y=r; //[x,y]区间
        que[cnt].z=k;                  //第k大
        que[cnt].op=i;                 //对应询问编号
    }
    solve(0,1e9,1,cnt);   //值域二分 
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";  
    
    return 0;
}

例2. 动态区间第k小[P2617 Dynamic Rankings]

参考代码：

//整体二分
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m,a[N];
struct node{
    int x,y,z,op;
}que[N*3],lq[N*3],rq[N*3];
int cnt,tr[N],ans[N];
bool flag[N];
void add(int x,int d)
{
    for(int i=x;i<=n;i+=i&(-i))tr[i]+=d;
}
int query(int x)
{
    int ret=0;
    for(int i=x;i;i-=i&(-i))ret+=tr[i];
    return ret;
}
void solve(int lval,int rval,int st,int ed)
{
    if(st>ed)return;   //操作序列为空
    if(lval==rval)
    {
        for(int i=st;i<=ed;i++)
            if(que[i].op>0)ans[que[i].op]=lval;
        return;
    }
    int mid=lval+rval>>1;
    int lt=0,rt=0;
    for(int i=st;i<=ed;i++)
        if(que[i].op==0)   //赋值操作
        {
            if(que[i].y<=mid)add(que[i].x,1),lq[++lt]=que[i];
            else rq[++rt]=que[i];
        }
        else if(que[i].op==-1)
        {
            if(que[i].y<=mid)add(que[i].x,-1),lq[++lt]=que[i];
            else rq[++rt]=que[i];
        }
        else  //询问
        {
            int num=query(que[i].y)-query(que[i].x-1);
            if(num>=que[i].z)lq[++lt]=que[i];
            else que[i].z-=num,rq[++rt]=que[i];
        }
    for(int i=ed;i>=st;i--)//还原
        if(que[i].op==0 && que[i].y<=mid)add(que[i].x,-1);
        else if(que[i].op==-1 && que[i].y<=mid)add(que[i].x,1);
    
    for(int i=1;i<=lt;i++)que[st+i-1]=lq[i];
    for(int i=1;i<=rt;i++)que[st+lt+i-1]=rq[i];
    
    solve(lval,mid,st,st+lt-1);
    solve(mid+1,rval,st+lt,ed);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        que[++cnt].op=0;   //表示赋值 0表示增加一个值
        que[cnt].x=i;        //位置
        que[cnt].y=a[i];      //值
    }
    for(int i=1;i<=m;i++)
    {
        char op;
        cin>>op;
        if(op=='Q')
        {
            int l,r,k; cin>>l>>r>>k;
            que[++cnt].x=l;  que[cnt].y=r; //[x,y]区间
            que[cnt].z=k;                  //第k大
            que[cnt].op=i;                 //对应询问编号
            flag[i]=1;
        }else
        {
            int x,y;
            cin>>x>>y;
            //去掉一个值A[x]
            que[++cnt].op=-1;
            que[cnt].x=x;
            que[cnt].y=a[x];
            //增加一个值A[x]+=y
            que[++cnt].op=0;
            que[cnt].x=x;
            que[cnt].y=y;
            a[x]=y;
                        
        }        
    }
    solve(0,1e9,1,cnt);   //值域二分 
    for(int i=1;i<=m;i++)
        if(flag[i])
            cout<<ans[i]<<"\n";  
    return 0;
}

例3. 静态矩阵第k小 P1527 [国家集训队] 矩阵乘法

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505,Q=6e4+10;
int n,q,ans[Q],cnt,t[N][N];
struct Node{
    int x,y,val;
    bool operator<(Node a)const{
        return val<a.val;
    }
}a[N*N];
struct Query{
    int x1,y1,x2,y2,k,id;
}que[Q],lq[Q],rq[Q];

void add(int x,int y,int d)
{
    for(int i=x;i<=n;i+=i&(-i))
        for(int j=y;j<=n;j+=j&(-j))
            t[i][j]+=d;
}

int query(int x,int y)
{
    int ret=0;
    for(int i=x;i;i-=i&(-i))
        for(int j=y;j;j-=j&(-j))ret+=t[i][j];
    return ret;
}
int cal(int x1,int y1,int x2,int y2)
{
    return query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1);
}


void solve(int l,int r,int st,int ed)
{
    if(st>ed)return;
    if(l==r)
    {
        for(int i=st;i<=ed;i++)ans[que[i].id]=a[l].val;
        return;
    }
    int mid=l+r>>1; 
    for(int i=l;i<=mid;i++)add(a[i].x,a[i].y,1);   //小于 a[mid].val ,树状数组上增加1
    
    int lt=0,rt=0;
    for(int i=st;i<=ed;i++)
    {
        int num=cal(que[i].x1,que[i].y1,que[i].x2,que[i].y2);
        
        if(num>=que[i].k)lq[++lt]=que[i];
        else que[i].k-=num,rq[++rt]=que[i];
    }
    //还原
    for(int i=l;i<=mid;i++)add(a[i].x,a[i].y,-1);

    for(int i=1;i<=lt;i++)que[st+i-1]=lq[i];
    for(int i=1;i<=rt;i++)que[st+lt+i-1]=rq[i];
    
    solve(l,mid,st,st+lt-1);
    solve(mid+1,r,st+lt,ed); 
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            ++cnt;
            cin>>a[cnt].val;
            a[cnt].x=i,a[cnt].y=j;    
        }
    for(int i=1;i<=q;i++)
    {
        cin>>que[i].x1>>que[i].y1>>que[i].x2>>que[i].y2>>que[i].k;
        que[i].id=i;
    }
    sort(a+1,a+cnt+1);

    solve(1,cnt,1,q);
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";   
    
    return 0;
}

例4 P3332 K大数查询

使用线段树做区间修改，然后再整体二分

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=5e4+10;
int n,q;
struct Node{
    ll l,r,c;
    int op,id;
}que[N],lq[N],rq[N];
ll t[N*4],ans[N];  //线段树
ll lazy[N*4];
bool flag[N];
void pushdown(int p,int l,int r)
{
    if(lazy[p])
    {
        int mid=l+r>>1;
        lazy[p<<1]+=lazy[p]; lazy[p<<1|1]+=lazy[p];
        t[p<<1]+=lazy[p]*(mid-l+1);  t[p<<1|1]+=lazy[p]*(r-mid); 
        lazy[p]=0;
    }
}
void modify(int p,int l,int r,int ql,int qr,ll d)
{
    if(ql<=l && r<=qr)
    {
       t[p]+=d*(r-l+1);
       lazy[p]+=d;
       return;
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    if(ql<=mid)modify(p<<1,l,mid,ql,qr,d);
    if(mid<qr)modify(p<<1|1,mid+1,r,ql,qr,d);
    
    t[p]=t[p<<1]+t[p<<1|1];
}
int query(int p,int l,int r,int ql,int qr)
{
    if(ql<=l && r<=qr)
    {
        return t[p];
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    int ret=0;
    if(ql<=mid)ret+=query(p<<1,l,mid,ql,qr);
    if(mid<qr)ret+=query(p<<1|1,mid+1,r,ql,qr);
    return ret;
}

void solve(ll lval,ll rval,int st,int ed)
{
    if(st>ed)return;
    if(lval==rval){
        for(int i=st;i<=ed;i++)
            if(que[i].op==2)//查询
                ans[que[i].id]=lval;
        return;
    }
    ll mid=lval+rval>>1;
    int lt=0,rt=0;
    for(int i=st;i<=ed;i++)
    {
        if(que[i].op==1)//插入操作
        {
            if(que[i].c>mid)modify(1,1,n,que[i].l,que[i].r,1),rq[++rt]=que[i];
            else lq[++lt]=que[i];
        }
        else{  //查询
            int num=query(1,1,n,que[i].l,que[i].r);
            if(num>=que[i].c)rq[++rt]=que[i];
            else que[i].c-=num,lq[++lt]=que[i];
        }
    }
    //还原
    for(int i=ed;i>=st;i--)
        if(que[i].op==1 && que[i].c>mid)modify(1,1,n,que[i].l,que[i].r,-1);

    for(int i=1;i<=lt;i++)que[st+i-1]=lq[i];
    for(int i=1;i<=rt;i++)que[st+lt+i-1]=rq[i];

    solve(lval,mid,st,st+lt-1);
    solve(mid+1,rval,st+lt,ed);
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=q;i++)
    {
        int op,l,r,c;
        cin>>que[i].op>>que[i].l>>que[i].r>>que[i].c;
        if(que[i].op==2)flag[i]=1;
        que[i].id=i;               //查询
    }
    solve(1,1ll<<63,1,q);

    for(int i=1;i<=q;i++)
        if(flag[i])cout<<ans[i]<<"\n";    
    
    return 0;
}

学习完毕

{{ select(1) }}

#edu2005. 基于值域的整体分治算法（整体二分）

例1：静态区间第k小/P3834可持久化线段树

例2. 动态区间第k小[P2617 Dynamic Rankings]

例3. 静态矩阵第k小 P1527 [国家集训队] 矩阵乘法

例4 P3332 K大数查询

学习完毕

状态

开发

支持

#edu2005. 基于值域的整体分治算法（整体二分）

基于值域的整体分治算法（整体二分）

例1： 静态区间第k小/P3834可持久化线段树

例2. 动态区间第k小[P2617 Dynamic Rankings]

例3. 静态矩阵第k小 P1527 [国家集训队] 矩阵乘法

例4 P3332 K大数查询

学习完毕

状态

开发

支持

还没有账户？

登录

例1：静态区间第k小/P3834可持久化线段树