首页 > 其他分享 >整体二分板子

整体二分板子

时间:2023-03-10 17:22:32浏览次数:55  
标签:二分 ch int void 整体 板子 read inline getchar

P3834 可持久化线段树 2

静态区间第 \(k\) 小。

存个不带修整体二分板子。

离散化,拿树状数组维护一下元素出现次数。

假设当前区间内所有答案都是 \(mid\)。

实时更新,这样就可以计算 \(\le mid\) 的数,也就是排名啦。

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
using namespace std;

const int N = 5e5 + 10, inf = 1e9;
int n, m, tot, a[N], b[N], t[N], res[N];
unordered_map <int, int> Map;

inline void upd(int pos, int val) {
    for (; pos <= n; pos += lowbit(pos)) t[pos] += val;
    return ;
}

inline int query(int pos, int res = 0) {
    for (; pos; pos -= lowbit(pos)) res += t[pos];
    return res;
}

struct Query { int l, r, k, id, typ; } qry[N], qy[N], _qy[N];
inline void solve(int l, int r, int ql, int qr) {
    if (ql > qr) return ;
    if (l == r) {
        for (int i = ql; i <= qr; ++i)
            if (qry[i].typ == 2) res[qry[i].id] = l;
        return ;
    }
    int mid = (l + r) >> 1, cnt = 0, _cnt = 0;
    for (int i = ql; i <= qr; ++i) {
        if (qry[i].typ & 1) {
            if (qry[i].l <= mid)
                upd(qry[i].id, 1), qy[++cnt] = qry[i];
            else _qy[++_cnt] = qry[i];
        } else {
            int k = query(qry[i].r) - query(qry[i].l - 1);
            if (qry[i].k <= k) qy[++cnt] = qry[i];
            else qry[i].k -= k, _qy[++_cnt] = qry[i];
        }
    }
    for (int i = 1; i <= cnt; ++i)
        if (qy[i].typ & 1) upd(qy[i].id, -1);
    for (int i = 1; i <= cnt; ++i) qry[ql + i - 1] = qy[i];
    for (int i = 1; i <= _cnt; ++i) qry[ql + cnt + i - 1] = _qy[i];
    solve(l, mid, ql, ql + cnt - 1);
    solve(mid + 1, r, ql + cnt, qr); return ;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n); int len = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; ++i) Map[a[i]] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
    for (int i = 1; i <= n; ++i) qry[++tot] = {Map[a[i]], -1, -1, i, 1};
    for (int i = 1, l, r, k; i <= m; ++i)
        cin >> l >> r >> k, qry[++tot] = {l, r, k, i, 2};
    solve(1, len, 1, tot);
    for (int i = 1; i <= m; ++i) cout << b[res[i]] << endl;
    return 0;
}

P1527 矩阵乘法

静态子矩形内第 \(k\) 小。

相同的做法,二维的树状数组。没了。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define lowbit(x) ((x) & -(x))
using namespace std;

template <typename T> inline void read(T &x) {
    x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}

template <typename T, typename ...Args>
inline void read(T &x, Args &...args) { read(x), read(args...); }

const int N = 1e3 + 10, M = 1e6 + 10;
int n, q, tot, b[M], res[M], a[N][N], t[N][N];
__gnu_pbds::gp_hash_table <int, int> Map;

inline void upd(int x, int y, int val) {
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= n; j += lowbit(j)) t[i][j] += val;
    return ;
}

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

struct Query { int l, r, _l, _r, k, x, y, typ; } qry[M], qy[M], _qy[M];
inline void solve(int l, int r, int ql, int qr) {
    if (ql > qr) return ;
    if (l == r) {
        for (int i = ql; i <= qr; ++i)
            if (qry[i].typ == 2) res[qry[i].x] = l;
        return ;
    }
    int cnt = 0, _cnt = 0, mid = (l + r) >> 1;
    for (int i = ql; i <= qr; ++i) {
        if (qry[i].typ & 1) {
            if (qry[i].l <= mid) upd(qry[i].x, qry[i].y, 1), qy[++cnt] = qry[i];
            else _qy[++_cnt] = qry[i];
        } else {
            int k = query(qry[i]._l, qry[i]._r);
            k -= query(qry[i].l - 1, qry[i]._r) + query(qry[i]._l, qry[i].r - 1);
            k += query(qry[i].l - 1, qry[i].r - 1);
            if (qry[i].k <= k) qy[++cnt] = qry[i];
            else qry[i].k -= k, _qy[++_cnt] = qry[i];
        }
    }
    for (int i = 1; i <= cnt; ++i)
        if (qy[i].typ & 1) upd(qy[i].x, qy[i].y, -1);
    for (int i = 1; i <= cnt; ++i) qry[ql + i - 1] = qy[i];
    for (int i = 1; i <= _cnt; ++i) qry[ql + cnt + i - 1] = _qy[i];
    solve(l, mid, ql, ql + cnt - 1);
    solve(mid + 1, r, ql + cnt, qr); return ;
}

int main() {
    read(n, q); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
        read(a[i][j]), b[++tot] = a[i][j];
    sort(b + 1, b + 1 + tot); int len = unique(b + 1, b + 1 + tot) - b - 1;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
        Map[a[i][j]] = lower_bound(b + 1, b + 1 + len, a[i][j]) - b; tot = 0;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
        qry[++tot] = {Map[a[i][j]], -1, -1, -1, -1, i, j, 1};
    for (int i = 1, l, r, _l, _r, k; i <= q; ++i)
        read(l, r, _l, _r, k), qry[++tot] = {l, r, _l, _r, k, i, 0, 2};
    solve(1, len, 1, tot); for (int i = 1; i <= q; ++i) printf("%d\n", b[res[i]]);
    return 0;
}

P2617 Dynamic Rankings

想当年我是拿分块写的这题。

带修整体二分板子题。

把修改操作拆成删除上一次该位置上的元素,和在这个位置上添加一个元素。

对于每个操作记一个标记 \(tag\) 就行,撤销操作就加上 \(-tag\)。

就酱。双 \(\log\) 无所畏惧。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define lowbit(x) (x & -x)
using namespace std;

template <typename T> inline void read(T &x) {
    x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} template <typename T, typename ...Args>
inline void read(T &x, Args &...args) { read(x), read(args...); }
inline void readch(char &ch) {
    ch = getchar(); while (ch > 'Z' || ch < 'A') ch = getchar(); return ;
} template <typename T> inline void write(T x) {
    if (x > 9) write(x / 10); putchar(x % 10 ^ 48); return ;
}

const int N = 5e5 + 10;
int n, m, g, tot, a[N], b[N], t[N], lst[N], res[N];
__gnu_pbds::gp_hash_table <int, int> Map;
struct Query { int l, r, k, id, typ, val; } qry[N], qy[N], _qy[N];
struct haha { char op; int l, r, k; } h[N];

inline void upd(int pos, int val) {
    for (; pos <= n; pos += lowbit(pos)) t[pos] += val;
    return ;
}

inline int query(int pos, int res = 0) {
    for (; pos; pos -= lowbit(pos)) res += t[pos];
    return res;
}

inline void solve(int l, int r, int ql, int qr) {
    if (ql > qr) return ;
    if (l == r) {
        for (int i = ql; i <= qr; ++i)
            if (qry[i].typ == 2) res[qry[i].id] = l;
        return ;
    }
    int mid = (l + r) >> 1, cnt = 0, _cnt = 0;
    for (int i = ql; i <= qr; ++i) {
        if (qry[i].typ & 1) {
            if (qry[i].l <= mid) upd(qry[i].id, qry[i].val), qy[++cnt] = qry[i];
            else _qy[++_cnt] = qry[i];
        } else {
            int k = query(qry[i].r) - query(qry[i].l - 1);
            if (qry[i].k <= k) qy[++cnt] = qry[i];
            else qry[i].k -= k, _qy[++_cnt] = qry[i];
        }
    }
    for (int i = 1; i <= cnt; ++i) if (qy[i].typ & 1) upd(qy[i].id, -qy[i].val);
    for (int i = 1; i <= cnt; ++i) qry[ql + i - 1] = qy[i];
    for (int i = 1; i <= _cnt; ++i) qry[ql + cnt + i - 1] = _qy[i];
    solve(l, mid, ql, ql + cnt - 1);
    solve(mid + 1, r, ql + cnt, qr); return ;
}

int main() {
    read(n, m); for (int i = 1; i <= n; ++i) read(a[i]), b[++g] = a[i];
    for (int i = 1; i <= m; ++i) {
        readch(h[i].op), read(h[i].l, h[i].r);
        if (h[i].op == 'Q') read(h[i].k); else b[++g] = h[i].r;
    }
    sort(b + 1, b + 1 + g); int len = unique(b + 1, b + 1 + g) - b - 1;
    for (int i = 1; i <= n; ++i) Map[a[i]] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
    for (int i = 1; i <= m; ++i)
        if (h[i].op == 'C') Map[h[i].r] = lower_bound(b + 1, b + 1 + len, h[i].r) - b;
    for (int i = 1; i <= n; ++i) qry[++tot] = {lst[i] = Map[a[i]], -1, -1, i, 1, 1};
    for (int i = 1; i <= m; ++i) {
        if (h[i].op == 'Q') qry[++tot] = {h[i].l, h[i].r, h[i].k, i, 2, 0};
        else {
            qry[++tot] = {lst[h[i].l], -1, -1, h[i].l, 1, -1};
            qry[++tot] = {lst[h[i].l] = Map[h[i].r], -1, -1, h[i].l, 1, 1};
        }
    }
    solve(1, len, 1, tot); for (int i = 1; i <= m; ++i)
        if (res[i]) write(b[res[i]]), puts("");
    return 0;
}

标签:二分,ch,int,void,整体,板子,read,inline,getchar
From: https://www.cnblogs.com/MistZero/p/Parallel-Binsearch.html

相关文章

  • Mybatis 源码(二):整体设计概览
    1、Mybatis整体架构Mybatis的整体框架分为三层,分别是基础支持层、核心处理层、和接口层。 1.1、接口层SqlSession是接口层的核心对象,是应用程序与Mybatis交互......
  • 最小生成树板子
     #include<bits/stdc++.h>usingnamespacestd; constintN=5003,M=2e5+2;intf[N],n,m;structE{ intx,y,z;}e[M];intfind(intx){ returnx==f[x......
  • Unity 火炬之光 部分学习笔记(一) 游戏整体架构
    mmo开源项目泰课正版课程跳转链接b站学习视频跳转链接【RPG类游戏复刻-火炬之光】开源项目源码学习跳转链接(项目为16年的,使用的NGUI)仅作为个人学习笔记,只记录......
  • 算法基础课笔记:第一章,基础算法 排序 + 二分
    这节课的内容排序快排归并排序二分整数二分浮点数二分如何提高自己敲模板的熟练度呢?反复的练,孰能生巧。重复3-5次。快排1.确定分界点2.调整区......
  • 二分法
      #include<iostream>usingnamespacestd;constintN=1e5+10;inta[N],st[N];intnum=0;intmain(){intn,q;cin>>n>>q;for(inti=1;i<=n;i++){cin>>a[i];......
  • 整数二分的边界条件
     有单调性的题目一定可以二分,没有单调性的可能可以二分,二分和单调性没有直接关系。整数二分的本质是边界,整个区间可以一份为二,一半满足一半不满足,则二分即可以找前一半......
  • 这个二分查找好难(Drying)
    DryingItisveryhardtowashandespeciallytodryclothesinwinter.ButJaneisaverysmartgirl.Sheisnotafraidofthisboringprocess.Janehasdecided......
  • HDU2199 Can you solve this equation? (二分查找)
    Canyousolvethisequation?TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):12794    AcceptedS......
  • 电磁计量整体解决方案
    在现代社会中,计量举足轻重,它涉及生活的方方面面、各行各业所有领域,我国目前按专业,把计量分为十大类计量,即长度计量、热学计量、力学计量、电磁学计量、无线电计量、时间频......
  • 环形链表(哈希表、链表)、寻找两个正序数组的中位数(数组、二分查找)、二进制求和(位
    环形链表(哈希表、链表)给定一个链表,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,我们使用整......