LOJ516 DP一般看规律 离散化+乱搞

给定一个长度为 n 的序列 a,一共有 m 次操作,
每次操作给定 x, y,使序列中所有 x 变成 y,问每次操作后,值相等的位置的最小下标差是多少。若序列中无相同的数,则输出2147483647。

n, m <= 1e5, 所有数在int范围内

题目链接

对于这道题,ans明显是只减不增的。而且对ans造成的影响必然是x变成y后使得y的距离变小了。试图从这里着手。

我们需要一种数据结构来将x, y合并,并求出下标的最小差。很显然不可能int范围内所有值都开一个这种数据结构,必定会空间爆炸。由于此题数值的大小和具体值不对答案产生影响,所以可以直接离散化,然后进行操作。我比较懒,就直接用set来水。每次操作后暴力判断最小的下标差

然后我就T了。

WA T 的一声哭了出来

发现读入数据很多,输出数据也很多,所以加一个快读快输试试。

然后只快了300ms,又T了。

之前说了,ans是只减不增的,所以当ans为1的时候后面的答案一定都为1了,不用进行合并,暴力判断这种很费时间的操作了。并且这道题其实答案很容易变成1,我也不知道为什么。

然后就A过去了。跑的比我想象的快多了

还顺便上了统计第一页,好开心

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
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>

//懒的加fread,否则可能更快
void input(int &var) {
int ope = 1;
var = 0;
char ch = getchar();
while((ch < '0' || '9' < ch) && ch != '-') ch = getchar();
if(ch == '-') {
ope = -1;
ch = getchar();
}
while('0' <= ch && ch <= '9') {
var = var * 10 + ch - '0';
ch = getchar();
}
var *= ope;
return;
}

//懒的加fwrite
void output(int num) {
if(num < 0) {
putchar('-');
num = -num;
} else if(num == 0) {
putchar('0');
return;
}
if(num > 9) {
output(num / 10);
}
putchar(num % 10 + '0');
return;
}

const int MAX_LEN = 100000;
const int MAX_ASK_NUM = 100000;

struct Query {
int before;
int after;
} query[MAX_ASK_NUM];

int num;
int askn;

int arr[MAX_LEN + 1];
std::vector<int> vec;

std::set<int> tree[MAX_LEN + (MAX_ASK_NUM << 1) + 5];

void init();
void solve();

int main() {
init();
solve();
return 0;
}

int getId(int key) {
return std::lower_bound(vec.begin(), vec.end(), key) - vec.begin();
}

void init() {
input(num);
input(askn);
// scanf("%d%d", &num, &askn);
for(int i = 1; i <= num; ++i) {
input(arr[i]);
// scanf("%d", arr + i);
vec.push_back(arr[i]);
}

for(int i = 1; i <= askn; ++i) {
input(query[i].before);
input(query[i].after);
// scanf("%d%d", &query[i].before, &query[i].after);
vec.push_back(query[i].before);
vec.push_back(query[i].after);
}

sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

for(int i = 1; i <= num; ++i) {
arr[i] = getId(arr[i]);
tree[arr[i]].insert(i);
}

for(int i = 1; i <= askn; ++i) {
query[i].before = getId(query[i].before);
query[i].after = getId(query[i].after);
}

return;
}

void solve() {
int ans = 0x7fffffff;
int loc = askn + 1;
for(int i = 1; i <= askn; ++i) {
tree[query[i].after].insert(tree[query[i].before].begin(), tree[query[i].before].end());
tree[query[i].before].clear();

std::set<int>::iterator i1 = tree[query[i].after].begin(), i2 = tree[query[i].after].begin();
if(i2 != tree[query[i].after].end()) {
++i2;
while(i2 != tree[query[i].after].end()) {
ans = std::min(ans, *i2 - *i1);
++i1;
++i2;
}
}
if(ans == 1) {
loc = i;
break;
}
output(ans);
putchar('\n');
// printf("%d\n", ans);
}
while(loc++ <= askn) {
putchar('1');
putchar('\n');
}
return;
}