『分类讨论与并查集』Homework

题目描述

题解

如果$y$的取值比较小，我们可以每一次都对读入都直接用数组标记。

如果$y$的取值比较大的话，我们可以查找$1?t$的最小值，$t+1$~$2?t$的最小值等等。最小值可以利用并查集来维护，倒着删除数字即可。具体实现的话让每一个数$i$联想$i+1$,如果存在数字i就以自己为祖先；每次从第一个开始找即可。删除数字就把$i$连向$i+1$，其它就是细节问题了。

我们来考虑这个分界线是多少？$n$的取值差不多有几十万，$y$的取值几百到一千即可。这里取$\sqrt{300000}$为分界线。

代码如下：

#include <bits/stdc++.h>using namespace std;
const int N = 2000000;int n, T;
int val[N], del[N], vis[N], a[N], fa[N], ans[N];int get(int x)
{
    if (fa[x] == x) return x;return fa[x] = get(fa[x]);
}char get(void)
{
    char c = getchar();while (c < 'A' || c > 'Z') c = getchar();return c;
}int main(void)
{
    freopen("set.in","r",stdin);freopen("set.out","w",stdout);scanf("%d", &n);T = sqrt(300000);int Max = 0;memset(a,30,sizeof a);memset(ans,-30,sizeof ans);for (int i=1;i<=n;++i){
    char c = get(); scanf("%d", val+i);if (c == 'A') {
    del[i] = 1;//删除标记 vis[val[i]] = 1;for (int j=1;j<=T;++j)a[j] = min(a[j],val[i]%j);//第一种情况直接暴力标记 Max = max(Max,val[i]);}if (c == 'B') {
    if (val[i] <= T) ans[i] = a[val[i]];//第一种情况的查询 }}for (int i=0;i<=Max+1;++i) vis[i] ? fa[i] = i : fa[i] = i+1;//并查集向右找第一次出现 for (int i=n;i>=1;--i){
    if (del[i] == 1) fa[val[i]] = get(val[i]+1);//删除 else if (ans[i] < 0) {
    ans[i] = INT_MAX;for (int j=0;j<=Max;j+=val[i])ans[i] = min(ans[i],get(j)%val[i]);//枚举每一段，找段内第一次出现的数字 }}for (int i=1;i<=n;++i) if (ans[i] >= 0) printf("%d\n", ans[i]);return 0;
}