OI笔记 | 基础离线算法笔记
怎么说呢,上周五斟酌了一下,报了某谷的省选计划听听看。第一节说是讲了一些很基础的东西,但是我很多算法都没有学过阿!!果然我还是太菜了吗呜呜呜,感觉又回到刚开始学 OI 的时候大家都认为很基础的东西但我都不会那种奇特的感觉qwq。
另外,这节课讲的东西很杂。非要我能分类出一个专题来的话就是讲了两个离线算法就是 CDQ分治 和 整体二分。正好之前没学过,所以来写个笔记。
另外放了两题也是需要离线做的可爱题。
毕竟刚学这两玩意,所有写过的这两个算法的题都在这下面了,这篇文章肯定非常非常不能够说明这两个算法的各种用途,大概之后会记得补上!!
CDQ 分治
oi-wiki 上介绍 CDQ 分治可以解决的三类问题:
- 解决和点对有关的问题。
- 1D 动态规划的优化与转移。
- 通过 CDQ 分治,将一些动态问题转化为静态问题。
这里暂时不提到优化动态规划这部分,因为我不会。之后再补。
三维偏序
有 $ n $ 个元素,第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性,设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 $j$ 的数量。
对于 $ d \in [0, n) $,求 $ f(i) = d $ 的数量。
考虑 CDQ 分治:
我们先把元素按 $a_i$ 排序并对属性去重。
把区间分为 $[l,mid]$ 与 $[mid + 1,r]$,由于已经排序,则从左右两个区间分别任选出两个元素自然会满足 $a_i\leq a_j$。
然后对于 $b_i$ 的要求,用类似归并排序来统计。
对于 $c_i$ 的要求,用树状数组来统计。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
struct node {int a, b, c, cnt, ans;} a[MAX_N], q[MAX_N];
int ans[MAX_N];
bool cmpb(node x, node y) {
if(x.b == y.b) return x.c < y.c;
return x.b < y.b;
}
bool cmpa(node x, node y) {
if(x.a == y.a) return cmpb(x, y);
return x.a < y.a;
}
int lowbit(int x) {return x & -x;}
struct treearray {
int t[MAX_N], len;
treearray() {memset(t, 0, sizeof(t));}
void add(int pos, int x) {
for(int i = pos; i <= len; i += lowbit(i))
t[i] += x;
}
int query(int pos) {
int ans = 0;
for(int i = pos; i >= 1; i -= lowbit(i))
ans += t[i];
return ans;
}
} tree;
inline ll read() {...}
inline void write(ll x) {...}
void CDQ(int l, int r) {
if(l == r) return;
int mid = (l + r) >> 1;
CDQ(l, mid), CDQ(mid + 1, r);
sort(q + l, q + mid + 1, cmpb), sort(q + mid + 1, q + r + 1, cmpb);
int i = l, j = mid + 1;
for(; j <= r; j++) {
while(q[i].b <= q[j].b && i <= mid)
tree.add(q[i].c, q[i].cnt), i++;
q[j].ans += tree.query(q[j].c);
}
for(int k = l; k < i; k++)
tree.add(q[k].c, -q[k].cnt);
}
int main() {
int n = read(), k = read(), cnt = 0, m = 0;
tree.len = k;
for(int i = 1; i <= n; i++)
a[i].a = read(), a[i].b = read(), a[i].c = read();
sort(a + 1, a + n + 1, cmpa);
for(int i = 1; i <= n; i++) {
cnt++;
if(a[i].a != a[i + 1].a || a[i].b != a[i + 1].b || a[i].c != a[i + 1].c)
q[++m] = a[i], q[m].cnt = cnt, cnt = 0;
}
CDQ(1, m);
for(int i = 1; i <= m; i++)
ans[q[i].ans + q[i].cnt - 1] += q[i].cnt;
for(int i = 0; i < n; i++)
write(ans[i]), putchar('\n');
}
动态逆序对
对于序列 $a$,它的逆序对数定义为集合
\(\{(i,j)| i<j \wedge a_i > a_j \}\)
中的元素个数。
现在给出 $1\sim n$ 的一个排列,按照某种顺序依次删除 $m$ 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
设 $a_i$ 的删除时间为 $tim_i$,则逆序对只需要满足 $i<j \wedge a_i > a_j \wedge tim_i < tim_j$,所以转化为三维偏序。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
struct node {
int val, tim, ans;
node() {val = 0, tim = 0, ans = 0;}
} a[MAX_N];
int pos[MAX_N], n, m;
ll ans[MAX_N];
struct TreeArray {
int t[MAX_N];
int lowbit(int x) {return x & -x;}
void add(int i, int x) {for(; i <= n + 1; i += lowbit(i)) t[i] += x;}
ll query(int i) {int ret = 0; for(; i >= 1; i -= lowbit(i)) ret += t[i]; return ret;}
} tree;
inline ll read() {...}
char buf[100];
inline void write(ll x) {...}
inline bool cmpval(node x, node y) {return x.val < y.val;}
inline bool cmptim(node x, node y) {return x.tim < y.tim;}
// 原逆序对
ll solve() {
ll ret = 0;
for(int i = 1; i <= n; i++) {
ret += tree.query(n + 1) - tree.query(a[i].val);
tree.add(a[i].val, 1);
}
for(int i = 1; i <= n; i++)
tree.add(a[i].val, -1);
return ret;
}
void CDQ(int l, int r) {
if(l == r) return;
int mid = (l + r) >> 1;
CDQ(l, mid), CDQ(mid + 1, r);
int i = l, j = mid + 1;
for(; i <= mid; i++) {
while(j <= r && a[i].val > a[j].val)
tree.add(a[j].tim, 1), j++;
a[i].ans += tree.query(m + 1) - tree.query(a[i].tim);
}
for(int k = mid + 1; k < j; k++)
tree.add(a[k].tim, -1);
i = mid, j = r;
for(; j >= mid + 1; j--) {
while(i >= l && a[i].val > a[j].val)
tree.add(a[i].tim, 1), i--;
a[j].ans += tree.query(m + 1) - tree.query(a[j].tim);
}
for(int k = mid; k > i; k--)
tree.add(a[k].tim, -1);
sort(a + l, a + r + 1, cmpval);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) {
a[i].val = read();
pos[a[i].val] = i;
}
for(int i = 1; i <= m; i++) {
int x = read();
a[pos[x]].tim = i;
}
for(int i = 1; i <= n; i++)
if(!a[i].tim) a[i].tim = m + 1;
ll old = solve();
CDQ(1, n);
sort(a + 1, a + n + 1, cmptim);
for(int i = 1; i <= m; i++) {
write(old), putchar('\n');
old -= a[i].ans;
}
return 0;
}
整体二分
如果一个问题可以二分答案、且有多组询问、可离线,那么有时候可以将所有的询问一起二分。
具体做法是,猜测答案值域的 $mid$ 是定义域内所有问题的答案,并将询问依据它的答案与 $mid$ 的关系分成两部分进行分治。整体二分的复杂度是 $O(Q \log V)$,其中 $V$ 是二分答案的值域。有时候要套数据结构。
区间静态第 $k$ 小
我们先离散化,然后把数列的数值也加到询问数组里,方便遍历分治的区间内对询问有影响的数值,打个 $type$ 标记区分是询问还是数值即可。
每次猜测在当前分治的 $[ql,qr]$ 内询问的所有答案都为 $mid$,然后遍历一遍 $[ql,qr]$ 内的所有询问。
-
如果遇到一个数值 $a_i$ 且 $a_i \le mid$,把它的位置加入树状数组,并把它分到分治的左半部分;否则分到右半部分。
-
如果遇到一个询问 $(L,R)$,用树状数组查询当前 $[L,R]$ 内有多少个数,记为 $x$。如果 $x\le k$,把这个询问分到分治的左半部分;否则分到右半部分。
当前这一层执行完后,我们把树状数组清空,递归下去分治即可。
像二分一样,当答案的值域 $[l,r]$ 內只有一个元素时 (l==r
),递归结束,当前询问区间 $[ql,qr]$ 内的询问答案即为 $l$。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 10;
typedef long long ll;
typedef pair<int, int> pii;
struct que {
int l, r, k, id, type;
que(int _l = 0, int _r = 0, int _k = 0, int _id = 0, int _type = 0) : l(_l), r(_r), k(_k), id(_id), type(_type){}
};
int n, m, tot, cnt;
pii raw[MAX_N];
int a[MAX_N], val[MAX_N], ans[MAX_N];
que q[MAX_N << 1], q1[MAX_N << 1], q2[MAX_N << 1];
struct TreeArray {
int t[MAX_N];
TreeArray() {memset(t, 0, sizeof(t));}
int lowbit(int x) {return x & -x;}
void add(int i, int v) {for(; i <= n; i += lowbit(i)) t[i] += v;}
int query(int i) {int ret = 0; for(; i >= 1; i -= lowbit(i)) ret += t[i]; return ret;}
} tree;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
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(q[i].type == 2) ans[q[i].id] = l;
return;
}
int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
for(int i = ql; i <= qr; i++) {
if(q[i].type == 1) {
if(q[i].l <= mid) tree.add(q[i].id, 1), q1[++cnt1] = q[i];
else q2[++cnt2] = q[i];
}
else {
int x = tree.query(q[i].r) - tree.query(q[i].l - 1);
if(q[i].k <= x) q1[++cnt1] = q[i];
else q[i].k -= x, q2[++cnt2] = q[i];
}
}
for(int i = 1; i <= cnt1; i++)
if(q1[i].type == 1) tree.add(q1[i].id, -1);
for(int i = 1; i <= cnt1; i++)
q[i + ql - 1] = q1[i];
for(int i = 1; i <= cnt2; i++)
q[i + cnt1 + ql - 1] = q2[i];
solve(l, mid, ql, cnt1 + ql - 1);
solve(mid + 1, r, ql + cnt1, qr);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++)
raw[i].first = read(), raw[i].second = i;
sort(raw + 1, raw + n + 1);
for(int i = 1; i <= n; i++) {
if(raw[i] != raw[i - 1]) tot++;
a[raw[i].second] = tot;
val[tot] = raw[i].first;
}
for(int i = 1; i <= n; i++)
q[++cnt] = que(a[i], -1, -1, i, 1);
for(int i = 1; i <= m; i++)
q[++cnt].l = read(), q[cnt].r = read(), q[cnt].k = read(), q[cnt].id = i, q[cnt].type = 2;
solve(0, tot + 1, 1, cnt);
for(int i = 1; i <= m; i++)
write(val[ans[i]]), putchar('\n');
return 0;
}
[例题] MET-Meteors
有 $n$ 个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为 $m$ 份(第 $m$ 份和第 $1$ 份相邻),第 $i$ 份上有第 $a_i$ 个国家的太空站。
这个星球经常会下陨石雨。BIU 已经预测了接下来 $k$ 场陨石雨的情况。
BIU 的第 $i$ 个成员国希望能够收集 $p_i$ 单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。
对于这题,我们像上面一样进行分治。每次把 $[l,mid]$ 的陨石雨下下来,用树状数组维护每个位置接受到的陨石,然后枚举当前询问区间 $[ql,qr]$,用树状数组查询每个国家现在接受到了多少陨石。如果接受到的量小于期望,分到左边;否则分到右边。
细节略多,调了很久。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 6e5 + 10;
ll n, m, k;
struct TreeArray {
ll t[MAX_N];
TreeArray() {memset(t, 0, sizeof(t));}
int lowbit(int x) {return x & -x;}
void add(int i, ll v) {for(; i <= 2 * m; i += lowbit(i)) t[i] += v;}
ll query(int i) {ll ret = 0; for(; i >= 1; i -= lowbit(i)) ret += t[i]; return ret;}
} tree;
struct que {
ll pos, need, ans;
bool operator < (const que &t) const {return pos < t.pos;}
} q[MAX_N], q1[MAX_N], q2[MAX_N];
struct op {ll l, r, val;} ops[MAX_N];
vector<ll> bl[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void solve(int l, int r, int ql, int qr) {
if(ql > qr) return;
if(l == r) {
for(int i = ql; i <= qr; i++)
q[i].ans = l;
return;
}
int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
for(int i = l; i <= mid; i++)
tree.add(ops[i].l, ops[i].val), tree.add(ops[i].r + 1, -ops[i].val);
for(int i = ql; i <= qr; i++) {
ll sum = 0;
for(ll j : bl[q[i].pos]) {
sum += tree.query(j), sum += tree.query(j + m);
if(sum > q[i].need) break;
}
if(q[i].need <= sum) q1[++cnt1] = q[i];
else q[i].need -= sum, q2[++cnt2] = q[i];
}
for(int i = l; i <= mid; i++)
tree.add(ops[i].l, -ops[i].val), tree.add(ops[i].r + 1, ops[i].val);
for(int i = 1; i <= cnt1; i++)
q[i + ql - 1] = q1[i];
for(int i = 1; i <= cnt2; i++)
q[i + ql + cnt1 - 1] = q2[i];
solve(l, mid, ql, ql + cnt1 - 1);
solve(mid + 1, r, ql + cnt1, qr);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++)
bl[read()].push_back(i);
for(int i = 1; i <= n; i++)
q[i].need = read(), q[i].pos = i;
k = read();
for(int i = 1; i <= k; i++) {
ops[i].l = read(), ops[i].r = read(), ops[i].val = read();
if(ops[i].r < ops[i].l) ops[i].r += m;
}
solve(1, k + 1, 1, n);
sort(q + 1, q + n + 1);
for(int i = 1; i <= n; i++) {
if(q[i].ans == k + 1) puts("NIE");
else write(q[i].ans), putchar('\n');
}
return 0;
}
[例题] 视频倍增期
对于一个数列 $a$,每个时刻都有一次操作。操作有两种:
$\texttt{0 l r x}$:将区间 $[l,r]$ 的所有数加上 $x$。
$\texttt{1 i}$:找到 $a_i$ 第一次恰好达到 $\lceil \frac{a_i}{2}\rceil$ 的时刻与当前时刻的距离。
$1 \le n, m \le {10}^5$。
$1 \le x \le {10}^8$;
考虑这个问题如果只有一个位置,可以直接二分找到。
那么这题当然就可以整体二分,时间复杂度 $O(n\log^2 n)$。
注意一下 long long
。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int n, m;
struct que {
bool type;
int l, r, x, ans, tim; ll aim;
que(bool _type = 0, int _l = 0, int _r = 0, int _x = 0, int _ans = 0, int _tim = 0, ll _aim = 0) :
type(_type), l(_l), r(_r), x(_x), ans(_ans), tim(_tim), aim(_aim) {}
bool operator < (const que &t) const {return tim < t.tim;}
} q[MAX_N], q1[MAX_N], q2[MAX_N];
int ans[MAX_N];
struct BIT {
ll t[MAX_N];
BIT() {memset(t, 0, sizeof(t));}
inline int lowbit(int x) {return x & -x;}
inline void add(int i, int x) {
for(; i <= n; i += lowbit(i))
t[i] += x;
}
inline ll query(int i) {
ll ret = 0;
for(; i; i -= lowbit(i))
ret += t[i];
return ret;
}
} tree;
inline ll read() {...}
inline void write(ll x) {...}
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(q[i].type == 1) q[i].ans = q[i].aim ? l : 0;
return;
}
int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
for(int i = ql; i <= qr; i++) {
if(!q[i].type) {
if(q[i].tim <= mid) {
tree.add(q[i].l, q[i].x), tree.add(q[i].r + 1, -q[i].x);
q1[++cnt1] = q[i];
}
else q2[++cnt2] = q[i];
}
else {
ll now = tree.query(q[i].x);
if(q[i].aim <= now) q1[++cnt1] = q[i];
else q[i].aim -= now, q2[++cnt2] = q[i];
}
}
for(int i = 1; i <= cnt1; i++) {
q[ql + i - 1] = q1[i];
if(!q1[i].type) tree.add(q1[i].l, -q1[i].x), tree.add(q1[i].r + 1, q1[i].x);
}
for(int i = 1; i <= cnt2; i++)
q[ql + i + cnt1 - 1] = q2[i];
solve(l, mid, ql, ql + cnt1 - 1);
solve(mid + 1, r, ql + cnt1, qr);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++) {
int op = read();
if(!op) {
int l = read(), r = read(), x = read();
q[i] = que(op, l, r, x, -1, i, -1);
tree.add(l, x), tree.add(r + 1, -x);
}
else {
int k = read();
ll aim = tree.query(k);
aim = (aim / 2) + (aim % 2);
q[i] = que(op, -1, -1, k, -1, i, aim);
}
}
for(int i = 1; i <= m; i++)
if(!q[i].type) tree.add(q[i].l, -q[i].x), tree.add(q[i].r + 1, q[i].x);
solve(1, m + 1, 1, m);
sort(q + 1, q + m + 1);
for(int i = 1; i <= m; i++)
if(q[i].type) write(i - q[i].ans), putchar('\n');
}
带修区间第 $k$ 小
基本就是静态区间第 $k$ 小,把修改操作分割成了 删除原数 $\to$ 插入新数 的形式即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int n, m;
struct op {
int x, y, k, type, id;
op(int _x = 0, int _y = 0, int _k = 0, int _type = 0, int _id = 0) : x(_x), y(_y), k(_k), type(_type), id(_id) {}
} q[MAX_N << 2], q1[MAX_N << 2], q2[MAX_N << 2];
struct TreeArray {
int t[MAX_N];
TreeArray() {memset(t, 0, sizeof(t));}
int lowbit(int x) {return x & -x;}
void add(int i, int x) {for(; i <= n; i += lowbit(i)) t[i] += x;}
int query(int i) {int ret = 0; for(; i >= 1; i -= lowbit(i)) ret += t[i]; return ret;}
} tree;
int tot, a[MAX_N], ans[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline char read_char() {...}
void solve(int l, int r, int ql, int qr) {
if(l > r || ql > qr) return;
if(l == r) {
for(int i = ql; i <= qr; i++)
if(q[i].type == 1) ans[q[i].id] = l;
return;
}
int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
for(int i = ql; i <= qr; i++) {
if(q[i].type == 0) {
if(q[i].y <= mid) tree.add(q[i].x, q[i].k), q1[++cnt1] = q[i];
else q2[++cnt2] = q[i];
}
else {
int t = tree.query(q[i].y) - tree.query(q[i].x - 1);
if(q[i].k <= t) q1[++cnt1] = q[i];
else q[i].k -= t, q2[++cnt2] = q[i];
}
}
for(int i = 1; i <= cnt1; i++) {
q[ql + i - 1] = q1[i];
if(q1[i].type == 0) tree.add(q1[i].x, -q1[i].k);
}
for(int i = 1; i <= cnt2; i++)
q[ql + i + cnt1 - 1] = q2[i];
solve(l, mid, ql, ql + cnt1 - 1);
solve(mid + 1, r, ql + cnt1, qr);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
q[++tot] = op(i, a[i], 1, 0, -1);
}
for(int i = 1; i <= m; i++) {
char opt = read_char();
ans[i] = -1;
if(opt == 'Q') {
int x = read(), y = read(), k = read();
q[++tot] = op(x, y, k, 1, i);
}
else {
int x = read(), y = read();
q[++tot] = op(x, a[x], -1, 0, -1);
a[x] = y;
q[++tot] = op(x, a[x], 1, 0, -1);
}
}
solve(0, 1e9, 1, tot);
for(int i = 1; i <= m; i++)
if(ans[i] != -1) write(ans[i]), putchar('\n');
return 0;
}
洛谷 P3332 和这题很像阿,只不过把单点修改改为了区间修改。那么我们需要一个区间修改区间查询的数据结构,当然可以线段树,但是我搜了发现树状数组也可以做区间加区间查!!所以这里就不写整体二分的思路了就介绍一下这种树状数组。
让树状数组维护差分数组 $pre$ 的前缀和。所以如果想查原数组 $a$ 的前缀,朴素的做法是:
\[\sum\limits_{i=1}^p a_i = \sum\limits_{i=1}^p \sum_{j=1}^i pre_j\]然后我们化简一下这个和式,发现 $pre_1$ 贡献了 $p$ 次,$pre_2$ 贡献了 $(p-1)$ 次, 以此类推。所以可以展开和式:
\[\sum\limits_{i=1}^p \sum_{j=1}^i pre_j=\sum_{i=1}^p pre_i \cdot (p + 1 - i)=(p + 1)\cdot a_i - i\cdot a_i\]那么树状数组只要维护比平时多维护一个 $i\cdot a_i$ 即可。查询时查的就是上式。
struct TreeArray {
int t1[MAX_N], t2[MAX_N];
TreeArray() {memset(t1, 0, sizeof(t1)), memset(t2, 0, sizeof(t2));}
int lowbit(int i) {return i & -i;}
void add(int pos, int v) {
for(int i = pos; i <= n; i += lowbit(i))
t1[i] += v, t2[i] += pos * v;
}
int query(int pos) {
int ret = 0;
for(int i = pos; i >= 1; i -= lowbit(i))
ret += (pos + 1) * t1[i] - t2[i];
return ret;
}
} tree;
二维矩阵询问子矩阵第 $k$ 小
思路和一维的情况类似,把树状数组换成二维树状数组即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 610, MAX_Q = 6e4 + 10;
int n, q, tot, tmp;
int ans[MAX_Q];
struct node {
int x, y, val;
bool operator < (const node &t) const {return val < t.val;}
node(int _x = 0, int _y = 0, int _val = 0) : x(_x), y(_y), val(_val) {}
} a[MAX_N * MAX_N];
struct que {
int x, y, X, Y, k, id;
que(int _x = 0, int _y = 0, int _X = 0, int _Y = 0, int _k = 0, int _id = 0) : x(_x), y(_y), X(_X), Y(_Y), k(_k), id(_id) {}
} qs[MAX_Q], q1[MAX_Q], q2[MAX_Q];
struct TreeArray {
int t[MAX_N][MAX_N];
TreeArray() {memset(t, 0, sizeof(t));}
int lowbit(int x) {return x & -x;}
void add(int x, int y, int v) {
for(int i = x; i <= n; i += lowbit(i))
for(int j = y; j <= n; j += lowbit(j))
t[i][j] += v;
}
int query(int x, int y) {
int ret = 0;
for(int i = x; i >= 1; i -= lowbit(i))
for(int j = y; j >= 1; j -= lowbit(j))
ret += t[i][j];
return ret;
}
int sum(que p) {return query(p.X, p.Y) - query(p.x - 1, p.Y) - query(p.X, p.y - 1) + query(p.x - 1, p.y - 1);}
} tree;
inline ll read() {...}
inline void write(ll x) {...}
void solve(int l, int r, int ql, int qr) {
if(ql > qr) return;
if(l == r) {
for(int i = ql; i <= qr; i++)
ans[qs[i].id] = a[l].val;
return;
}
int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
for(int i = l; i <= mid; i++)
tree.add(a[i].x, a[i].y, 1);
for(int i = ql; i <= qr; i++) {
int t = tree.sum(qs[i]);
if(qs[i].k <= t) q1[++cnt1] = qs[i];
else qs[i].k -= t, q2[++cnt2] = qs[i];
}
for(int i = l; i <= mid; i++)
tree.add(a[i].x, a[i].y, -1);
for(int i = 1; i <= cnt1; i++)
qs[ql + i - 1] = q1[i];
for(int i = 1; i <= cnt2; i++)
qs[ql + cnt1 + i - 1] = q2[i];
solve(l, mid, ql, ql + cnt1 - 1);
solve(mid + 1, r, ql + cnt1, qr);
}
int main() {
n = read(), q = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
tmp = read(), a[++tot] = node(i, j, tmp);
for(int i = 1; i <= q; i++) {
int x = read(), y = read(), X = read(), Y = read(), k = read();
qs[i] = que(x, y, X, Y, k, i);
}
sort(a + 1, a + tot + 1);
solve(1, n * n, 1, q);
for(int i = 1; i <= q; i++)
write(ans[i]), putchar('\n');
return 0;
}
二维数点
给定平面上的 $n$ 个点的坐标 $(x_i,y_i)$。
有 $Q$ 次询问,每次给出 $x_1, y_1, x_2, y_2$,要求求出以 $(x_1,y_1)$ 为左下角, $(x_2,y_2)$ 为右上角的矩形范围内的点的个数。
题解
数据范围让我们不能直接用前缀和解决,但我们可以用前缀和的思想。考虑用 $f(u,v)$ 表示 $(0,0)$ 到 $(u,v)$ 内的点数,则一个询问 $(x_1, y_1, x_2, y_2)$ 可以拆成 $f(x_2, y_2) - f(x_1 - 1,y_2) - f(x_2, y_1 - 1) + f(x_1 -1, y_1 - 1)$。
那么可以把询问离线下来,按 $x$ 排序,用树状数组来维护 $y$ 这一维上点的个数。
具体来说,对于我们拆出来的单个询问 $f(u,v)$,我们直接把所有 $x_i\le u$ 的点的 $y_i$ 在树状数组里 $+1$,然后用 $v$ 查询树状数组的前缀和即为 $f(u,v)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_RANGE = 1e7 + 10, MAX_N = 5e5 + 10;
int n, m, tot, now = 1;
struct TreeArray {
int t[MAX_RANGE];
TreeArray() {memset(t, 0, sizeof(t));}
inline int lowbit(int x) {return x & -x;}
inline void add(int i, int v) {for(; i <= n; i += lowbit(i)) t[i] += v;}
inline int query(int i) {int ret = 0; for(; i >= 1; i -= lowbit(i)) ret += t[i]; return ret;}
} tree;
struct que {
int x, y, sgn, id;
que(int _x = 0, int _y = 0, int _sgn = 0, int _id = 0) : x(_x), y(_y), sgn(_sgn), id(_id) {}
bool operator < (const que &t) const {return x == t.x ? y < t.y : x < t.x;}
} q[MAX_N << 2];
pii pts[MAX_N];
int ans[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++)
pts[i].first = read() + 1, pts[i].second = read() + 1;
sort(pts + 1, pts + n + 1);
for(int i = 1; i <= m; i++) {
int x = read() + 1, y = read() + 1, X = read() + 1, Y = read() + 1;
q[++tot] = que(X, Y, 1, i);
q[++tot] = que(x - 1, Y, -1, i);
q[++tot] = que(X, y - 1, -1, i);
q[++tot] = que(x - 1, y - 1, 1, i);
}
sort(q + 1, q + tot + 1);
for(int i = 1; i <= tot; i++) {
while(now <= n && pts[now].first <= q[i].x)
tree.add(pts[now].second, 1), now++;
ans[q[i].id] += q[i].sgn * tree.query(q[i].y);
}
for(int i = 1; i <= m; i++)
write(ans[i]), putchar('\n');
return 0;
}
宝石之国
校内模拟赛的一题,不知道出处挂不了链接,可以自己查一下哪里可以提交
给定一个 $n$ 个数的数列 $a_1,a_2,\dots , a_n$,有 $m$ 次询问,每次给出两个端点 $l,r$,询问区间 $[l,r]$ 内两个相同元素的最短距离。对于 $a_x=a_y$,它们的距离定义为 $\lvert x-y\rvert$。
如果区间内不存在相同元素,输出 -1
。
$n,m\le2\times 10^5$
题解
把所有询问离线下来,按右端点排序。每次把 $pos\le q_i.r$ 的点纳入考虑范围内,即把距离更新到线段树的上一个位置处,然后用线段树维护区间最小值即可。
离散化一下比较好,因为这题没给 $a_i$ 的范围。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2e5 + 10, INF = (1 << 30);
int a[MAX_N], t[MAX_N], lstpos[MAX_N];
struct que {
int l, r, id, ans;
bool operator < (const que &t) const {return r < t.r;}
} q[MAX_N];
bool cmpid(que x, que y) {return x.id < y.id;}
int d[MAX_N << 2];
inline ll read() {...}
char buf[100];
inline void write(ll x) {...}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return (s + ((t - s) >> 1));}
inline void pu(int p) {d[p] = min(d[lc(p)], d[rc(p)]);}
void build_tree(int s, int t, int p) {
if(s == t) {
d[p] = INF;
return;
}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
pu(p);
}
void update(int s, int t, int p, int x, int v) {
if(s == t) {
d[p] = v;
return;
}
int m = mid(s, t);
if(x <= m) update(s, m, lc(p), x, v);
else update(m + 1, t, rc(p), x, v);
pu(p);
}
int query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
int m = mid(s, t), ret = INF;
if(l <= m) ret = min(ret, query(s, m, lc(p), l, r));
if(r > m) ret = min(ret, query(m + 1, t, rc(p), l, r));
return ret;
}
int main() {
int n = read(), m = read();
for(int i = 1; i <= n; i++)
t[i] = a[i] = read();
sort(t + 1, t + n + 1);
int tot = unique(t + 1, t + n + 1) - t - 1;
for(int i = 1; i <= n; i++)
a[i] = lower_bound(t + 1, t + tot + 1, a[i]) - t;
for(int i = 1; i <= m; i++) {
q[i].l = read(), q[i].r = read();
q[i].id = i;
}
sort(q + 1, q + m + 1);
build_tree(1, n, 1);
int now = 1;
for(int i = 1; i <= m; i++) {
while(now <= q[i].r) {
if(lstpos[a[now]]) update(1, n, 1, lstpos[a[now]], now - lstpos[a[now]]);
lstpos[a[now]] = now;
now++;
}
q[i].ans = query(1, n, 1, q[i].l, q[i].r);
if(q[i].ans == INF) q[i].ans = -1;
}
sort(q + 1, q + m + 1, cmpid);
for(int i = 1; i <= m; i++)
write(q[i].ans), putchar('\n');
return 0;
}
♥