bzoj 4320 ShangHai2006 Homework

　　维护一个mod 1到mod 500的最小答案数组，对于每个A操作更新一下该数组，并把其置入一个set中，对于B操作，如果询问<=500直接输出，如果大于500则枚举倍数去set中查找第一个大于等于该倍数的数字，复杂度O(nsqrt(n)log(n))

　　代码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<set>
 5 #define pb push_back
 6 #define N 700100
 7 using namespace std;
 8 int n,a,i,j,ans[N];
 9 char ch;
10 set<int> s;
11 set<int>::iterator it;
12 int main()
13 {
14     s.clear();
15 
16     for (i=1;i<=500;i++)
17     ans[i]=0x37373737;
18     scanf("%d",&n);
19      
20     
21     for (i=1;i<=n;i++)
22     {
23         scanf(" %c %d",&ch,&a);
24         if (ch=='A')
25         {
26             for (j=1;j<=500;j++)
27             ans[j]=min(ans[j],a%j);
28             s.insert(a);
29         }
30         else
31         {
32             if (a<=500)
33             printf("%d
",ans[a]);
34             else
35             {
36                 int Ans=0x37373737;
37                 for (j=0;j<=300000;j+=a)
38                 {
39                     it=s.lower_bound(j);
40                     if (it==s.end()) break;
41                     Ans=min(Ans,(*it)-j);
42                 }
43                 printf("%d
",Ans);
44             }
45         }
46     } 
47 }