BZOJ 4320(ShangHai2006 Homework-询问分段+并查集)

Description

1：在人物集合 S 中加入一个新的程序员，其代号为 X,保证 X 在当前集合中不存在。
2：在当前的人物集合中询问程序员的mod Y 最小的值。 （为什么统计这个？因为拯救
过世界的人太多了，只能取模）
Input

第一行为用空格隔开的一个个正整数 N。
接下来有 N 行，若该行第一个字符为“A” ，则表示操作 1；若为“B”，表示操作 2；
其中 对于 100%的数据：N≤100000， 1≤X,Y≤300000，保证第二行为操作 1。
Output

对于操作 2，每行输出一个合法答案。
Sample Input

5

A 3

A 5

B 6

A 9

B 4

Sample Output

3

1

HINT

【样例说明】

在第三行的操作前，集合里有 3、5 两个代号，此时 mod 6 最小的值是 3 mod 6 = 3；

在第五行的操作前，集合里有 3、5、9，此时 mod 4 最小的值是 5 mod 4 = 1；

询问分段+并查集
对于Y≤3000−−−−√我们暴力更新
大于的，我们查询离1,Y,2Y..往后出现的第一个数（并查集或set都可以）

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (300000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
class bingchaji
{
public:
    int father[MAXN],n,cnt;
    void mem(int _n)
    {
        n=cnt=_n;
        For(i,n) father[i]=i;
    }
    int getfather(int x) 
    {
        if (father[x]==x) return x;

        return father[x]=getfather(father[x]);
    }
    void unite(int x,int y)
    {
        x=getfather(x);
        y=getfather(y);
        if (x^y) {
            --cnt;
            father[x]=y;
        }
    }
    bool same(int x,int y)
    {
        return getfather(x)==getfather(y);
    }
}S;
const int N=300000,B=sqrt(300000);
int opt[MAXN],a[MAXN],mn[MAXN],ans[MAXN];
int main()
{
//  freopen("bzoj4320.in","r",stdin);
//  freopen(".out","w",stdout);
    int n;
    scanf("%d\n",&n);
    S.mem(N+1); MEMI(mn) MEMI(ans)
    For(i,N) S.father[i]=i+1;
    For(i,n) {
        char c;int p;
        scanf("%c %d\n",&c,&p);
        opt[i]=c-'A';a[i]=p;
        if (c=='A') {
            S.father[p]=p;
            For(j,B) mn[j]=min(mn[j],p%j);
        }else {
            if (p<=B) ans[i]=mn[a[i]];
        }
    }
    ForD(i,n) {
        if (!opt[i]) {
            S.father[a[i]]=a[i]+1;
        } else {
            if (a[i]>B) {
                ans[i]=S.getfather(1)%a[i];
                for(int j=a[i];j<=N;j+=a[i]) {
                    int p=S.getfather(j);
                    if (p<=N) ans[i]=min(ans[i],p%a[i]);
                }
            }
        }
    }
    For(i,n) if (opt[i]) printf("%d\n",ans[i]);
    return 0;
}