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
A 3
A 5
B 6
A 9
B 4
Sample Output
3
1
这种求的东西很奇怪的题要想到根号分治。
考虑小于$\sqrt y$这部分答案每次可以暴力更新，设g[i]为当y为i时的答案。
大于$\sqrt y$的这部分相当于有若干后缀，在每个后缀里找最小值，一共最多不超过$\sqrt y$个后缀，那么我们可以$O(\sqrt y)$修改$O(1)$查每个后缀。
具体地，更新时用x更新这个块左端点到x的信息和前面那些块的信息。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
#define N 3000050
#define RR register
int M=550;
int pos[N],L[N],f[N],g[N],tag[N],n=3000000;
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd() {
RR int x=0; RR char c=nc();
while(c<'0'||c>'9') c=nc();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=nc();
return x;
}
inline char rc() {
RR char c=nc();
while(c!='A'&&c!='B') c=nc();
return c;
}
char pbuf[10000000] , *pp = pbuf;
inline void write(int x) {
static int sta[35];
RR int top = 0;
if(!x)sta[++top]=0;
while(x) sta[++top] = x % 10 , x /= 10;
while(top) *pp ++ = sta[top -- ] ^ '0';
}
void add(int x) {
int i;
for(i=1;i<=M;i++) {
g[i]=min(g[i],x%i);
}
for(i=L[pos[x]];i<=x;i++) f[i]=min(f[i],x);
for(i=pos[x]-1;i>=0;i--) tag[i]=min(tag[i],x);
}
int ask(int x) {
if(!x) x++;
return min(tag[pos[x]],f[x]);
}
int solve(int x) {
if(x<M) return g[x];
int t=N,i,j;
for(i=0,j=x;i<=n;i=j,j+=x) {
if(j>n) j=n+1;
int y=ask(i);
if(y<j) t=min(t,y-i);
}
return t;
}
int main() {
int i;
for(i=1;i<=n;i++) pos[i]=i/M,f[i]=N;
for(i=n;i;i--) L[pos[i]]=i;
for(i=1;i<M;i++) g[i]=N;
for(i=0;i<=n/M;i++) tag[i]=N;
int q; q=rd();
int x;
while(q--) {
char opt=rc(); x=rd();
if(opt=='A') {
add(x);
}else {
write(solve(x)); *pp++='\n';
}
}
fwrite(pbuf,1,pp-pbuf,stdout);
}