Poj3145Harmony Forever线段树+鸽巢原理

　　小数据直接暴力，大数据查找0-mod — 1,mod — 2*mod-1,2*mod — 3*mod-1.....

因为 n%mod 的范围<=n-1 ,所以k*mod — (k+1)*mod之间%mod的最小值 应该是 k*mod — (k+1)*mod-1之间的最小值，如果存在的话，用线段树维护下区间最值就好了，有个地方得注意下。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<stdlib.h>
using namespace std;
typedef long long LL;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

const int maxn = 1000000 + 1000;
int sum[maxn << 2];
const int INF = 1<<30;
int ncnt;
int val[maxn];
int pos[maxn];

void up(int rt){
    sum[rt] = min(sum[rt << 1], sum[rt << 1 | 1]);
}

void build(int l, int r, int rt)
{
    sum[rt] = INF;
    if (l == r){
        return;
    }
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
    up(rt);
}

void update(int key, int l, int r, int rt)
{
    if (l == r){
        sum[rt] = key; return;
    }
    int mid = (l + r) >> 1;
    if (key <= mid) update(key, lson);
    else update(key, rson);
    up(rt);
}

int ask(int L, int R, int l, int r, int rt)
{
    if (L <= l&&r <= R) return sum[rt];
    int ans = INF;
    int mid = (l + r) >> 1;
    if (L <= mid) ans = min(ans, ask(L, R, lson));
    if (R > mid) ans = min(ans, ask(L, R, rson));
    return ans;
}

void gao(int x)
{
    int Min = INF; int ans=INF;
    for (int i = ncnt - 1; i >= 1; i--){
        if (val[i] % x == 0) {
            printf("%d
", i); return ;
        }
        if (val[i] % x < Min){
            Min = val[i] % x;
            ans = i;
        }
    }
    printf("%d
", ans);
}

void gao1(int x)
{
    int l = 0; int r = x - 1; int ans = -1;//刚开始初始为INF 挂了一晚上，因为他后面要取模不能直接 拿这个ans%x 与temp%x比较
    while (l <= maxn){
        if (r > maxn) r = maxn;
        int temp = ask(l, r, 0, maxn, 1);
        if(temp!=INF){
        if (ans==-1||temp%x < ans%x) ans = temp;
        else if (temp%x == ans%x&&pos[temp]>pos[ans])
            ans = temp;
        }
        l += x; r += x;
    }
    printf("%d
", pos[ans]);
}

int main()
{
    char str[100];
    int k;
    int cnt = 0;
    int T;
    while (scanf("%d",&T),T){
        if(cnt) puts("");
        ncnt = 1;
        build(0, maxn, 1);
        printf("Case %d:
", ++cnt);
        while (T--){
            scanf("%s%d", str, &k);
            if (str[0] == 'B'){
                val[ncnt] = k;
                pos[k] = ncnt++;
                update(k, 0, maxn, 1);
            }
            else{
                if(ncnt==1){
                    printf("-1
");
                }
                else
                if (k < 10000) gao(k);
                else gao1(k);
            }
        }
    }
    return 0;
}