专栏文章

CF2147F Exchange Queries

EEuphoricStar
CF2147F题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minth98c
此快照首次捕获于
2025/12/02 08:05
3 个月前
此快照最后确认于
2025/12/02 08:05
3 个月前
查看原文
以下是场上 16min 速通的做法。
若 ii 可以买到 jj 就连一条 i→ji \to j 的有向边，相当于求可达点对数量。发现这个图是竞赛图加上若干条边，所以缩点之后一定是一条链。
令 api=sia_{p_i} = s_i。设 max⁡j=1iaj=i\max\limits_{j = 1}^i a_j = i 的所有位置为 b1,b2,…,bkb_1, b_2, \ldots, b_k（设 b0=0b_0 = 0），那么一个强连通分量即为 [bi−1+1,bi][b_{i - 1} + 1, b_i]，它可以到达 [1,bi][1, b_i] 中的所有点。
所以答案即为：
∑i=1kbi×(bi−bi−1)=∑i=1kbi2−∑i=2kbi−1×bi\sum\limits_{i = 1}^k b_i \times (b_i - b_{i - 1}) = \sum\limits_{i = 1}^k b_i^2 - \sum\limits_{i = 2}^k b_{i - 1} \times b_i
要求支持交换 aa 的两个元素，然后查询上述式子。
考虑线段树维护，对于每个 ii，维护 ii 减去前缀 [1,i][1, i] 中 ≤i\le i 的 aja_j 的个数，容易发现这个值一定 ≥0\ge 0。那么一个 aja_j 会对 i∈[max⁡(j,aj),n]i \in [\max(j, a_j), n] 有 11 的贡献。
问题变成，区间（其实是后缀）±1\pm 1，设值为 00（即最小值）的所有位置为 b1,b2,…,bkb_1, b_2, \ldots, b_k，求 ∑i=1kbi2−∑i=2kbi−1×bi\sum\limits_{i = 1}^k b_i^2 - \sum\limits_{i = 2}^k b_{i - 1} \times b_i。
容易线段树维护。线段树每个结点维护这个区间最靠左、最靠右的区间最小值，和当前区间的答案。合并是容易的。
时间复杂度 O((n+m)log⁡n)O((n + m) \log n)。
CPP
// Problem: F. Exchange Queries
// Contest: Codeforces - Codeforces Global Round 29 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2147/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 100100;

int n, m, a[maxn], b[maxn], p[maxn], ip[maxn];

struct node {
	int mn, l, r;
	ll s;
};

inline node operator + (const node &a, const node &b) {
	node res;
	res.mn = min(a.mn, b.mn);
	if (a.mn < b.mn) {
		res.l = a.l;
		res.r = a.r;
		res.s = a.s;
	} else if (a.mn > b.mn) {
		res.l = b.l;
		res.r = b.r;
		res.s = b.s;
	} else {
		res.l = a.l;
		res.r = b.r;
		res.s = a.s + b.s - 1LL * a.r * b.l;
	}
	return res;
}

namespace SGT {
	node a[maxn << 2];
	int tag[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = a[x << 1] + a[x << 1 | 1];
	}
	
	inline void pushtag(int x, int y) {
		a[x].mn += y;
		tag[x] += y;
	}
	
	inline void pushdown(int x) {
		if (!tag[x]) {
			return;
		}
		pushtag(x << 1, tag[x]);
		pushtag(x << 1 | 1, tag[x]);
		tag[x] = 0;
	}
	
	void build(int rt, int l, int r) {
		tag[rt] = 0;
		if (l == r) {
			a[rt].mn = a[rt].l = a[rt].r = l;
			a[rt].s = 1LL * l * l;
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	
	void update(int rt, int l, int r, int ql, int qr, int x) {
		if (ql > qr) {
			return;
		}
		if (ql <= l && r <= qr) {
			pushtag(rt, x);
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
		p[a[i]] = b[i];
		ip[b[i]] = a[i];
	}
	SGT::build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		SGT::update(1, 1, n, max(i, p[i]), n, -1);
	}
	while (m--) {
		int o, i, j;
		scanf("%d%d%d", &o, &i, &j);
		if (o == 1) {
			swap(a[i], a[j]);
			SGT::update(1, 1, n, max(a[i], p[a[i]]), n, 1);
			SGT::update(1, 1, n, max(a[j], p[a[j]]), n, 1);
			swap(p[a[i]], p[a[j]]);
			SGT::update(1, 1, n, max(a[i], p[a[i]]), n, -1);
			SGT::update(1, 1, n, max(a[j], p[a[j]]), n, -1);
			swap(ip[p[a[i]]], ip[p[a[j]]]);
		} else {
			swap(b[i], b[j]);
			swap(ip[b[i]], ip[b[j]]);
			int x = ip[b[i]], y = ip[b[j]];
			SGT::update(1, 1, n, max(x, p[x]), n, 1);
			SGT::update(1, 1, n, max(y, p[y]), n, 1);
			swap(p[ip[b[i]]], p[ip[b[j]]]);
			SGT::update(1, 1, n, max(x, p[x]), n, -1);
			SGT::update(1, 1, n, max(y, p[y]), n, -1);
		}
		printf("%lld\n", SGT::a[1].s);
	}
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...