Template -「整体二分」
2024-09-06 23:56:53
写的简单。主要是留给自己做复习资料。
「BZOJ1901」Dynamic Rankings.
给定一个含有 \(n\) 个数的序列 \(a_1,a_2 \dots a_n\)，需要支持两种操作：
Q l r k表示查询下标在区间 \([l,r]\) 中的第 \(k\) 小的数。C x y表示将 \(a_x\) 改为 \(y\)。
引入整体二分。
其实就是我们对于二分到的一个值域 mid，去离线针对所有的询问进行 check。
具体是利用一些数据结构。
然后根据 check 和 mid 的大小将询问分为两拨，再分治下去解决问题。
参考于 OI-wiki 的板子很精简且思路便于理解。
#include <cstdio>
int Abs (int x) { return x < 0 ? -x : x; }
int Max (int x, int y) { return x > y ? x : y; }
int Min (int x, int y) { return x < y ? x : y; }
int Read () {
int x = 0, k = 1;
char s = getchar();
while (s < '0' || s > '9') {
if(s == '-')
k = -1;
s = getchar ();
}
while ('0' <= s && s <= '9')
x = (x << 3) + (x << 1) + (s ^ 48), s = getchar ();
return x * k;
}
void Write (int x) {
if(x < 0)
x = -x, putchar ('-');
if(x > 9)
Write (x / 10);
putchar (x % 10 + '0');
}
void Print (int x, char s) { Write (x), putchar (s); }
const int MAXN = 2e5 + 5;
char Opt[3];
int Ans[MAXN], BIT[MAXN], a[MAXN], n, m;
int Low_Bit (int x) {
return x & -x;
}
void Update (int k, int x) {
for (int i = k; i <= n; i += Low_Bit (i))
BIT[i] += x;
}
int Query (int k) {
int Res = 0;
for (int i = k; i >= 1; i -= Low_Bit (i))
Res += BIT[i];
return Res;
}
struct Node {
bool Type;
int Id, x, y, k;
Node () {}
Node (bool T, int I, int X, int Y, int K) {
Type = T, Id = I, x = X, y = Y, k = K;
}
} q[MAXN], Tmp[2][MAXN];
void Solve (int l, int r, int L, int R) {
if (l > r || L > R)
return ;
if (L == R) {
for (int i = l; i <= r; i++)
if (q[i].Type)
Ans[q[i].Id] = L;
return ;
}
int Mid = (L + R) >> 1, Cnt0 = 0, Cnt1 = 0;
for (int i = l; i <= r; i++)
if (q[i].Type) {
int Check = Query (q[i].y) - Query (q[i].x - 1);
if (q[i].k <= Check)
Tmp[0][++Cnt0] = q[i];
else
q[i].k -= Check, Tmp[1][++Cnt1] = q[i];
}
else {
if (q[i].y <= Mid)
Update (q[i].x, q[i].k), Tmp[0][++Cnt0] = q[i];
else
Tmp[1][++Cnt1] = q[i];
}
for (int i = 1; i <= Cnt0; i++)
if (!Tmp[0][i].Type)
Update (Tmp[0][i].x, -Tmp[0][i].k);
for (int i = 1; i <= Cnt0; i++)
q[l + i - 1] = Tmp[0][i];
for (int i = 1; i <= Cnt1; i++)
q[l + Cnt0 + i - 1] = Tmp[1][i];
Solve (l, l + Cnt0 - 1, L, Mid), Solve (l + Cnt0, r, Mid + 1, R);
}
int main () {
n = Read (), m = Read ();
int p = 0, Tot = 0;
for (int i = 1, x; i <= n; i++)
x = Read (), q[++p] = Node (0, 0, i, x, 1), a[i] = x;
for (int i = 1, x, y; i <= m; i++) {
scanf ("%s", Opt + 1), x = Read (), y = Read ();
if (Opt[1] == 'Q') {
int k = Read ();
q[++p] = Node (1, ++Tot, x, y, k);
}
else
q[++p] = Node (0, 0, x, a[x], -1), q[++p] = Node (0, 0, x, y, 1), a[x] = y;
}
Solve (1, p, 0, 1e9);
for (int i = 1; i <= Tot; i++)
Print (Ans[i], '\n');
return 0;
}
「ZJOI2013」K 大数查询
需要维护 \(n\) 个可重整数集，集合的编号从 \(1\) 到 \(n\)。这些集合初始都是空集，有 \(m\) 个操作：
1 l r c表示将 \(c\) 加入到编号在 \([l,r]\) 内的集合中。2 l r c表示查询编号在 \([l,r]\) 内的集合的并集中，第 \(c\) 大的数是多少。
注意可重集的并是不去除重复元素的，如 \(\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}\)。
放在这里是因为发现它比上道题的唯一差别在于区间修改。
也就是说整体二分的数据结构理论上可以百搭。比如线段树。
#include <cstdio>
typedef long long LL;
int Abs (int x) { return x < 0 ? -x : x; }
int Max (int x, int y) { return x > y ? x : y; }
int Min (int x, int y) { return x < y ? x : y; }
int Read () {
int x = 0, k = 1;
char s = getchar();
while (s < '0' || s > '9') {
if(s == '-')
k = -1;
s = getchar ();
}
while ('0' <= s && s <= '9')
x = (x << 3) + (x << 1) + (s ^ 48), s = getchar ();
return x * k;
}
LL Read_LL () {
LL x = 0, k = 1;
char s = getchar();
while (s < '0' || s > '9') {
if(s == '-')
k = -1;
s = getchar ();
}
while ('0' <= s && s <= '9')
x = (x << 3) + (x << 1) + (s ^ 48), s = getchar ();
return x * k;
}
void Write (int x) {
if(x < 0)
x = -x, putchar ('-');
if(x > 9)
Write (x / 10);
putchar (x % 10 + '0');
}
void Print (int x, char s) { Write (x), putchar (s); }
const int MAXN = 5e4 + 5;
int Ans[MAXN], n, m;
struct Segment_Tree {
#define Lson p << 1
#define Rson p << 1 | 1
struct Segment_Node {
int l, r;
bool Clear;
LL Sum, Lazy;
Segment_Node () {}
Segment_Node (int L, int R, LL S, LL La, bool C) {
l = L, r = R, Sum = S, Lazy = La, Clear = C;
}
} Tr[MAXN * 4];
void Push (int p) {
if (Tr[p].Clear) {
Tr[Lson].Sum = Tr[Rson].Sum = 0;
Tr[Lson].Lazy = Tr[Rson].Lazy = 0;
Tr[Lson].Clear = Tr[Rson].Clear = true;
Tr[p].Clear = false;
}
if (Tr[p].Lazy) {
Tr[Lson].Sum += Tr[p].Lazy * (Tr[Lson].r - Tr[Lson].l + 1);
Tr[Rson].Sum += Tr[p].Lazy * (Tr[Rson].r - Tr[Rson].l + 1);
Tr[Lson].Lazy += Tr[p].Lazy, Tr[Rson].Lazy += Tr[p].Lazy;
Tr[p].Lazy = 0;
}
}
void Pull (int p) {
Tr[p].Sum = Tr[Lson].Sum + Tr[Rson].Sum;
}
void Make_Tree (int p, int l, int r) {
Tr[p].l = l, Tr[p].r = r;
if (Tr[p].l == Tr[p].r)
return ;
int Mid = (Tr[p].l + Tr[p].r) >> 1;
Make_Tree (Lson, l, Mid);
Make_Tree (Rson, Mid + 1, r);
}
void Update (int p, int l, int r, LL x) {
if (l <= Tr[p].l && Tr[p].r <= r) {
Tr[p].Sum += x * (Tr[p].r - Tr[p].l + 1), Tr[p].Lazy += x;
return ;
}
Push (p);
int Mid = (Tr[p].l + Tr[p].r) >> 1;
if (l <= Mid)
Update (Lson, l, r, x);
if (r > Mid)
Update (Rson, l, r, x);
Pull (p);
}
LL Query (int p, int l, int r) {
if (l <= Tr[p].l && Tr[p].r <= r)
return Tr[p].Sum;
Push (p);
int Mid = (Tr[p].l + Tr[p].r) >> 1;
LL Res = 0;
if (l <= Mid)
Res += Query (Lson, l, r);
if (r > Mid)
Res += Query (Rson, l, r);
Pull (p);
return Res;
}
#undef Lson
#undef Rson
} Seg;
struct Node {
LL k;
bool Type;
int Id, x, y;
Node () {}
Node (bool T, int I, int X, int Y, LL K) {
Type = T, Id = I, x = X, y = Y, k = K;
}
} q[MAXN], Tmp[2][MAXN];
void Solve (int l, int r, int L, int R) {
if (l > r || L > R)
return ;
if (L == R) {
for (int i = l; i <= r; i++)
if (q[i].Type)
Ans[q[i].Id] = L;
return ;
}
int Mid = (L + R) >> 1, Cnt0 = 0, Cnt1 = 0;
Seg.Tr[1].Clear = true, Seg.Tr[1].Sum = Seg.Tr[1].Lazy = 0;
for (int i = l; i <= r; i++)
if (q[i].Type) {
LL Check = Seg.Query(1, q[i].x, q[i].y);
if (q[i].k <= Check)
Tmp[1][++Cnt1] = q[i];
else
q[i].k -= Check, Tmp[0][++Cnt0] = q[i];
}
else {
if (q[i].k > Mid)
Seg.Update (1, q[i].x, q[i].y, 1ll), Tmp[1][++Cnt1] = q[i];
else
Tmp[0][++Cnt0] = q[i];
}
for (int i = 1; i <= Cnt0; i++)
q[l + i - 1] = Tmp[0][i];
for (int i = 1; i <= Cnt1; i++)
q[l + Cnt0 + i - 1] = Tmp[1][i];
Solve (l, l + Cnt0 - 1, L, Mid), Solve (l + Cnt0, r, Mid + 1, R);
}
int main () {
LL k;
n = Read (), m = Read ();
int p = 0, Tot = 0;
Seg.Make_Tree (1, 1, n);
for (int i = 1, Opt, x, y; i <= m; i++) {
Opt = Read (), x = Read (), y = Read (), k = Read_LL ();
if (Opt == 1)
q[++p] = Node (0, i, x, y, k);
else
q[++p] = Node (1, ++Tot, x, y, k);
}
Solve (1, p, -n, n);
for (int i = 1; i <= Tot; i++)
Print (Ans[i], '\n');
return 0;
}
最新文章
- Android 短信广播接收相关问题
- 使用NISI制作.Net程序服务安装包
- Javascript之登陆验证
- Java [leetcode 36]Valid Sudoku
- 【转】Android自定义控件
- 为什么JavaScript开发如此疯狂
- if....else
- 迷宫 洛谷 p1605
- 201521123085 《Java程序设计》第12周学习总结
- SQL Server安装【转载】
- c# 初识WPF
- Java反射获取字节码以及判断类型
- NOIP-接水问题
- C# 获取当前服务器运行程序的根目录
- 20155339 Exp5 MSF基础应用
- poj1142
- Mysql：This version of MySQL doesn’t yet support ‘LIMIT & IN/ALL/ANY/SOME 错误解决
- dbAdmin 不等于 root 集合中角色
- vs code 设置工作区背景图片方法
- 网页中引用优酷视频去广告自动播放代码[xyytit]