Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

说来惭愧,三个小时AC,这里有代码,求hack

Posted by Yick_Liao at 2015-01-14 19:38:10 on Problem 3368
这道题在刚刚开始的时候我确实没有想到是用的线段树,或许应该说是不知道该怎么是用线段树,但是我先用暴力在脑袋里面模拟一下这个过程,后来发现了实际上其中是有玄机的,原来的数组是没有多大用的,就只用记录每个数字第一次出现的位置就行了,然后原数组中的每个数字的个数就是下一个数字的位置减去当前数字的位置,用线段树来维这些数字的个数就行了。。。 说多了也不好,有些细节就自己慢慢思考吧。(代码写的不好,而且可能思路还不太好,我是菜鸟,请别喷,可以讨论)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mid l + (r - l) / 2
#define lson id << 1, l, mid
#define rson id << 1 | 1, mid + 1, r
#define MAXN 100001
using namespace std;
int arr[MAXN], tree[MAXN * 4];
void Build(int id, int l, int r)
{
    if (l == r) tree[id] = arr[l + 1] - arr[l];
    else
    {
        Build(lson);
        Build(rson);
        tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
    }
}
int Query(int id, int l, int r, int L, int R)
{
    if (R < l || r < L) return 0;
    if (L <= l && r <= R) return tree[id];
    return max(Query(lson, L, R), Query(rson, L, R));
}
int main()
{
    int N, M;
    while (cin >> N && N && cin >> M)
    {
        int k = 1, num_t = MAXN;
        for (int i = 1; i <= N; ++i)
        {
            int num;
            scanf("%d", &num);
            if (num != num_t)
            {
                arr[k++] = i;
                num_t = num;
            }
        }
        arr[k++] = N + 1;
        memset(tree, 0, sizeof(tree));
        Build(1, 1, k - 1);
        while (M--)
        {
            int pos1, pos2;
            scanf("%d%d", &pos1, &pos2);
            int idx1 = lower_bound(arr + 1, arr + k, pos1) - arr;
            int idx2 = lower_bound(arr + 1, arr + k, pos2) - arr;
            if (arr[idx1] == pos1 && arr[idx2] == pos2)
            {
                if (idx1 == idx2) cout << 1 << endl;
                else cout << Query(1, 1, k - 1, idx1, idx2 - 1) << endl;
            }
            else if (arr[idx1] == pos1 && arr[idx2] != pos2)
            {
                if (idx1 + 1 == idx2) cout << pos2 - pos1 + 1 << endl;
                else
                {
                    idx2--;
                    cout << max(pos2 - arr[idx2] + 1, Query(1, 1, k - 1, idx1, idx2 - 1)) << endl;
                }
            }
            else if (arr[idx1] != pos1 && arr[idx2] == pos2)
            {
                int ans = arr[idx1] - pos1;
                if (idx1 == idx2) cout << ans << endl;
                else cout << max(ans, Query(1, 1, k - 1, idx1, idx2 - 1)) << endl;
            }
            else
            {
                if (idx1 == idx2) cout << pos2 - pos1 + 1 << endl;
                else if (idx1 + 1 == idx2) cout << max(arr[idx1] - pos1, pos2 - arr[idx2 - 1] + 1) << endl;
                else cout << max(arr[idx1] - pos1, max(pos2 - arr[idx2 - 1] + 1, Query(1, 1, k - 1, idx1, idx2 - 2))) << endl;
            }
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator