Eva

HomeworkTime Limit: 10 Sec  Memory Limit: 128 MB
Description

  1：在人物集合 S 中加入一个新的程序员，其代号为 X,保证 X 在当前集合中不存在。 

  2：在当前的人物集合中询问程序员的mod Y 最小的值。 （为什么统计这个？因为拯救

过世界的人太多了，只能取模） 

第一行为用空格隔开的一个个正整数 N。 

接下来有 N 行，若该行第一个字符为“A” ，则表示操作 1；若为“B”，表示操作 2； 

其中 对于 100%的数据：N≤100000， 1≤X,Y≤300000，保证第二行为操作 1。 

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

5            
A 3             
A 5
B 6
A 9
B 4

3
1

【样例说明】 

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

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

/**************************************************************

    Problem: 4320

    User: ictsing

    Language: C++

    Result: Accepted

    Time:1456 ms

    Memory:6272 kb

****************************************************************/

 

//BZOJ4320 ShangHai2006 Homework

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int mt = 300000+5;

int f[mt],ans[mt],type[mt],num[mt];

char op[2];

bool check[mt];

const int mxb=550;

int minn[mxb+10];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

      ch=getchar();

      if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

      num=num*10+ch-'0';

      ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int findf(int x)

{

    if(!f[x]||f[x]==x) return x;

    return f[x]=findf(f[x]);

}

int main()

{

    int n=read();

    memset(minn,0x3f,sizeof(minn));

    for(int i=1;i<=n;i++)

    {

        scanf("%s",op);

        type[i]=1;

        num[i]=read();      

        if(op[0]=='A')

        {

            type[i]=0;

            for(int j=1;j<=mxb;j++)

                minn[j]=min(minn[j],num[i]%j);

            check[num[i]]=true;

        }

        else if(num[i]<=mxb) ans[i]=minn[num[i]];

    }

    for(int i=1;i<=300000;i++)

        if(!check[i]) f[findf(i)]=findf(i+1);

    for(int i=n;i>=1;i--)

    {

        if(type[i]==0)

        {

            f[findf(num[i])]=findf(num[i]+1);

        }

        else if(num[i]>mxb)

        {

            ans[i]=0x7fffffff;

            for(int j=0;j<=300000;j+=num[i])

            {

                int tmp=findf(max(j,1));

                if(tmp<=300000) ans[i]=min(ans[i],tmp%num[i]);

            }

        }

    }

    for(int i=1;i<=n;i++)

        if(type[i]==1)

            printf("%d\n",ans[i]);

    return 0;

}