[LOJ#2326]「清华集训 2017」简单数据结构
试题描述
参加完IOI2018之后就是姚班面试。而你，由于讨厌物理、并且想成为乔布斯一样的创业家，被成功踢回贵系。
转眼，时间的指针被指向2019，大二，12月初，考试周。
你早听学长说，数据结构期中考很难，对竞赛生不友好，集训队选手做不完卷子。
你冷笑。哼，堂堂国际金，这点难度的考试算什么。
两小时，你看完习题解析前五章所有内容，并且倒背如流；
一小时，你看了500页的讲义，并且记忆犹新；
十分钟，你骑车到考场，自信的你只带了一把水笔，虽然考试让带资料；
现在，摊开传说中神级卷子，你定神一看——
给出一个长度为 \(N\) 的序列 \(A_{1},A_{2},\cdots,A_{N}\)，如果 \(A\) 中的一个子序列 \(B_1,B_2,\cdots,B_M\)，满足条件：
\(1\le M\le N\)
\(\forall 1\le i<M\)，\(B_i | B_{i+1}\)那么称 \(B\) 为 \(A\) 的上升倍数子序列。
现在有一个长度为 \(N\) 的序列 \(A\) 被初始化为 \(A_{1},A_{2},\cdots,A_{N}\)，以及 \(Q\) 次对序列 \(A\) 的操作。此处要求实现如下四种操作：
0 x：在序列 \(A\) 的最左端插入一个数字 \(x\)；1 x：在序列 \(A\) 的最右端插入一个数字 \(x\)；2：移除序列 \(A\) 最左端的一个数字；3：移除序列 \(A\) 最右端的一个数字；
在初始化序列 \(A\) 和每次操作之后，请计算此时序列 \(A\) 中最长上升倍数子序列的长度 \(\mathrm{MaxLen}\)，以及所有长度为 \(\mathrm{MaxLen}\) 的上升倍数子序列的不同的开头数 \(\mathrm{Cnt}\)，输出 \(\mathrm{MaxLen}\) 和 \(\mathrm{Cnt}\)。
为了大幅度降低题目难度，保证在任意时刻序列 \(A\) 非空，其中的元素互不相等，并且均为 \(1\sim M\) 之间的正整数；同一个数字最多只会被插入 \(C\) 次。
输入
输入第一行包含三个正整数 \(N,M,Q\)，具体含义见上，保证 \(1\le N \le 10^5\)，\(N\le M \le 10^6\)，\(0\le Q \le 10^5\)；
输入第二行包含 \(N\) 个正整数，为 \(A_1,A_2,\cdots,A_N\)，保证 \(1\le A_i\le M\)，并且序列 \(A\) 中的元素互不相等；
接下来共 \(Q\) 行输入，每行输入格式形如 0 x 或者 1 x 或者 2 或者 3，具体含义见上。
输出
输出共 \(Q+1\) 行，在初始化和每次对序列 \(A\) 操作后，输出 \(A\) 中最长上升倍数子序列的长度 \(\mathrm{MaxLen}\) 和所有长度为 \(\mathrm{MaxLen}\) 的上升倍数子序列的不同的开头数 \(\mathrm{Cnt}\)，用一个空格隔开。
输入示例
5 10 101 2 5 9 1021 7330 8321 830 3
输出示例
3 12 22 22 21 31 41 31 22 11 21 3
数据规模及约定
对于所有的数据，有 \(1\le N \le 10^5\)，\(N\le M \le 10^6\)，\(0\le Q \le 10^5\)，\(1\le A_i\le M\)，\(C=10\)。
后记
“奋战两小时，考个四五十”的表情包占领了你的朋友圈：
- “啊，感觉自己人生完全了”
- “但愿……我真的能拿到四五十”
- “我考完了……考完了……完了”
- “曾经以为是开玩笑的，原来我还是naïve了”
你冷笑。提前半小时交卷，你自然觉得，数据结构，满分，正常。
题解
这题就是一个有时间复杂度保证的暴力。
令 \(f_i\) 表示以第 \(i\) 个数为开头的最长上升倍数子序列长度，然后再记录一下每种 \(f_i\) 的值各有多少个。同时维护一下对于每个位置 \(i\)，使最长上升倍数子序列长度最长（即取到 \(f_i\)）时可能的所有结尾（我们令位置 \(i\) 的结尾集合为 \(Rely_i\)）。
左边添加直接维护，就是 dp 再往左推一格。左边删也是只用删掉一个位置的信息。
右边添加 \(x\)，就将所有左边有的 \(x\) 的约数的位置找出来更新一下，维护一下上面的信息。右边删也是找到所有约数的位置，然后在更新 \(f_i\) 的时候，讨论一下它的 \(Rely_i\) 是否只包含最后一个位置，然后当 \(f\) 值需要变小时暴力处理就好了。
#include#include #include #include #include #include #include #include #include using namespace std;#define rep(i, s, t) for(int i = (s); i <= (t); i++)#define dwn(i, s, t) for(int i = (s); i >= (t); i--)int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 1000010int n, m, q, f[maxn], pos[maxn], A[maxn], hd, tl, tot[21];vector divisor[maxn];set RelyOn[maxn];void GetDivisor(int x) { if(divisor[x].size()) return ; int m = (int)sqrt(x + .5); rep(i, 1, m) if(x % i == 0) { divisor[x].push_back(i); if(i != x / i) divisor[x].push_back(x / i); } sort(divisor[x].begin(), divisor[x].end()); return ;}void upd(int x, int v) { if(f[x]) tot[f[x]]--; f[x] = v; tot[v]++; return ;}int tmpos[maxn], cnt;int main() { n = read(); m = read(); q = read(); hd = q + 1; tl = q; rep(i, 1, n) A[++tl] = read(), pos[A[tl]] = tl; dwn(i, tl, hd) { for(int x = A[i] << 1; x <= m; x += A[i]) if(pos[x] > i) { if(f[pos[x]] + 1 > f[i]) upd(i, f[pos[x]] + 1), RelyOn[i] = RelyOn[pos[x]]; else if(f[pos[x]] + 1 == f[i]) { set :: iterator it = RelyOn[pos[x]].begin(); while(it != RelyOn[pos[x]].end()) { if(!RelyOn[i].count(*it)) RelyOn[i].insert(*it); it++; } } } if(!f[i]) upd(i, 1), RelyOn[i].insert(i); } dwn(i, 20, 1) if(tot[i]){ printf("%d %d\n", i, tot[i]); break; } rep(kase, 1, q) { int tp = read();// printf("%d: %d\n", kase, tp); if(tp == 0) { A[--hd] = read(); pos[A[hd]] = hd; for(int x = A[hd] << 1; x <= m; x += A[hd]) if(pos[x]) { if(f[pos[x]] + 1 > f[hd]) upd(hd, f[pos[x]] + 1), RelyOn[hd] = RelyOn[pos[x]]; else if(f[pos[x]] + 1 == f[hd]) { set :: iterator it = RelyOn[pos[x]].begin(); while(it != RelyOn[pos[x]].end()) { if(!RelyOn[hd].count(*it)) RelyOn[hd].insert(*it); it++; } } } if(!f[hd]) upd(hd, 1), RelyOn[hd].insert(hd); } if(tp == 1) { A[++tl] = read(); pos[A[tl]] = tl; upd(tl, 1); RelyOn[tl].insert(tl); GetDivisor(A[tl]); cnt = 0; rep(i, 0, (int)divisor[A[tl]].size() - 1) { tmpos[++cnt] = pos[divisor[A[tl]][i]]; if(!tmpos[cnt]) cnt--; } sort(tmpos + 1, tmpos + cnt + 1); dwn(i, cnt - 1, 1) rep(j, i + 1, cnt) if(A[tmpos[j]] % A[tmpos[i]] == 0) { if(f[tmpos[i]] < f[tmpos[j]] + 1) upd(tmpos[i], f[tmpos[j]] + 1), RelyOn[tmpos[i]] = RelyOn[tmpos[j]]; else if(f[tmpos[i]] == f[tmpos[j]] + 1) { set :: iterator it = RelyOn[tmpos[j]].begin(); while(it != RelyOn[tmpos[j]].end()) { if(!RelyOn[tmpos[i]].count(*it)) RelyOn[tmpos[i]].insert(*it); it++; } } } } if(tp == 2) { int x = A[hd++]; tot[f[pos[x]]]--; f[pos[x]] = 0; RelyOn[pos[x]].clear(); pos[x] = 0; } if(tp == 3) { int x = A[tl--], xp = pos[x]; tot[f[pos[x]]]--; f[pos[x]] = 0; RelyOn[pos[x]].clear(); pos[x] = 0; GetDivisor(x); cnt = 0; rep(i, 0, (int)divisor[x].size() - 1) { tmpos[++cnt] = pos[divisor[x][i]]; if(!tmpos[cnt]) cnt--; } sort(tmpos + 1, tmpos + cnt + 1); dwn(i, cnt, 1) { int tx = A[tmpos[i]]; if(!RelyOn[pos[tx]].count(xp)) continue; RelyOn[pos[tx]].erase(xp); if(RelyOn[pos[tx]].empty()) { tot[f[pos[tx]]]--; f[pos[tx]] = 0; for(int v = tx << 1; v <= m; v += tx) if(pos[v] > pos[tx]) { if(f[pos[v]] + 1 > f[pos[tx]]) upd(pos[tx], f[pos[v]] + 1), RelyOn[pos[tx]] = RelyOn[pos[v]]; else if(f[pos[v]] + 1 == f[pos[tx]]) { set :: iterator it = RelyOn[pos[v]].begin(); while(it != RelyOn[pos[v]].end()) { if(!RelyOn[pos[tx]].count(*it)) RelyOn[pos[tx]].insert(*it); it++; } } } if(!f[pos[tx]]) upd(pos[tx], 1), RelyOn[pos[tx]].insert(pos[tx]); } } }// rep(i, hd, tl) printf("%d%c", A[i], i < tl ? ' ' : '\n'); dwn(i, 20, 1) if(tot[i]){ printf("%d %d\n", i, tot[i]); break; } } return 0;}