• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# HDU7107. GCD on Sequence 利用线段树计数

4小时前 1次浏览

## HDU7107. GCD on Sequenc++e

### 代码：

``````#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define now nodes[rt]
#define ls nodes[rt << 1]
#define rs nodes[rt << 1 | 1]
typedef long long Lint;
const int maxn = 1e5 + 10;
int n;
int a[maxn], pos[maxn];
struct Node {
Lint sum;
Lint r_val;
Lint tag;
int l, r;
};
struct Seg {
Node nodes[maxn << 2];

void update_node(int rt, Lint tag) {
now.sum = tag * (now.r - now.l + 1);
now.r_val = tag;
now.tag = tag;
}

void pushup(int rt) {
now.sum = ls.sum + rs.sum;
now.r_val = rs.r_val;
}

void pushdown(int rt) {
if (now.tag) {
update_node(rt << 1, now.tag);
update_node(rt << 1 | 1, now.tag);
now.tag = 0;
}
}

void build(int rt, int l, int r, Lint val) {
now.l = l, now.r = r;
now.tag = 0;
if (l == r) {
now.sum = val;
now.r_val = val;
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid, val);
build(rt << 1 | 1, mid + 1, r, val);
pushup(rt);
}

// 用val覆盖区间[L, R]
void update(int rt, int L, int R, Lint val) {
if (L <= now.l && now.r <= R) {
update_node(rt, val);
return;
}
pushdown(rt);
if (L <= ls.r)
update(rt << 1, L, R, val);
if (R >= rs.l)
update(rt << 1 | 1, L, R, val);
pushup(rt);
}

// 区间[1,n]的和
Lint query_sum() { return nodes[1].sum; }

// 寻找第一个大于val的位置
int query_pos(int rt, Lint val) {
if (now.l == now.r) {
return now.l;
}
if (ls.r_val > val) {
return query_pos(rt << 1, val);
} else {
return query_pos(rt << 1 | 1, val);
}
}
} seg;

// g[i]存<=n的i的倍数的位置
vector<int> g[maxn];

Lint ans[maxn];
void solve() {
seg.build(1, 1, n, n);
for (int i = 1; i <= n; i++) {
g[i].clear();
}
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
g[i].push_back(pos[j]);
}
}
for (int i = 1; i <= n; i++) {
sort(g[i].begin(), g[i].end());
}
// 从大到小枚举val
for (int i = n; i >= 1; i--) {
ans[i] = 0;
for (int j = 0; j < g[i].size() - 1; j++) {
Lint o_sum = seg.query_sum();
if (seg.nodes[1].r_val > g[i][j + 1] - 1) {
int pos = seg.query_pos(1, g[i][j + 1] - 1);
if (pos <= g[i][j])
seg.update(1, pos, g[i][j], g[i][j + 1] - 1);
}
Lint n_sum = seg.query_sum();
ans[i] += o_sum - n_sum;
}
}
for (int i = 1; i <= n; i++) {
printf("%lldn", ans[i]);
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
pos[a[i]] = i;
}
solve();
}
return 0;
}
``````