百度科学家(可持久化线段树+Tarjan)

描述

传送门:2018 计蒜之道 初赛 第一场 - Problem D

百度有一位非常有名的大科学家,这位大科学家有很多藏书。

大科学家有一个图书馆,所以放书的容量也随之增加了,图书馆可以看成一个长度为 $N$ 的序列,一开始里面放着 $N$ 本书,每本书都记载了一个特定元素的信息,书中的元素各不相同。

大科学家会先进行若干次研究,最后进行一次科学实验,这次实验需要选取一些元素放在一起来进行。每次研究,大科学家会从图书馆中的某些位置抽出一些书来看,然后得出“如果 $x$ 位置上的书对应的元素被拿来做实验了,那么区间 $[l,r]$ 位置上的书对应的元素也必须拿来做实验,否则会爆炸”这样的结论。

大科学家有不止 $N$ 本书(也就是说世界上有不止 $N$ 种元素),但是他自己没时间给图书馆换书,所以他雇了一个实习生,这个实习生会时不时地拿出一本从来没被放入图书馆的书,然后替换掉图书馆中某个位置原来的书。所以对于大科学家得到的两次看似一样的研究结果,可能由于图书馆中的书被换了,它们的实质内容可能不一样。

每本书还记载着对应元素的非负污染值,大科学家希望在完成一次科学实验的前提下(不能不选任何元素),这次实验的总污染值最小。作为一个旁观者,你能看到科学家做的所有研究结果以及实习生换书的顺序,然后你需要告诉大科学家,这个最小总污染值是多少。

听说马上要科技胜利了,大科学家精力充沛,再也不用担心他的实验结论受到限制了。

输入格式

第一行一个正整数 $N$,代表图书馆的容量。

接下来一行 $N$ 个数,第 $i$ 个非负整数 $a_i$​ 代表最开始图书馆中第 $i$ 本书所描述的元素的污染值。

接下来一行一个整数 $M$,代表事件的总数。

接下来 $M$ 行,每行代表一个事件:

若为 $0$ $x$ $y$,代表实习生拿了一本新书替换了 $x$ 位置的书,新书对应元素的污染值为 $y$。

若为 $1$ $x$ $l$ $r$,代表大科学家得到了新的结果,如果 $x$ 位置的书对应的元素加入了实验,那么 $[l,r]$ 区间内的书对应的元素都必须拿来做实验。

保证大科学家的书籍总数 ($N+$ 新书数量 ) $\le 10^5$)。

每个元素的污染值 $0\le (a_i,y) \le 10^9$。

保证 $1 \le x \le N$, $1 \le l \le r \le N$,$M \le 10^5$。

输出格式

输出一个整数,代表最小总污染值。

样例输入

1
2
3
4
5
6
7
5
1 10 100 1000 10000
4
1 1 3 4
1 3 5 5
0 3 0
1 3 1 2

样例输出

1
10

样例解释

一开始书架上有 $5$ 本书,我们记这些元素的编号顺次为 $1,2,3,4,5$,他们的污染值分别为 $1,10,100,1000,10000$。

一共有 $4$ 个事件:

  1. 大科学家发现,选了元素 $1$ 就必须选元素 $3,4$。
  2. 大科学家发现,选了元素 $3$ 就必须选元素 $5$。
  3. 实习生拿了一本新书,我们记这个新元素的编号为 $6$,他的污染值为 $0$,替换掉现在书架上的第 $3$ 本书,现在书架上的 $5$ 本书对应元素为 $1,2,6,4,5$。
  4. 大科学家发现,选了元素 $6$(因为它在位置 $3$ 上)就必须选元素 $1,2$。

于是在所有可能的方案中,单选一个元素 $2$ 来做实验是总污染值最小的,因为如果选择元素 $1$ 或元素 $6$,都存在一些绑定关系使得总污染值不可能比 $10$ 更小。

思路

  • 简单:直接根据依赖关系建图,传递闭包即可。
  • 中等:直接根据依赖关系建图,强连通分量缩点后,选择出度为零的点中权值最小的即可。

  • 显然,在这题的数据范围下,图是没法暴力建的。如果还要建图,就要用数据结构优化。
  • 先考虑没有新书的情况,我们先建立一个线段树,父亲向儿子连边;然后在连依赖关系的时候,就是线段树的一个区间查询。
  • 如果有新书,那么前面的依赖关系不变,所以容易想到可持久化。
  • 建完图,就和中等是一个题了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int N = 1 << 17;
vector<int> G[N << 5];

int val[N << 5], lson[N << 5], rson[N << 5];
int sz;
int id[N];

void build(int l, int r, int& o)
{
o = ++sz;
if (l == r)
{
id[l] = o;
cin >> val[o];
return;
}
int m = l + r >> 1;
build(l, m, lson[o]), G[o].push_back(lson[o]);
build(m + 1, r, rson[o]), G[o].push_back(rson[o]);
}

void update(int p, int v, int l, int r, int& o, int k)
{
o = ++sz;
val[o] = val[k], lson[o] = lson[k], rson[o] = rson[k];
if (l == r)
{
id[l] = o;
val[o] = v;
return;
}
int m = l + r >> 1;
if (p <= m)
update(p, v, l, m, lson[o], lson[k]);
else
update(p, v, m + 1, r, rson[o], rson[k]);
G[o].push_back(lson[o]), G[o].push_back(rson[o]);
}

void query(int p, int L, int R, int l, int r, int o)
{
if (L <= l && r <= R)
{
G[p].push_back(o);
return;
}
int m = l + r >> 1;
if (L <= m) query(p, L, R, l, m, lson[o]);
if (m < R) query(p, L, R, m + 1, r, rson[o]);
}

int pre[N << 5], lowlink[N << 5], sccno[N << 5], dfs_clock, scc_cnt;
stack<int> S;
void dfs(int u)
{
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
for (auto& v : G[u])
{
if (!pre[v])
{
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if (!sccno[v])
lowlink[u] = min(lowlink[u], pre[v]);
}
if (lowlink[u] == pre[u])
{
scc_cnt++;
for (;;)
{
int x = S.top();
S.pop();
sccno[x] = scc_cnt;
if (x == u) break;
}
}
}
void find_scc(int n)
{
dfs_clock = 0, scc_cnt = 0;
clr(sccno, 0), clr(pre, 0);
for (int i = 1; i <= n; i++)
if (!pre[i]) dfs(i);
}

ll f[N << 5];

void debug()
{
for (int u = 1; u <= sz; u++) {
for (auto& v : G[u])
cerr << "(" << u << "," << v << ")";
cerr << endl;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
fastin int n, m, rt;
cin >> n;
build(1, n, rt);
cin >> m;
while (m--)
{
static int op;
cin >> op;
if (op == 1)
{
static int x, l, r;
cin >> x >> l >> r;
query(id[x], l, r, 1, n, rt);
}
else
{
static int x, y;
cin >> x >> y;
update(x, y, 1, n, rt, rt);
}
}
// debug();
find_scc(sz);
for (int i = 1; i <= sz; i++) f[sccno[i]] += val[i];
for (int u = 1; u <= sz; u++)
for (auto& v : G[u])
if (sccno[u] != sccno[v]) f[sccno[u]] = 1e18;
ll ans = 1e18;
for (int i = 1; i <= scc_cnt; i++)
ans = min(ans, f[i]);
cout << ans << endl;
return 0;
}
捐助作者
0%