Poj 3145 Harmony 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;

}