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

这种求的东西很奇怪的题要想到根号分治。

考虑小于$\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);

}

秒客网