【无码专区13】最小公倍数（线段树）

因为只有std，没有自我实现，所以是无码专区

主要是为了训练思维能力

my idea顾名思义，记录了我的整个思维过程，以及自己部分实现细节口胡，还有期望分数

solution才是dls正解，但是因为只有潦草几句，所以大部分会有我自己基于正解上面的算法实现过程，可能选择的算法跟std中dls的实现不太一样。

std可能也会带有博主自己的注释。

---

problem

有 $n$ 个数，其表示为 $2^{a_i}\cdot 3^{b_i}$，给定 $a_i,b_i$。

对于所有的非空子集，求出它们的最小公倍数，并求和。

答案对 $1e9+7$ 取模。

测试点编号	$n\le$	$a_i,b_i\le$
$1-2$	$20$	$10^9$
$3-4$	$10^3$	$10^9$
$5-6$	$10^5$	$10^3$
$7-10$	$10^5$	$10^9$

---

my idea

读完题就直接思考具有特殊性质的数据点，因为往往这种数据点的算法就是正解最朴素的原始样子。有价值的题都会这么设计部分分。某些毒瘤题呃呃呃

$n\le 10^3$ 应该是与 $n^2$ 挂钩的算法。

大概是枚举子集的最小值和最大值，强制入选，然后二维数点中间所有可以选择的数。为了避免算重，相同值的点还得强制规定一个大小，比如编号。

$a_i,b_i\le 10^3$ 本质上与上面差不多。

只不过是从因子的幂次角度入手枚举。

枚举最大值的 $a,b$，二维数点所有 $a_i\le a,b_i\le b$ 的点，考虑是否选择。

同样为了避免算重，也得规定第三排序法则。

以上只是粗略的想法，并未细想。因为这个时候发现上面的做法其实是可以做正解的。

$2^a,3^b$ 是相互独立的，可分开计算。

将所有数按 $a$ 幂次大小升序排序后。

考虑枚举第 $i$ 个数的 $a$ 作为最小公倍数的 $a$。

显然，子集内的其余元素只能从 $1\le j<i$ 里面选。

对 $b$ 建立权值线段树，维护元素个数。

为了去重，强制枚举的数必选，那么最小公倍数 $b$ 的至少是 $b_i$。

直接线段树上查一段区间作为作为最小公倍数 $b$ 的答案。

具体而言：

线段树的叶子节点 $x$ 维护的是 $b_j\le x,1\le j<i$ 的 $j$ 的个数，假设为 $c$ 个。

一个叶子节点如果是最后选的子集数的最小公倍数的 $b$ 的话。

那么可能的子集为 $2^{c-1}$ 个，$-1$ 是因为必须要求 $b_j=x$ 的 $j$ 中强制被选一个，这样才会有 $b_j$，否则会假掉。

一个点对答案的贡献就是 $2^{c-1}\ast x$，此时必须保证有至少一个 $b_j=x$ 才行。

所以一个点还要维护一个标记 $f$，表示是否有至少一个 $j$ 满足 $b_j=x$。

那么一个点对答案的贡献应该是 $2^{c-1}\ast x\ast f$。

对于枚举的 $i$ 而言，算出来的贡献为 $2^{a_i}\ast$ 线段树查询区间 $[b_j,MaxB]$。

注意到，这个形式意味着还要对 $b$ 进行离散化处理。

因为 $i$ 能让 $b_i$ 的线段树对应节点 $f=1$，而这之前可能是 $f=0$。

所以要先修改再查询。

修改根据节点维护信息，对应的应是区间修改 $[1,b_i]$，且特殊的， $b_i$ 的 $f$ 要置为 $1$。

所以可以拆成区间修改 $[1,b_i)$ 和单点修改 $b_i$。

懒标记一旦增加，相当于是多了一个个数，幂次 $+1$，拆出来变成外部 $\times 2$。

即 $2^{lazy}\cdot (2^{c_1}\ast x_1\ast f_1+2^{c_2}\ast x_2\ast f_2+...+)$。

时间复杂度为 $O(n\log n)$。

---

solution

首先不妨设 $a_i,b_i$ 两两不同。

考虑枚举集合中 $b_i$ 最大的元素，将所有 $b_j<b_i$ 的元素按 $a_j$ 从小到大排序。

不妨记作 $a_1^{\prime },a_2^{\prime },...,a_{i-1}^{\prime }$，那么会有 $2^{i-1}$ 个子集，最大值是 $a_{i-1}^{\prime }$。

考虑将 $a_i$ 加入后，所有最大值 $<a_i$ 的子集，最大值都变成了 $a_i$，剩下的子集不变。

将 $a_i$ 加入到上面的有序序列后，所有比 $a_i$ 大的元素排名都会 $+1$，对应的子集个数会翻倍。

问题等价于区间乘 $2$ 以及区间求和，线段树维护。

就是my idea类似的思想，yeah我做出来了！

---

std

#include <bits/stdc++.h>
#define ls(x) (x << 1)
#define rs(x) ((x << 1) | 1)
#define LL long long
using namespace std;
const int maxn = 100010;
const LL mod = 1000000007;

struct node {
	int x, y, rank;
};

bool cmp1(node x, node y) {
	return x.x == y.x ? x.y < y.y : x.x < y.x;
}

bool cmp2(node x, node y) {
	return x.y == y.y ? x.x < y.x : x.y < y.y;
}
node a[maxn];

struct SegementTree {
	LL sum, cnt, lz;
};
SegementTree tr[maxn * 4];

LL qpow(LL x, LL y) {
	LL ans = 1;
	for (; y; y >>= 1) {
		if (y & 1)
			ans = (ans * x) % mod;
		x = (x * x) % mod;
	}
	return ans;
}

void pushup(int x) {
	tr[x].sum = (tr[ls(x)].sum + tr[rs(x)].sum) % mod;
	tr[x].cnt = (tr[ls(x)].cnt + tr[rs(x)].cnt) % mod;
}

void maintain(int x, int y) {
	tr[x].sum = (tr[x].sum * qpow(2, y)) % mod;
	tr[x].lz += y;
}

void pushdown(int x) {
	if (tr[x].lz) {
		if (tr[ls(x)].cnt)
			maintain(ls(x), tr[x].lz);
		if (tr[rs(x)].cnt)
			maintain(rs(x), tr[x].lz);
		tr[x].lz = 0;
	}
}

void build(int x, int l, int r) {
	if (l == r) {
		tr[x].sum = tr[x].cnt = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(x), l, mid);
	build(rs(x), mid + 1, r);
	pushup(x);
}

void update_cnt(int x, int l, int r, int pos, int y, int z) {
	if (l == r) {
		tr[x].cnt = 1;
		tr[x].sum = (qpow(2, y) * qpow(2, z)) % mod;
		return;
	}
	pushdown(x);
	int mid = (l + r) >> 1;
	if (pos <= mid)
		update_cnt(ls(x), l, mid, pos, y, z);
	else
		update_cnt(rs(x), mid + 1, r, pos, y, z);
	pushup(x);
}

void update_sum(int x, int l, int r, int ql, int qr) {
	if (l >= ql && r <= qr) {
		tr[x].lz++;
		tr[x].sum = (tr[x].sum * 2) % mod;
		return;
	}
	pushdown(x);
	int mid = (l + r) >> 1;
	if (ql <= mid)
		update_sum(ls(x), l, mid, ql, qr);
	if (qr > mid)
		update_sum(rs(x), mid + 1, r, ql, qr);
	pushup(x);
}

LL query_cnt(int x, int l, int r, int ql, int qr) {
	if (l >= ql && r <= qr) {
		return tr[x].cnt;
	}
	int mid = (l + r) >> 1;
	pushdown(x);
	LL ans = 0;
	if (ql <= mid)
		ans += query_cnt(ls(x), l, mid, ql, qr);
	if (qr > mid)
		ans += query_cnt(rs(x), mid + 1, r, ql, qr);
	return ans;
}

LL query_sum(int x, int l, int r, int ql, int qr) {
	if (l >= ql && r <= qr) {
		return tr[x].sum;
	}
	int mid = (l + r) >> 1;
	LL ans = 0;
	pushdown(x);
	if (ql <= mid)
		ans += query_sum(ls(x), l, mid, ql, qr);
	if (qr > mid)
		ans += query_sum(rs(x), mid + 1, r, ql, qr);
	return ans % mod;
}

int main() {
	freopen("", "r", stdin);
	freopen("", "w", stdout);
	int n;
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &a[i].x, &a[i].y);
		}
		sort(a + 1, a + 1 + n, cmp1);
		for (int i = 1; i <= n; i++) {
			a[i].rank = i;
		}
		sort(a + 1, a + 1 + n, cmp2);
		build(1, 1, n);
		LL ans = 0;
		for (int i = 1; i <= n; i++) {
			LL tmp = query_cnt(1, 1, n, 1, a[i].rank);
			update_cnt(1, 1, n, a[i].rank, tmp, a[i].x);
			ans = (ans + query_sum(1, 1, n, a[i].rank, n) * qpow(3, a[i].y) % mod) % mod;
			if (a[i].rank != n)
				update_sum(1, 1, n, a[i].rank + 1, n);
		}
		printf("%lld\n", ans);
	}
}