OI笔记 | 基础离线算法笔记

怎么说呢,上周五斟酌了一下,报了某谷的省选计划听听看。第一节说是讲了一些很基础的东西,但是我很多算法都没有学过阿!!果然我还是太菜了吗呜呜呜,感觉又回到刚开始学 OI 的时候大家都认为很基础的东西但我都不会那种奇特的感觉qwq。

另外,这节课讲的东西很杂。非要我能分类出一个专题来的话就是讲了两个离线算法就是 CDQ分治整体二分。正好之前没学过,所以来写个笔记。

另外放了两题也是需要离线做的可爱题。

毕竟刚学这两玩意,所有写过的这两个算法的题都在这下面了,这篇文章肯定非常非常不能够说明这两个算法的各种用途,大概之后会记得补上!!

CDQ 分治

oi-wiki 上介绍 CDQ 分治可以解决的三类问题:

  1. 解决和点对有关的问题。
  2. 1D 动态规划的优化与转移。
  3. 通过 CDQ 分治,将一些动态问题转化为静态问题。

这里暂时不提到优化动态规划这部分,因为我不会。之后再补。

三维偏序

洛谷 P3810

有 $ 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');
}

动态逆序对

洛谷 P3157

对于序列 $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$ 小

洛谷 P3834

我们先离散化,然后把数列的数值也加到询问数组里,方便遍历分治的区间内对询问有影响的数值,打个 $type$ 标记区分是询问还是数值即可。

每次猜测在当前分治的 $[ql,qr]$ 内询问的所有答案都为 $mid$,然后遍历一遍 $[ql,qr]$ 内的所有询问。

  1. 如果遇到一个数值 $a_i$ 且 $a_i \le mid$,把它的位置加入树状数组,并把它分到分治的左半部分;否则分到右半部分。

  2. 如果遇到一个询问 $(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

洛谷 P3527

有 $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;
}

[例题] 视频倍增期

洛谷 P7602

对于一个数列 $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$ 小

洛谷 P2617

基本就是静态区间第 $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$ 小

洛谷 P1527

思路和一维的情况类似,把树状数组换成二维树状数组即可。

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

Joy © 2023 Powered by Jekyll and Theme by solid

今日诗词API Valine 评论管理 Github