bzoj4320 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；

正解：分块。

首先分类讨论，模数$<=sqrt{n}$和模数$>sqrt{n}$两种情况。

第一种情况直接在加入一个数以后暴力维护即可。

对于第二种情况，$300000/mod$肯定$<sqrt{n}$，所以我们每次查询时，可以直接查询$>=k*mod$的最小的数，直接更新最小值即可。

注意到第二种情况有$O(nsqrt{n})$次查询，$O(n)$次修改，所以我们要把查询的总复杂度降下来。

我们分块维护$>=i$的数中最小的数，每次修改复杂度变成$O(sqrt{n})$，查询复杂度降为$O(1)$就行了。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define inf (1<<30)
 6 #define N (300010)
 7 #define min(a,b) (a<b ? a : b)
 8 
 9 using namespace std;
10 
11 int bl[N],LL[N],RR[N],f[N],res[N],lazy[N],n,size,totb,block;
12 char ch[5];
13 
14 il int gi(){
15   RG int x=0,q=1; RG char ch=getchar();
16   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
17   if (ch=='-') q=-1,ch=getchar();
18   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
19   return q*x;
20 }
21 
22 il void update(RG int x,RG int v){
23   RG int B=bl[x]-1; for (RG int i=1;i<=B;++i) lazy[i]=min(lazy[i],v);
24   for (RG int i=LL[B+1];i<=x;++i) res[i]=min(res[i],v); return;
25 }
26 
27 il int query(RG int x){
28   RG int ret=min(res[1],lazy[1]);
29   for (RG int i=x;i<=size;i+=x) ret=min(ret,min(res[i],lazy[bl[i]])-i);
30   return ret;
31 }
32  
33 int main(){
34 #ifndef ONLINE_JUDGE
35   freopen("homework.in","r",stdin);
36   freopen("homework.out","w",stdout);
37 #endif
38   n=gi(),size=300000,block=550,totb=(size-1)/block+1;
39   for (RG int i=1;i<=totb;++i) lazy[i]=inf;
40   for (RG int i=1;i<=block;++i) f[i]=inf;
41   for (RG int i=1;i<=size;++i){
42     bl[i]=(i-1)/block+1,res[i]=inf;
43     if (!LL[bl[i]]) LL[bl[i]]=i; RR[bl[i]]=i;
44   }
45   for (RG int i=1,x;i<=n;++i){
46     scanf("%s",ch),x=gi();
47     if (ch[0]=='A'){
48       for (RG int j=1;j<=block;++j) f[j]=min(f[j],x%j);
49       update(x,x);
50     }
51     if (ch[0]=='B'){
52       if (x<=block) printf("%d
",f[x]);
53       else printf("%d
",query(x));
54     }
55   }
56   return 0;
57 }