首页 > ACM题库 > HDU-杭电 > HDU 3303-Harmony Forever-线段树-[解题报告]HOJ
2014
03-16

HDU 3303-Harmony Forever-线段树-[解题报告]HOJ

Harmony Forever

问题描述 :

We believe that every inhabitant of this universe eventually will find a way to live together in harmony and peace; that trust, patience, kindness and loyalty will exist between every living being of this earth; people will find a way to appreciate and cooperate with each other instead of continuous bickering, arguing and fighting. Harmony — the stage of society so many people dream of and yet it seems so far away from now …

Fortunately, the method of unlocking the key to true Harmony is just discovered by a group of philosophers. It is recorded on a strange meteorite which has just hit the earth. You need to decipher the true meaning behind those seemingly random symbols … More precisely, you are to write a program which will support the following two kinds of operation on an initially empty set S :

1.
B X : Add number X to set S . The Kth command in the form of B X always happens at time K , and number X does not belong to set S before this operation.
2.
A Y : Of all the numbers in set S currently, find the one which has the minimum remainder when divided by Y . In case a tie occurs, you should choose the one which appeared latest in the input. Report the time when this element is inserted.

It is said that if the answer can be given in the minimum possible time, true Harmony can be achieved by human races. You task is to write a program to help us.

输入:

There are multiple test cases in the input file. Each test case starts with one integer T where 1<=T<=40000 . The following T lines each describe an operation, either in the form of “B X " or “A Y " where 1<=X , Y<=500000 .

T = 0 indicates the end of input file and should not be processed by your program.

输出:

There are multiple test cases in the input file. Each test case starts with one integer T where 1<=T<=40000 . The following T lines each describe an operation, either in the form of “B X " or “A Y " where 1<=X , Y<=500000 .

T = 0 indicates the end of input file and should not be processed by your program.

样例输入:

5 
B 1 
A 5 
B 10 
A 5 
A 40 
2 
B 1 
A 2
0

样例输出:

Case 1: 
1 
2 
1 

Case 2: 
1

大意就是对一个集合,有两种操作,一个是将某个元素加入集合中,一个是问当前集合中mod y 最小的数,如果有多个,输出最近加入的那个元素,当然题目要求的是输出他们加入集合的时间是什么。

题目的数据范围一看就是线段树类型的。

然后对每个y,由鸽巢定理,y+1个数中必然存在mod y相同的数,那么分为多个区间进行查询,即[0, y - 1] [y , 2 * y - 1]…… 然后取最优解即可

但是这样可能会退化,当y等于1的时候就发现,要查询50W个区间,每次查询都是log(n)级别,还不如直接遍历当前序列效率高,因为序列最多也就4W个数据。

所以可以推测,当y比较小的时候,直接遍历会更快。

实际上离散化会更靠谱,因为只有4W个数据,然后建树查询的时候就方便多了 ,经过验证,离散前是1360ms,离散化后就成800多ms了,瞬间进前5

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 510005
#define MAXM 164444
#define INF 100000000
#define eps 1e-7
#define L(X) X<<1
#define R(X) X<<1|1
using namespace std;
struct node
{
    int left, right;
    int mi;
}tree[4 * MAXN];
int a[MAXN], pos[MAXN];
void up(int C)
{
    tree[C].mi = min(tree[L(C)].mi, tree[R(C)].mi);
}
void make_tree(int s, int e, int C)
{
    tree[C].left = s;
    tree[C].right = e;
    tree[C].mi = INF;
    if(s == e) return;
    int mid = (s + e) >> 1;
    make_tree(s, mid, L(C));
    make_tree(mid + 1, e, R(C));
}
void update(int p, int C)
{
    if(tree[C].left == tree[C].right)
    {
        tree[C].mi = p;
        return;
    }
    int mid = (tree[C].left + tree[C].right) >> 1;
    if(mid >= p) update(p, L(C));
    else update(p, R(C));
    up(C);
}
int ans;
void query(int s, int e, int C)
{
    if(tree[C].left >= s && tree[C].right <= e)
    {
        ans = min(ans, tree[C].mi);
        return;
    }
    int mid = (tree[C].left + tree[C].right) >> 1;
    if(mid >= s) query(s, e, L(C));
    if(mid < e) query(s, e, R(C));
}
int in()
{
    int flag = 1;
    char ch;
    int a = 0;
    while((ch = getchar()) == ' ' || ch == '\n');
    if(ch == '-') flag = -1;
    else
    a += ch - '0';
    while((ch = getchar()) != ' ' && ch != '\n')
    {
        a *= 10;
        a += ch - '0';
    }
    return flag * a;
}
void out(int a)
{
    if(a >= 10)out(a / 10);
    putchar(a % 10 + '0');
}
int main()
{
    int t, x, cas = 0;
    char s;
    while(scanf("%d", &t) != EOF && t)
    {
        if(cas) puts("");
        int cnt = 0;
        memset(pos, -1, sizeof(pos));
        printf("Case %d:\n", ++cas);
        make_tree(1, MAXN - 1, 1);
        getchar();
        while(t--)
        {
            s = getchar();
            x = in();
            if(s == 'A')
            {

                if(x < 5000)
                {
                    ans = INF;
                    int tx = x;
                    for(int i = cnt - 1; i >= 0; i--)
                    {
                        if(a[i] % x < tx)
                        {
                            tx = a[i] % x;
                            ans = a[i];
                        }
                        if(tx == 0) break;
                    }
                    if(ans == INF) {puts("-1");}
                    else {out(pos[ans] + 1); putchar('\n');}
                }
                else
                {
                    int bd = 500055 / x;
                    int res = INF;
                    int tx = x;
                    for(int i = 0; i <= bd; i++)
                    {
                        ans = INF;
                        int low = i * x;
                        if(low < 1) low = 1;
                        int high = (i + 1) * x - 1;
                        if(high > 500054) high = 500054;
                        query(low, high, 1);
                        if(ans == INF) continue;
                        if(ans % x < tx)
                        {
                            tx = ans % x;
                            res = ans;
                        }
                        else if(ans % x == tx)
                        {
                            if(pos[ans] > pos[res]) res = ans;
                        }
                    }
                    if(res == INF) {puts("-1");}
                    else {out(pos[res] + 1); putchar('\n');}
                }
            }
            else
            {
                if(pos[x] == -1)
                {
                    pos[x] = cnt;
                    a[cnt++] = x;
                    update(x, 1);
                }
            }
        }
    }
    return 0;
}

然后是离散化版本的,速度快了许多啊

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 45555
#define MAXM 164444
#define INF 100000000
#define eps 1e-7
#define L(X) X<<1
#define R(X) X<<1|1
using namespace std;
struct node
{
    int left, right;
    int mi;
}tree[4 * MAXN];
int a[MAXN], pos[555555], x[MAXN], ax[MAXN];
void up(int C)
{
    tree[C].mi = min(tree[L(C)].mi, tree[R(C)].mi);
}
void make_tree(int s, int e, int C)
{
    tree[C].left = s;
    tree[C].right = e;
    tree[C].mi = INF;
    if(s == e) return;
    int mid = (s + e) >> 1;
    make_tree(s, mid, L(C));
    make_tree(mid + 1, e, R(C));
}
void update(int p, int C)
{
    if(tree[C].left == tree[C].right)
    {
        tree[C].mi = x[p];
        return;
    }
    int mid = (tree[C].left + tree[C].right) >> 1;
    if(mid >= p) update(p, L(C));
    else update(p, R(C));
    up(C);
}
int ans;
void query(int s, int e, int C)
{
    if(tree[C].left >= s && tree[C].right <= e)
    {
        ans = min(ans, tree[C].mi);
        return;
    }
    int mid = (tree[C].left + tree[C].right) >> 1;
    if(mid >= s) query(s, e, L(C));
    if(mid < e) query(s, e, R(C));
}
int in()
{
    int flag = 1;
    char ch;
    int a = 0;
    while((ch = getchar()) == ' ' || ch == '\n');
    if(ch == '-') flag = -1;
    else
    a += ch - '0';
    while((ch = getchar()) != ' ' && ch != '\n')
    {
        a *= 10;
        a += ch - '0';
    }
    return flag * a;
}
void out(int a)
{
    if(a >= 10)out(a / 10);
    putchar(a % 10 + '0');
}
int bin(int v, int bound)
{
    int low = 0, high = bound - 1, mid;
    while(low <= high)
    {
        mid = (low + high) >> 1;
        if(x[mid] == v) return mid;
        if(x[mid] < v) low = mid + 1;
        else high = mid - 1;
    }
    return high;
}
char s[40005];
int main()
{
    int t, cas = 0;
    while(scanf("%d", &t) != EOF && t)
    {
        if(cas) puts("");
        int cnt = 0;
        memset(pos, -1, sizeof(pos));
        printf("Case %d:\n", ++cas);
        int nt = 0;
        getchar();
        for(int i = 0; i < t; i++)
        {
            s[i] = getchar();
            ax[i] = in();
            if(s[i] == 'B') x[nt++] = ax[i];
        }
        x[nt++] = 1;
        x[nt++] = 500100;
        sort(x, x + nt);
        nt = unique(x, x + nt) - x;
        make_tree(0, nt - 1, 1);
        for(int i = 0; i < t; i++)
        {
            if(s[i] == 'A')
            {
                if(ax[i] < 500)
                {
                    ans = INF;
                    int tx = ax[i];
                    for(int j = cnt - 1; j >= 0; j--)
                    {
                        if(a[j] % ax[i] < tx)
                        {
                            tx = a[j] % ax[i];
                            ans = a[j];
                        }
                        if(tx == 0) break;
                    }
                    if(ans == INF) {puts("-1");}
                    else {out(pos[ans] + 1); putchar('\n');}
                }
                else
                {
                    int bd = 500055 / ax[i];
                    int res = INF;
                    int tx = ax[i];
                    for(int j = 0; j <= bd; j++)
                    {
                        ans = INF;
                        int low = j * ax[i];
                        if(low < 1) low = 1;
                        int high = (j + 1) * ax[i] - 1;
                        if(high > 500054) high = 500054;
                        int ll = bin(low, nt);
                        int rr = bin(high, nt);
                        if(x[ll] < low) ll++;
                        if(ll > rr) continue;
                        query(ll, rr, 1);
                        if(ans == INF) continue;
                        if(ans % ax[i] < tx)
                        {
                            tx = ans % ax[i];
                            res = ans;
                        }
                        else if(ans % ax[i] == tx)
                        {
                            if(pos[ans] > pos[res]) res = ans;
                        }
                    }
                    if(res == INF) {puts("-1");}
                    else {out(pos[res] + 1); putchar('\n');}
                }
            }
            else
            {
                if(pos[ax[i]] == -1)
                {
                    pos[ax[i]] = cnt;
                    a[cnt++] = ax[i];
                    int l = bin(ax[i], nt);
                    update(l, 1);
                }
            }
        }
    }
    return 0;
}

参考:http://blog.csdn.net/sdj222555/article/details/7383593