整体二分

简述

相当类似 CDQ 的一种算法。说的冠冕一点，是对于每个 mid 批量处理查询的算法。

更加简单的说法就是：二分答案，对于每个 \(mid\)，用二维数点之类的方法判断每个查询的答案是大于 \(mid\) 还是小于 \(mid\)，据此将查询分为两类继续递归下去。（一般来说会把修改也放进来，使用类似 cdq 的方法离线维护）

一般适用于离线可带修区间第 \(k\) 大、第 \(k\) 小的问题，记得转化为这种问题时想到整体二分。

标程

目标题目：P2617 Dynamic Rankings（而不是模板题）

要说的都在代码里了。

/*
主体来说，就是把查询和修改按顺序放到一个数组里。
二分的时候，按顺序，<=mid的修改改动其下标+1，查询时根据下标范围内是否>k来判断在左侧还是右侧（二维数点）
最后把数组合并，并清空树状数组
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll n,m;
ll a[N],c[N],t[N],ans[N];
inline ll lowbit(ll x)
{
    return x&-x;
}
ll ask(ll p)
{
    ll res=0;
    for(ll i=p;i;i-=lowbit(i))
        res+=t[i];
    return res;
}
void add(ll p,ll x)
{
    if(!p) return;
    for(ll i=p;i<=n;i+=lowbit(i))
        t[i]+=x;
}

//type：0 表示询问，非0表示修改
//id：表示修改的位置（感觉放到k里更好）
//l,r,k：表示查询[l,r]的第k小
//v：表示修改为的值
struct node
{
    ll type,id;
    ll l,r,k;
    ll v;
}q[N*3],q1[N*3],q2[N*3];//q存放所有修改和查询（按顺序），q1存放将要递归至左边的，q2存放右边的
ll cnt;
void solve(ll lq,ll rq,ll lv,ll rv)
{
    if(lq>rq)
        return;
    if(lv==rv)
    {
        for(ll i=lq;i<=rq;i++)
            if(!q[i].type)
                ans[q[i].id]=lv;
        return;
    }
    ll mid=(lv+rv)>>1,cnt1=0,cnt2=0;
    for(ll i=lq;i<=rq;i++)
    {
        if(q[i].type)
        {
            if(q[i].v<=mid)
            {
                add(q[i].id,q[i].type);//修改
                q1[++cnt1]=q[i];
            }
            else
                q2[++cnt2]=q[i];
        }
        else
        {
            ll num=ask(q[i].r)-ask(q[i].l-1);//查询下标在[l,r]间的<=mid数有多少
            if(num>=q[i].k)//注意符号
                q1[++cnt1]=q[i];
            else
            {
                q[i].k-=num;
                q2[++cnt2]=q[i];
            }
        }
    }
    for(ll i=lq;i<=rq;i++)//清空BIT
        if(q[i].type && q[i].v<=mid)
            add(q[i].id,-q[i].type);
    for(ll i=1;i<=cnt1;i++)//合并两个数组
        q[lq+i-1]=q1[i];
    for(ll i=1;i<=cnt2;i++)
        q[lq+cnt1+i-1]=q2[i];
    solve(lq,lq+cnt1-1,lv,mid);
    solve(lq+cnt1,rq,mid+1,rv);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        q[++cnt]={1,i,0,0,0,a[i]};
    }
    ll cntq=0;
    for(ll i=1;i<=m;i++)
    {
        char op;
        cin>>op;
        if(op=='Q')
        {
            cnt++;
            cin>>q[cnt].l>>q[cnt].r>>q[cnt].k;
            q[cnt].type=0;
            q[cnt].id=++cntq;
        }
        else
        {
            ll p,x;
            cin>>p>>x;
            q[++cnt]={-1,p,0,0,0,a[p]};
            a[p]=x;
            q[++cnt]={1,p,0,0,0,a[p]};
        }
    }
    solve(1,cnt,0,1e9);
    for(ll i=1;i<=cntq;i++)
        cout<<ans[i]<<"\n";
    return 0;
}

调题记录

全都是基于模板改一下计数方法或者转化一下题面。

P1527 [国家集训队] 矩阵乘法

单修矩查树状数组即可。\(\color{red}\text{WA}\)：空间开小了。

P7424 [THUPC2017] 天天爱射击

转化题意：每块木板所在区间内，射出时间第 \(k\) 早的子弹是哪一个。

\(\color{red}\text{WA}\)：有的木板一直不会碎，二分的初始值域设小了。也要小心值域设太大越界。

P4175 [CTSC2008] 网络管理

一个很 naive 的想法是树链剖分维护链上内容，但是完全没必要。只需树状数组维护返根链上的计数，查询就是树上差分，修改就是子树修改（摊成dfn序即可）。

\(\color{red}\text{WA}\)：求的是第 \(k\) 大，不是第 \(k\) 小！由于一个点有两个编号（id、dfn），把他们两个搞混了，还没法用样例测出来。此时可以考虑分块瞪眼法，先确定一部分的正确性，再去瞪下一部分。