HDU 4366 Successor 分块做法

http://acm.hdu.edu.cn/showproblem.php?pid=4366

今日重新做了这题的分块，果然是隔太久了，都忘记了。。

首先，用DFS序变成一维的问题

关键是它有两个权值，该如何处理呢?

首先假设我们的DFS序列是List，

那么，对其进行分块。对于每一个块，先按能力排序，用数组tosort[]保存，这样我就可以用O（magic）的时间，就是扫一次这个块，维护出一个数组，mx[i]表示大于等于tosort[i].ablity时，最大的忠诚度。

那么我查询的时候，就可以，如果不在块里的，暴力，否则，因为每一个块已经排好序，那么我可以二分出一个位置，找到第一个能力值大于等于所查询的val，那么mx[pos]是答案，因为mx[pos]就表示大于等于这个位置的能力值，所拥有的最大忠诚度。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn =  + ;

struct Edge {

    int u, v, w;

    int tonext;

}e[ * maxn];

int num;

int first[maxn + ];

int getid[ + ];

struct node {

    int loy, abi;

    bool operator < (const struct node & rhs) const {

        return abi < rhs.abi;

    }

}a[maxn], List[maxn], tosort[maxn];

void addEgde(int u, int v) {

    ++num;

    e[num].u = u;

    e[num].v = v;

    e[num].tonext = first[u];

    first[u] = num;

}

int DFN;

int L[maxn], R[maxn];

bool vis[maxn];

void dfs(int cur) {

    L[cur] = DFN;

    for (int i = first[cur]; i; i = e[i].tonext) {

        int v = e[i].v;

//        assert(vis[v] == false);

//        vis[v] = true;

        ++DFN;

        List[DFN] = tosort[DFN] = a[v];

        dfs(v);

    }

    R[cur] = DFN;

}

int magic;

int mx[maxn];

int tofind(int begin, int end, int val) {

//    cout << begin << " " << end << " ***" << endl;

    if (tosort[end].abi <= val) return -;

    if (tosort[begin].abi > val) return mx[begin];

    while (begin <= end) {

        int mid = (begin + end) >> ;

        if (tosort[mid].abi > val) {

            end = mid - ;

        } else begin = mid + ;

    }

    return mx[begin];

}

void work() {

    int n, m;

    cin >> n >> m;

    magic = (int)sqrt(n * 1.0);

    for (int i = ; i <= n - ; ++i) {

        int fa;

        cin >> fa >> a[i].loy >> a[i].abi;

        getid[a[i].loy] = i;

        addEgde(fa, i);

    }

    dfs();

//    for (int i = 0; i <= n - 1; ++i) {

//        cout << L[i] << " " << R[i] << endl;

//    }

    for (int i = ; i < n; i += magic) {

        int j = i + magic;

        if (j > n) break;

        sort(tosort + i, tosort + j);

        mx[j - ] = tosort[j - ].loy;

        for (int k = j - ; k >= i; --k) {

            if (tosort[k].loy < mx[k + ]) {

                mx[k] = mx[k + ];

            } else mx[k] = tosort[k].loy;

        }

//        for (int k = i; k < i + magic; ++k) {

//            cout << mx[k] << endl;

//        }

    }

    while (m--) {

        int id;

        cin >> id;

        int val = a[id].abi;

        int begin = L[id], end = R[id];

//        cout << begin << " " << end << " ***" << endl;

        int ans = -;

        for (int i = begin + ; i <= end;) {

            if (i % magic ==  && i + magic <= end) {

                ans = max(ans, tofind(i, i + magic - , val));

                i += magic;

            } else {

                if (List[i].abi > val && ans < List[i].loy) {

                    ans = List[i].loy;

                }

                ++i;

            }

        }

        if (ans == -) {

            cout << - << endl;

        } else cout << getid[ans] << endl;

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    IOS;

    a[].abi = a[].loy = -;

    List[] = tosort[] = a[];

    int t;

    cin >> t;

    while (t--) {

        DFN = ;

        num = ;

        memset(mx, -, sizeof mx);

        memset(first, , sizeof first);

        work();

    }

    return ;

}

这题可以用线段树做。

对于这一类题目，就是要维护的东西有两个的。

1、能力值要比所查询的元素大

2、要在一定的区间里查询这些值。

有一个很好用的方法就是排序。

我们肯定是要排除一个因数的影响的了。

我们可以按能力排序，然后先查询能力值最大的（肯定是-1）

然后把它插进线段树，然后找次大的。

这样就确保了每个元素查询的，都是合法的（就是里面的元素，能力值都比他大）

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#define lson L, mid, cur << 1

#define rson mid + 1, R, cur << 1 | 1

const int maxn =  + ;

struct Edge {

    int u, v, w;

    int tonext;

}e[ * maxn];

int num;

int first[maxn + ];

int getid[ + ];

struct node {

    int loy, abi, id;

    bool operator < (const struct node & rhs) const {

        if (abi != rhs.abi) return abi > rhs.abi;

        else return id < rhs.id;

    }

}a[maxn], List[maxn], tosort[maxn];

void addEgde(int u, int v) {

    ++num;

    e[num].u = u;

    e[num].v = v;

    e[num].tonext = first[u];

    first[u] = num;

}

int DFN;

int LQ[maxn], RQ[maxn];

void dfs(int cur) {

    LQ[cur] = DFN;

    for (int i = first[cur]; i; i = e[i].tonext) {

        int v = e[i].v;

        ++DFN;

        List[DFN] = tosort[DFN] = a[v];

        dfs(v);

    }

    RQ[cur] = DFN;

}

int mx[maxn << ];

void pushUp(int cur) {

    mx[cur] = max(mx[cur << ], mx[cur <<  | ]);

}

void UpDate(int pos, int val, int L, int R, int cur) {

    if (L == R) {

        if (pos == L) {

            mx[cur] = val; //wa

        }

        return;

    }

    int mid = (L + R) >> ;

    if (pos <= mid) UpDate(pos, val, lson);

    else UpDate(pos, val, rson);

    pushUp(cur);

}

int query(int begin, int end, int L, int R, int cur) {

    if (L >= begin && R <= end) {

        return mx[cur];

    }

    int mid = (L + R) >> ;

    int lans = -inf, rans = -inf;

    if (mid < end)  rans = query(begin, end, rson);

    if (mid >= begin) lans = query(begin, end, lson);

    return max(lans, rans);

}

int ans[maxn];

void work() {

    int n, m;

    cin >> n >> m;

    for (int i = ; i <= n - ; ++i) {

        int fa;

        cin >> fa >> a[i].loy >> a[i].abi;

        a[i].id = i;

        getid[a[i].loy] = i;

        addEgde(fa, i);

    }

    dfs();

    sort(a, a + n);

    memset(mx, -, sizeof mx);

    for (int i = ; i < n; ++i) {

        int id;

        if (i == n - ) id = ;

        else id = getid[a[i].loy];

        int res = query(LQ[id], RQ[id], , n - , );

        if (res == -) ans[id] = -;

        else ans[id] = getid[res];

        UpDate(LQ[id], a[i].loy, , n - , );

    }

    for (int i = ; i <= m; ++i) {

        int id;

        cin >> id;

        cout << ans[id] << endl;

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    IOS;

    int t;

    cin >> t;

    while (t--) {

        a[].abi = a[].loy = -inf;

        a[].id = ;

        DFN = ;

        num = ;

        memset(first, , sizeof first);

        work();

    }

    return ;

}

巴特西

HDU 4366 Successor 分块做法

最新文章

热门文章