首页 > 其他 > 详细

【洛谷5537】【XR-3】系统设计(哈希_线段树上二分)

时间:2019-12-09 01:16:02      阅读:183      评论:0      收藏:0      [点我收藏+]

我好像国赛以后就再也没有写过 OI 相关的博客 qwq

Upd: 这篇博客是 NOIP (现在叫 CSP 了)之前写的,但是咕到 CSP 以后快一个月才发表 …… 我最近这么咕怎么办啊 ……

题目

洛谷 5537

分析

这道题可以说是非常神了。这题看上去无从下手,但是 通过膜拜题解 后能发现一些美妙的性质。树是不修改的,任意一对祖先 - 后代之间的路径一定都可以表示成一个 固定的 整数序列。并且,如果 \(u,v,w\) 是祖先 - 后代且深度递增,则 \((u,v)\) 的序列与 \((v,w)\) 的序列拼接起来就是 \((u,w)\) 的序列。

技术分享图片

如图,\((1,2)\) 之间的序列是 "1" (因为 \(2\)\(1\) 的第一小的儿子);\((1,5)\) 之间的序列是 "12" (因为从 \(1\)\(5\) 要先走第一小,再走第二小),恰好是 \((1,2)\)\((2,5)\) 的序列拼起来。

这样,我们就可以用一个序列(对应着从根到这个结点的走法)来表示一个结点了(设 \(u\) 的序列为 \(s_u\) )。从结点 \(u\) 开始按照一个序列 \(a\) 走,走到的结点(如果存在)对应的序列就是 \(s_u\)\(a\) 拼接起来(相当于从根开始先按照 \(s_u\) 走到 \(u\) ,然后按 \(a\) 走到 \(s_u+a\) )。把序列 - 结点的映射关系用哈希表存下来,就可以 \(O(1)\) 判断从一个结点按照一个序列走若干步能否走到一个结点,以及查询如果能走到,走到的是哪个结点。

那么我们就有了一个做法:预处理出每个结点的序列的哈希值,并用线段树维护给定序列的哈希值。查询时二分走的长度(即取序列 \([l,\mathrm{mid}]\) 的部分),判断能否走到一个结点。直接二分是 \(O(nlog^2n)\) 过不去,必须在线段树上二分。

代码

比较弱,写了 6KB 。顺便说下陕西省美术馆门口写代码体验极佳。

注意拼接两个哈希值时乘的种子的次数。(这是个大坑)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;

namespace zyt
{
    template<typename T>
    inline bool read(T &x)
    {
        char c;
        bool f = false;
        x = 0;
        do
            c = getchar();
        while (c != EOF && c != '-' && !isdigit(c));
        if (c == EOF)
            return false;
        if (c == '-')
            f = true, c = getchar();
        do
            x = x * 10 + c - '0', c = getchar();
        while (isdigit(c));
        if (f)
            x = -x;
        return true;
    }
    template<typename T>
    inline void write(T x)
    {
        static char buf[20];
        char *pos = buf;
        if (x < 0)
            putchar('-'), x = -x;
        do
            *pos++ = x % 10 + '0';
        while (x /= 10);
        while (pos > buf)
            putchar(*--pos);
    }
    const int N = 5e5 + 10;
    typedef long long ll;
    int rot, n, m, q, arr[N];
    vector<int> g[N];
    namespace Hash
    {
        typedef pair<int, int> pii;
        typedef pii hash_t;
        const pii seed = pii(71, 853), P = pii(int(1e9 + 7), int(1e9 + 9));
        hash_t pow[N];
        pii operator + (const pii &a, const pii &b)
        {
            return pii((a.first + b.first) % P.first, (a.second + b.second) % P.second);
        }
        pii operator * (const pii &a, const pii &b)
        {
            return pii(int((ll)a.first * b.first % P.first), int((ll)a.second * b.second % P.second));
        }
        void init()
        {
            pow[0] = pii(1, 1);
            for (int i = 1; i < N; i++)
                pow[i] = pow[i - 1] * seed;
        }
    }
    using namespace Hash;
    hash_t h[N];
    namespace Hash_Table
    {
        const int P = 1e6 - 17, seed = 24601;
        struct edge
        {
            pii to;
            int w, next;
        }e[N];
        int head[P], ecnt;
        void add(const int a, const pii b, const int c)
        {
            e[ecnt] = (edge){b, c, head[a]}, head[a] = ecnt++;
        }
        void init()
        {
            ecnt = 0;
            memset(head, -1, sizeof(head));
        }
        void insert(const pii a, const int b)
        {
            int tmp = ((ll)a.first * seed + a.second) % P;
            add(tmp, a, b);
        }
        int query(const pii a)
        {
            int tmp = ((ll)a.first * seed + a.second) % P;
            for (int i = head[tmp]; ~i; i = e[i].next)
                if (e[i].to == a)
                    return e[i].w;
            return -1;
        }
    }
    namespace Segment_Tree
    {
        struct node
        {
            hash_t h;
        }tree[N << 2];
        void update(const int rot, const int len)
        {
            tree[rot].h = tree[rot << 1].h * pow[len] + tree[rot << 1 | 1].h;
        }
        void build(const int rot, const int lt, const int rt)
        {
            if (lt == rt)
                return void(tree[rot].h = hash_t(arr[lt], arr[lt]));
            int mid = (lt + rt) >> 1;
            build(rot << 1, lt, mid), build(rot << 1 | 1, mid + 1, rt);
            update(rot, rt - mid);
        }
        void change(const int rot, const int lt, const int rt, const int pos, const int x)
        {
            if (lt == rt)
                return void(tree[rot].h = hash_t(x, x));
            int mid = (lt + rt) >> 1;
            if (pos <= mid)
                change(rot << 1, lt, mid, pos, x);
            else
                change(rot << 1 | 1, mid + 1, rt, pos, x);
            update(rot, rt - mid);
        }
        hash_t query(const int rot, const int lt, const int rt, const int ls, const int rs)
        {
            if (ls <= lt && rt <= rs)
                return tree[rot].h;
            int mid = (lt + rt) >> 1;
            if (rs <= mid)
                return query(rot << 1, lt, mid, ls, rs);
            else if (ls > mid)
                return query(rot << 1 | 1, mid + 1, rt, ls, rs);
            else
                return query(rot << 1, lt, mid, ls, rs) * pow[min(rs, rt) - mid]
                    + query(rot << 1 | 1, mid + 1, rt, ls, rs);
        }
        int query(const int rot, const int lt, const int rt, const int ls, const int rs, const hash_t h)
        {
            if (lt == rt)
                return Hash_Table::query(h * seed + tree[rot].h);
            int mid = (lt + rt) >> 1;
            if (rs <= mid)
                return query(rot << 1, lt, mid, ls, rs, h);
            else if (ls > mid)
                return query(rot << 1 | 1, mid + 1, rt, ls, rs, h);
            else
            {
                int w;
                hash_t hh = h * pow[mid - max(ls, lt) + 1] + 
                    (ls <= lt ? tree[rot << 1].h : query(1, 1, m, ls, mid));
                if ((w = Hash_Table::query(hh)) != -1)
                {
                    int tmp = query(rot << 1 | 1, mid + 1, rt, ls, rs, hh);
                    if (tmp == -1)
                        return w;
                    else
                        return tmp;
                }
                else
                    return query(rot << 1, lt, mid, ls, rs, h);
            }
        }
    }
    void dfs(const int u)
    {
        sort(g[u].begin(), g[u].end());
        int cnt = 0;
        for (vector<int>::iterator it = g[u].begin(); it != g[u].end(); it++)
        {
            int v = *it;
            ++cnt;
            h[v] = h[u] * seed + hash_t(cnt, cnt);
            dfs(v);
        }
    }
    int work()
    {
        using namespace Segment_Tree;
        init();
        Hash_Table::init();
        read(n), read(m), read(q);
        for (int i = 1; i <= n; i++)
        {
            int a;
            read(a);
            if (!a)
                rot = i;
            else
                g[a].push_back(i);
        }
        h[rot] = hash_t(0, 0);
        dfs(rot);
        for (int i = 1; i <= n; i++)
            Hash_Table::insert(h[i], i);
        for (int i = 1; i <= m; i++)
            read(arr[i]);
        build(1, 1, m);
        while (q--)
        {
            int opt;
            read(opt);
            if (opt == 1)
            {
                int x, l, r, ans;
                read(x), read(l), read(r);
                ans = query(1, 1, m, l, r, h[x]);
                write(ans == -1 ? x : ans), putchar('\n');
            }
            else
            {
                int a, b;
                read(a), read(b);
                change(1, 1, m, a, b);
            }

        }
        return 0;
    }
}
int main()
{
    freopen("5537.in", "r", stdin);
    return zyt::work();
}

【洛谷5537】【XR-3】系统设计(哈希_线段树上二分)

原文:https://www.cnblogs.com/zyt1253679098/p/12008621.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!