首页 > 其他分享 >整体二分学习笔记

整体二分学习笔记

时间：2023-04-27 18:45:11浏览次数：35  
标签：二分 cnt int mid lval 笔记 st 学习

整体二分

引入

对于一堆询问，如果每个单独的询问都可以二分解决的话，时间复杂度为 \(O(NM\log N)\)，但实际上每次二分都会有一些残留信息被我们扔掉，如果我们将所有询问一起二分，就可以最大时间的减小复杂度。

讲解

经典例题：区间第k大

给定一个序列 a 和一个整数 S，有 2 种操作：

1. 将 a 序列的第 k 个数变为 w
2. 查询区间[l, r]中有多少数小于等于 S

这个题可以用一个树状数组来维护，对于 a 序列，我们将所有小于等于 S 的数的位置在树状数组中 +1，表示这个位置有一个小于等于 S 的数。

对于 1 操作，我们可以看作删除一个数再添加一个数，先看 \(a_k\) 是否大于 S，如果不大于则让这个位置 -1，再看 w 是否大于 S，如果小于等于就在这个位置 +1。

对于 2 操作，可以直接执行 ask(r) - ask(l - 1)，即为这个范围内有多少数小于等于 S。

给定 a 序列，求第 k 大的数是几

这个问题也可以用二分来解决。每次二分一个 mid，查询值域[l, r]内有多少小于 mid 的数，记为 cnt。如果 \(cnt >= k\)，可以在值域[l, mid]中接着二分。如果 \(cnt < k\)，可以令 k -= cnt，在值域[mid + 1, r]中继续二分。

给定 a 序列，有 m 个询问，每次询问区间[l, r]中的第 k 大数

我们可以按照上面第二题的思路，每个询问进行一次二分，时间复杂度为 \(O(NM\log N)\)，不能承受。

考虑每次二分值域，都会有一大部分信息被扔掉。所以我们应该对所有的询问全部进行二分。

算法流程如下：

  1. 值域达到边界，直接将当前的这些达到边界的询问的答案记录，返回即可。
  2. 二分出 mid，按照上面第一题的方法，用树状数组查找[l, r]中不大于 mid 的数的个数，记为 cnt。
  3. 再应用第二题的方法，将 \(k <= cnt\) 的询问放到 lq 序列中， 将 \(k > cnt\) 的询问的 k -= cnt，再放到 rq 序列中。
  4. 递归二分求解 lq 和 rq 序列。

同时，为了简化代码，将序列转化为 n 个插入操作，具体实现可以看上面的第一题。

代码：


#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
struct Q
{
    int op, x, y, k;
}q[N], lq[N], rq[N];

int ans[N];
int tt;
int n, m;
vector<int> nums;

struct tree_array
{
    int c[N];
    #define lowbit(x) x & -x

    inline void add(int x, int val)
    {
        for(; x <= n; x += lowbit(x)) c[x] += val;
    }

    inline int query(int x)
    {
        int res = 0;
        for(; x; x -= lowbit(x)) res += c[x];
        return res;
    }
}bit;

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(q[i].op > 0) ans[q[i].op] = lval;
        return;
    }

    int mid = lval + rval >> 1;
    int lt = 0, rt = 0;
    for(int i = st; i <= ed; i ++ )
    {
        if(q[i].op == 0)
        {
            if(q[i].y <= mid) bit.add(q[i].x, 1), lq[++ lt] = q[i];
            else rq[++ rt] = q[i];
        }
        else
        {
            int l = q[i].x, r = q[i].y;
            int cnt = bit.query(r) - bit.query(l - 1);
            if(cnt >= q[i].k) lq[++ lt] = q[i];
            else q[i].k -= cnt, rq[++ rt] = q[i];
        }
    }

    for(int i = ed; i >= st; i -- ) 
        if(q[i].op == 0 && q[i].y <= mid)
            bit.add(q[i].x, -1);
        
    for(int i = 1; i <= lt; i ++ ) q[st + i - 1] = lq[i];
    for(int i = 1; i <= rt; i ++ ) q[st + lt + i - 1] = rq[i];

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

int main()
{
    n = read(), m = read();
    memset(bit.c, 0, sizeof bit.c);
    for(int i = 1; i <= n; i ++ )
    {
        int val;
        scanf("%d", &val);
        q[++ tt] = {0, i, val, 0};
    }

    for(int i = 1; i <= m; i ++ )
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        q[++ tt] = {i, l, r, k};
    }

    solve(-INF, INF, 1, tt);

    for(int i = 1; i <= m; i ++ )
        printf("%d\n", ans[i]);
    
    return 0;
}

扩展：带修区间第 k 大

当然可以用树套树在线做，但是也可以用整体二分，而且运行起来更加优秀。

将每个修改操作看作 2 种操作，和上面的第一题一样，小于 mid 的就 -1，添加的数小于 mid 就 +1。

时间复杂度 \(O(N\log N)\)。

完整代码：


#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m, tt, id;

struct tree_array
{
    int c[N];
    #define lowbit(x) x & -x

    inline void add(int x, int val)
    {
        for(; x <= n; x += lowbit(x)) c[x] += val;
    }

    inline int query(int x)
    {
        int res = 0;
        for(; x; x -= lowbit(x)) res += c[x];
        return res;
    }
} bit;

struct Q
{
    int op, x, y, k;
}q[N], lq[N], rq[N];

int ans[N], a[N];

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(q[i].op > 0) 
                ans[q[i].op] = lval;
        return;
    }

    int mid = lval + rval >> 1;
    int lt = 0, rt = 0;
    for(int i = st; i <= ed; i ++ )
    {
        if(q[i].op <= 0)
        {
            if(q[i].y <= mid) bit.add(q[i].x, q[i].k), lq[++ lt] = q[i];
            else rq[++ rt] = q[i];
        }
        else
        {
            int l = q[i].x, r = q[i].y;
            int cnt = bit.query(r) - bit.query(l - 1);
            if(cnt >= q[i].k) lq[++ lt] = q[i];
            else q[i].k -= cnt, rq[++ rt] = q[i];
        }
    }

    for(int i = st; i <= ed; i ++ )
        if(q[i].op <= 0 && q[i].y <= mid)
            bit.add(q[i].x, -q[i].k);
    
    for(int i = 1; i <= lt; i ++ ) q[i + st - 1] = lq[i];
    for(int i = 1; i <= rt; i ++ ) q[i + lt + st - 1] = rq[i];

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

int main()
{
    n = read(), m = read();

    for(int i = 1; i <= n; i ++ )
    {
        a[i] = read();
        q[++ tt] = {0, i, a[i], 1};
    }

    for(int i = 1; i <= m; i ++ )
    {
        char op[5];
        scanf("%s", op);
        
        if(op[0] == 'Q')
        {
            int l = read(), r = read(), k = read();
            q[++ tt] = {++ id, l, r, k};
        }
        else
        {
            int x = read(), y = read();
            q[++ tt] = {-1, x, a[x], -1};
            q[++ tt] = {0, x, y, 1};
            a[x] = y;
        }
    }

    solve(-INF, INF, 1, tt);

    for(int i = 1; i <= id; i ++ )
        printf("%d\n", ans[i]);
    
    return 0;
}

练习

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

本题维护一个二维树状数组，然后和区间第 k 大没有一点不同。

struct tree_array
{
    int c[N][N];
    #define lowbit(x) x & -x

    inline 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;
    }

    inline int query(int x, int y)
    {
        if(!x || !y) return 0;
        int res = 0;
        for(int i = x; i; i -= lowbit(i))
            for(int j = y; j; j -= lowbit(j))
                res += c[i][j];
        return res;
    }

    inline int ask(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);
    }
} bit;

struct Q
{
    int op, x1, y1, x2, y2, k;
}q[M], lq[M], rq[M];
int ans[M];
int tt;

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(q[i].op != 0)
                ans[q[i].op] = lval;
        return;
    }
    int mid = lval + rval >> 1;
    int lt = 0, rt = 0;
    for(int i = st; i <= ed; i ++ )
    {
        if(q[i].op == 0)
        {
            if(q[i].k <= mid) bit.add(q[i].x1, q[i].y1, 1), lq[++ lt] = q[i];
            else rq[++ rt] = q[i];
        }
        else
        {
            int cnt = bit.ask(q[i].x1, q[i].y1, q[i].x2, q[i].y2);
            if(cnt >= q[i].k) lq[++ lt] = q[i];
            else q[i].k -= cnt, rq[++ rt] = q[i];
        }
    }

    for(int i = st; i <= ed; i ++ )
        if(q[i].op == 0 && q[i].k <= mid)
            bit.add(q[i].x1, q[i].y1, -1);
    
    for(int i = 1; i <= lt; i ++ ) q[i + st - 1] = lq[i];
    for(int i = 1; i <= rt; i ++ ) q[st + lt + i - 1] = rq[i];

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

P3527 [POI2011]MET-Meteors

很明显每个询问都能二分求解，时间长的肯定有更大概率收集全。

注意 \(l < r\) 的情况，这种情况可以将数组开成两倍，统计时加上长度即可。

统计每个国家收集多少的时候可以用图论的方式统计。

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e6 + 10;
int n, m, k;
int c[N], p[N], ans[N];

struct tree_array
{
    int c[N];
    #define lowbit(x) x & -x

    inline void add(int x, int val)
    {
        for(; x <= m * 2; x += lowbit(x)) c[x] += val;
    }

    inline int query(int x)
    {
        int res = 0;
        for(; x; x -= lowbit(x)) res += c[x];
        return res;
    }
} bit;

struct C
{
    int x, y, val;
}ch[N];

struct Q
{
    int c, k, h;
}q[N], lq[N], rq[N];

int e[N], ne[N], idx;

void add(int a, int b)
{
    e[++ idx] = b, ne[idx] = q[a].h, q[a].h = idx;
}

void solve(int lval, int rval, int st, int ed)
{
    if(st > ed) return;
    if(lval == rval)
    {
        for(int i = st; i <= ed; i ++ )
            ans[q[i].c] = lval;
        return;
    }

    int mid = lval + rval >> 1, lt = 0, rt = 0;
    for(int i = lval; i <= mid; i ++ ) 
    {
        bit.add(ch[i].x, ch[i].val), bit.add(ch[i].y + 1, -ch[i].val);
    }

    for(int i = st; i <= ed; i ++ )
    {
        int cnt = 0;
        for(int k = q[i].h; k && cnt <= q[i].k; k = ne[k])
        {
            int j = e[k];
            cnt += bit.query(j) + bit.query(j + m);
        }
        if(cnt >= q[i].k) lq[++ lt] = q[i];
        else q[i].k -= cnt, rq[++ rt] = q[i];
    }
    
    for(int i = lval; i <= mid; i ++ )
        bit.add(ch[i].x, -ch[i].val), bit.add(ch[i].y + 1, ch[i].val);

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

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

signed main()
{
    n = read(), m = read();

    for(int i = 1; i <= m; i ++ ) 
    {
        c[i] = read();
        add(c[i], i);
    }

    for(int i = 1; i <= n; i ++ )
    {
        q[i].k = read();
        q[i].c = i;
    }

    k = read();
    for(int i = 1; i <= k; i ++ )
    {
        int l = read(), r = read(), val = read();
        if(r < l) r += m;
        ch[i] = {l, r, val};
    }

    solve(1, k + 1, 1, n);

    for(int i = 1; i <= n; i ++ )
        if(ans[i] == k + 1) puts("NIE");
        else printf("%d\n", ans[i]);
    
    return 0;
}

P4602 [CTSC2018] 混合果汁

本题二分也很好想出来，唯一的难点在于怎么快速回答每个询问。

维护一个权值线段树，下标存储价格，内部存储物品的个数和总价格。

一开始先按美味值排序，维护一直到 mid 的前缀中的物品即可。


#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e6 + 10;
int n, m, cur;
int ans[N];

struct segment
{
    int v, sum;
}t[N << 2];

inline void pushup(int p)
{
    t[p].v = t[p << 1].v + t[p << 1 | 1].v;
    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}

void change(int p, int l, int r, int pos, int v)
{
    if(l == r) 
    {
        t[p].v += v;
        t[p].sum = l * t[p].v;
        return;
    }

    int mid = l + r >> 1;
    if(pos <= mid) change(p << 1, l, mid, pos, v);
    else change(p << 1 | 1, mid + 1, r, pos, v);
    pushup(p);
}

int query(int p, int l, int r, int v)
{
    if(!v) return 0;
    if(l == r) return l * v;
    int mid = l + r >> 1;
    if(t[p << 1].v >= v) return query(p << 1, l, mid, v);
    else return t[p << 1].sum + query(p << 1 | 1, mid + 1, r, v - t[p << 1].v);
}

int query1(int p, int l, int r, int pos)
{
    if(l == r) return t[p].sum;
    int mid = l + r >> 1;
    if(pos <= mid) return query1(p << 1, l, mid, pos);
    else return query1(p << 1 | 1, mid + 1, r, pos);
}

struct data
{
    int d, p, l;

    bool operator<(const data &D) const
    {
        return d > D.d;
    }
} a[N];

struct Q
{
    int id, g, l;
} q[N], lq[N], rq[N];

void solve(int lval, int rval, int st, int ed)
{
    if (st > ed || lval > rval)
        return;
    if (lval == rval)
    {
        for (int i = st; i <= ed; i ++)
            ans[q[i].id] = a[lval].d;
        return;
    }

    int mid = lval + rval >> 1;
    while(cur < mid)
        cur ++, change(1, 1, N - 1, a[cur].p, a[cur].l);
    while(cur > mid)
        change(1, 1, N - 1, a[cur].p, -a[cur].l), cur --;

    int lt = 0, rt = 0;
    for(int i = st; i <= ed; i ++ )
    {
        if(q[i].l > t[1].v) rq[++ rt] = q[i];
        else if(query(1, 1, N - 1, q[i].l) <= q[i].g) lq[++ lt] = q[i];
        else rq[++ rt] = q[i];
    }

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

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

signed main()
{
    n = read(), m = read();

    for (int i = 1; i <= n; i++)
    {
        a[i].d = read(), a[i].p = read(), a[i].l = read();
    }

    a[++ n] = {-1, 0, 0x3f3f3f3f};
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= m; i++)
    {
        int D = read(), L = read();
        q[i] = {i, D, L};
    }

    solve(1, n, 1, m);

    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);

    return 0;
}

标签：二分,cnt,int,mid,lval,笔记,st,学习
From： https://www.cnblogs.com/crimsonawa/p/17359940.html

相关文章

  • python+playwright 学习-59 设置默认允许麦克风和摄像头等权限
    前言有些场景在使用的时候，会弹出一些权限框，比如麦克风和摄像头等，通过监听alert是没法捕获的。正确做法是给浏览器设置默认允许麦克风和摄像头等权限，不让弹窗出来。使用context的grant_permissions方法加权限。权限框弹窗示例这种弹窗是权限窗，不是alert解决办法contex......
  • AJAX 了解学习
    AJAX=异步JavaScript和XML。AJAX是一种用于创建快速动态网页的技术。通过在后台与服务器进行少量数据交换，AJAX可以使网页实现异步更新。这意味着可以在不重新加载整个网页的情况下，对网页的某部分进行更新。传统的网页（不使用AJAX）如果需要更新内容，必需重载整个网页面。......
  • 前端学习笔记--主流web框架
    主流的web框架1.Django框架 大而全，自带的功能组件非常多！类似航空母舰 2.flask框架 小而精,自身的功能组件非常少！类似游骑兵 第三方模块多，也受限于第三方模块 ps:三行代码就可以启动一个flask后端服务 3.tornado框架 异步非阻塞 速度非常快，可以用于开发游戏服务器4.其......
  • 浅谈机器学习的学习策略及技术应用
    导言：在科技飞速发展的今天，机器学习已成为人工智能领域的重要组成部分。作为一名程序员，掌握机器学习技术已经成为提升自身竞争力的必备技能。本文将从学习策略和技术应用两个方面，探讨机器学习的相关内容。一、学习策略加强基础知识：机器学习是建立在数学、统计学、计算机科学等多个学......
  • Cpp学习
    C++学习数组方便存放同类型的元素一维数组一维数组数组名代表数组的首地址一维数组名可以计算出数组在内存空间所占内存大小二维数组二维数组名代表二维数组的首地址，也可以查看某行的首地址二维数组可以计算出数组在内存空间所占内存大小，也可以计算出某行所占内存大小......
  • 学习总结
    题目分析1001提交情况：1A解决方法：\(÷2\)和\(-x\)选一个减的少的减就可以了。1002提交情况：2A\(1st\)：没出示数据范围，直接模拟TLE。解决方法：考虑到每次修改至多影响\(1\)位的匹配情况，所以一开始将所有不匹配的地方放进一个set里面，每次修改字符在set中insert或era......
  • selenium笔记之PC浏览器仿真移动端
    本来写的UI走查的代码主要场景是web浏览器，少量h5页面校验不值得大费周章用真机去跑背景：首先尝试了移动端真机巡检，但是不同机型，需要调试出合适的appPackage以及其它参数上一段代码：publicAndroidDrivergetWebDriverForAPP(){AndroidDriverappDriver=null;......
  • HBase初步学习与性能测试
    1、HBase定义HBase(HadoopDatabase)是一个分布式、可扩展的NoSQL数据库。基于BigTable，为Hadoop框架当中的结构化数据提供存储服务，是面向列的分布式数据库。这一点与HDFS是不一样的，HDFS是分布式文件系统，管理的是存放在多个硬盘上的数据文件，不支持随机修改，而Hbase管理的是类似于k......
  • 关于深度学习中的两个概念weights和checkpoint
    WEIGHT和checkpoint都是深度学习中的概念，但它们的含义和作用有所不同。WEIGHT通常指的是神经网络中的参数。在训练过程中，神经网络的参数会不断更新以提高模型的准确性。这些参数通常被存储在称为“权重”的数组中。因此，当我们保存模型的权重时，我们实际上是将神经网络的参数保存到......
  • 深度学习--GAN实战
    深度学习--GAN实战DCGANimporttorchfromtorchimportnn,optim,autogradimportnumpyasnpimportvisdomimportrandom#用python-mvisdom.server启动服务h_dim=400batchsz=512viz=visdom.Visdom(use_incoming_socket=False)classGenerator(nn.Module......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99