翻车笔记_ TJOI2013 最长上升子序列 [DP, 树状数组]

有的时候确实需要确定最终的状态, 以计算出插入过程中状态的关系

懵逼的 题目

传送至 BZOJ

扯淡的 题解

我不就是想做个DP我容易嘛TUT

看到题没有任何头绪, 只能看看数据范围觉得应该是个$n\lg n$的LIS, 看到题解上写着

因为是从1到n插入的, 所以后插入的数不会对之前的LIS产生影响

也并没有联想到什么解法, 只能想到每插入一个数, 就从之前的f[]中二分一个可能的答案然后接上, 最后因为不能判断二分出的答案是否在插入位置的前面, 最后也放弃了…
然后看(参悟)了看(参悟)大佬的博客才知道 [不会对之后的答案产生影响] 的意思就是可以只求最后完成序列的LIS啊:

对于一个数a[i], 在i之前, 且比a[i]小的数(即满足二分条件的数), 一定在a[i]出现前就被插入了, 所以只要最后求一遍LIS就好了

然后我就高高兴兴想去写sb LIS, 然后发现一个问题: 插入完的序列怎么求啊
想一想插入一个数只会使这个位置之后的数的编号都++
那肯定要倒序插入了, 插入的时候把这个数之后的位置的编号–即可
那么只要维护一个区间修改单点查询的树状数组, 存储每一个位置在当前情况(即已经插入了后i个数)的编号, 然后二分插入的位置就好了

然后TTTTT…

发现二分写残了…因为有修改编号, 所以插到最后会出现几个位置的编号相同的情况, 然后就会把之前已经插入的值覆盖掉…GG
发现如果二分出的位置已经有数的话(即有多个位置的编号是当前要求的编号), 一定要选所有位置中最前面的: 否则选后面的位置 会把之后所有的编号–, 前面位置的编号不会改变, 之后将永远选不到惹

然后WAWAWAWA…和黄学长对拍了也没有发现问题…

没有关文件…

GG

沙茶的 代码

改了一天, 丑的一匹

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

// bzoj3173

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN (100000 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int a[MAXN];

struct tree
{
int c[MAXN];
int n;
inline int lowbit(int x)
{
return (x & (-x));
}
void init()
{
for (int i = 1; i <= n; i++)
{
c[i] = lowbit(i);
}
}
int cx(int x)
{
int re = 0;
for (int i = x; i; i -= lowbit(i))
{
re += c[i];
}
return re;
}
void xg(int x)
{
for (int i = x; i <= n; i += lowbit(i))
{
--c[i];
}
}
int ef(int x)
{
int le = 1;
int ri = n + 1;
while (le < ri)
{
int mid = (le + ri) >> 1;
int dqx = cx(mid);
if (dqx == x)
{
if (!a[mid])
{
return mid;
}
else
{
ri = mid;
}
}
else if (dqx < x)
{
le = mid + 1;
}
else
{
ri = mid;
}
}
}
}b;

int n;

int inp[MAXN];
int f[MAXN];
int ef(int);
void solve();
void init();
int main()
{
freopen("in.in", "r", stdin);
freopen("wa.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &inp[i]);
++inp[i];
}
init();
solve();
return 0;
}
void init()
{
b.n = n;
b.init();

//int dqx[MAXN];

for (int i = n; i >= 1; i--)
{
int x = b.ef(inp[i]);
b.xg(x);

/*for (int i = 1; i <= n; i++)
{
dqx[i] = b.cx(i);
}*/

a[x] = i;
}
}
void solve()
{
std::memset(f, 0x7f, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++)
{
int x = ef(a[i]);
f[x + 1] = min(f[x + 1], a[i]);
}
int out[MAXN];
int lastorder = 1;
for (int i = 1; i <= n; i++)
{
if (f[i] < INF)
{
for (int j = lastorder; j < f[i]; j++)
{
out[j] = i - 1;
}
lastorder = f[i];
}
else
{
for (int j = lastorder; j <= n; j++)
{
out[j] = i - 1;
}
break;
}
}
for (int i = 1; i <= n; i++)
{
printf("%d\n", out[i]);
}
}
int ef(int x)
{
int re = 0;
int le = 1;
int ri = n + 1;
while (le < ri)
{
int mid = (le + ri) >> 1;
if (f[mid] <= x)
{
re = mid;
le = mid + 1;
}
else
{
ri = mid;
}
}
return re;
}

/*
3
0 0 2
*/

/*
10
0 0 2 2 0 3 0 4 3 0
*/

By 没救的 Cansult