ABC 352
目录
D. Permutation Subsequence
E. Clique Connect
D. Permutation Subsequence
题中两个特征提示了是滑动窗口：（1）固定 k 个数（2）这 k 个数是连续的
因此只需要遍历 1 到 n，固定窗口大小为 k，下标就是数，而下标对应的值是这个数字在 p 数组中出现的下标，通过单调队列维护区间内的最大值和最小值。
单调队列里存的永远是下标，在遍历哪个数组存的就是那个数组的下标（也就是 i）。注意 h = 1，t = 0，看有没有元素是看 h <= t。
因为窗口长度是固定的，所以队列中的下标差值最大值就是固定的，判是否有元素过期（已经从窗口左端出去了），是看 q [ t ] 与 q [ h ] 的差是否超出窗口大小，而不是看队列里的数量是否超出窗口大小。其中 q [ t ] 就是 i。
注意要在 i >= k 的时候才能更新答案。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, k, cnt, ans, a[N], pos[N], q1[N], q2[N]; // min max
string s;signed main()
{cin >> n >> k;for (int i = 1; i <= n; i ++){cin >> a[i];pos[a[i]] = i;}int h1 = 1, t1 = 0, h2 = 1, t2 = 0;ans = INF;for (int i = 1; i <= n; i ++){while (h1 <= t1 && pos[q1[t1]] > pos[i])t1 --;q1[++ t1] = i;if (q1[h1] < i - k + 1)h1 ++;while (h2 <= t2 && pos[q2[t2]] < pos[i])t2 --;q2[++ t2] = i;if (q2[h2] < i - k + 1)h2 ++;if (i >= k)ans = min(ans, pos[q2[h2]] - pos[q1[h1]]);}cout << ans;return 0;
}
E. Clique Connect
和 ks 几乎完全一样，只不过没有直接给出所有要加的边。
先按照边权值从小到大排序，从小的开始，每个集合选第一个作为代表，遍历剩下的，如果不在一个集合就合并，一旦加满 n - 1 条边就退出。
能否建成一棵树是看能不能选出来 n - 1 条边，因为 ks 是对边进行操作，不是看能不能选出来 n 个点。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;struct node
{int k, c, id;bool operator < (const node & other) const{if (c != other.c)return c < other.c;return k < other.k;}
}p[N];int T, n, m, cnt, ans, fa[N];
vector<int> a[N];int find(int x)
{if (x == fa[x])return x;return fa[x] = find(fa[x]);
}signed main()
{cin >> n >> m;for (int i = 1; i <= m; i ++){cin >> p[i].k >> p[i].c;p[i].id = i;for (int j = 1; j <= p[i].k; j ++){int x;cin >> x;a[i].push_back(x);}}for (int i = 1; i <= n; i ++)fa[i] = i;sort(p + 1, p + m + 1);for (int i = 1; i <= m; i ++){int k = p[i].k, c = p[i].c, id = p[i].id;int u = a[id][0];u = find(u);for (int j = 1; j < a[id].size(); j ++){int v = a[id][j];v = find(v);if (u != v){fa[v] = u;cnt ++;ans += c;}}if (cnt == n - 1)break;}if (cnt != n - 1)cout << "-1";elsecout << ans;return 0;
}