BZOJ 3531 旅行 解题报告


3531: [Sdoi2014]旅行
Time Limit: 40 Sec  Memory Limit: 512 MB
Description
       S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
       在S国的历史上常会发生以下几种事件：
”CC x c”：城市x的居民全体改信了c教；
”CW x w”：城市x的评级调整为w;
”QS x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
”QM x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。
       由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。
       为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
Input
输入的第一行包含整数N，Q依次表示城市数和事件数。
接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。
接下来N-1行每行两个整数x，y表示一条双向道路。
接下来Q行，每行一个操作，格式如上所述。
Output
对每个QS和QM事件，输出一行，表示旅行者记下的数字。
Sample Input
5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4
Sample Output
8
9
11
3
HINT
N，Q < =10^5    ， C < =10^5

 数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。
Solution
此题改变了我长期以来对线段树的刻板认识——我一直以为线段树至多可建一棵，或者即使可以通过建多棵线段树解决也一定存在仅建立一棵线段树的解。可是本题必须建立多棵线段树。
本题包含树上的单点修改和区间查询，询问区间最大值与区间和。我们用树链剖分将树上的节点映射到直线上，然后为每一种宗教信仰的城市分别建一棵动态开点线段树，这样问题便转换成了最普通的线段树问题。
本题可能需要使用非常多空间，我们首先用队列实现一个动态内存分配系统。用队列维护可用的内存空间的地址，分配一块空间相当于队列的弹出(pop)，释放一块空间相当于队列的压入(push)，分别用方法add和del表示。实现：
template<typename _Tp>
class RAMexplorer
{
public:
    void setsize(int size)
    {
        this->size = size;
        data = new _Tp*[size];
        RAM = new _Tp[size];
        for (int i = 0; i<size; i++)
        {
            data[i] = &RAM[i];
        }
        head = 0;
        tail = size;
    }
    void del(_Tp *p)
    {
        data[(tail++) % size] = p;
    }
    _Tp* add()
    {
        return data[(head++) % size];
    }
private:
    int size;
    int tail, head;
    _Tp **data;
    _Tp *RAM;
};
由于动态开点，线段树的节点需要存放左右孩子的指针。注意是指针，而不是索引，这注意是为了适应我们手写的内存池。实现：
struct node
{
    int l, r;
    node *left, *right;
    int maxn, sum;
};
       修改总体上与普通的动态开点一致，唯一的变化是需要在回溯时动态释放内存（explorer是RAMexplorer对象）：
if (now->left->maxn == 0 && now->right->maxn == 0)
{
    explorer.del(now->left);
    explorer.del(now->right);
    now->left = NULL;
    now->right = NULL;
}
       剩下的操作基本上是照着模板默写，这里便不再讲解了。
Code（数据结构的题，347行是很正常的）
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

void read(int &x)
{
    x = 0; char ch = getchar(); bool f = 0;
    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    if (f)x = -x;
}

void read(long long &x)
{
    x = 0; char ch = getchar(); bool f = 0;
    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    if (f)x = -x;
}

void read(char &x)
{
    x = getchar();
    while (x <= ' ')x = getchar();
}

struct node
{
    int l, r;
    node *left, *right;
    int maxn, sum;
};

//内存池，用队列实现
template<typename _Tp>
class RAMexplorer
{
public:
    //设置内存池大小，只能调用一次
    void setsize(int size)
    {
        this->size = size;
        data = new _Tp*[size];
        RAM = new _Tp[size];
        for (int i = 0; i<size; i++)
        {
            data[i] = &RAM[i];
        }
        head = 0;
        tail = size;
    }
    void del(_Tp *p)
    {
        //      cout<<"del "<<p<<endl;
        data[(tail++) % size] = p;
    }
    _Tp* add()
    {
        return data[(head++) % size];
    }
private:
    int size;
    int tail, head;
    _Tp **data;
    _Tp *RAM;
};

//不同信仰的城市所在的线段树的根节点
node root[100001];
RAMexplorer <node> explorer;

//建树
void build(int v)
{
    for (int i = 0; i <= 100000; i++)
    {
        root[i].l = 1;
        root[i].r = v;
        root[i].right = NULL;
        root[i].left = NULL;
    }
}

//单点修改
void setdata(int p, int x, node *now)
{
    if (now->l == now->r)
    {
        now->maxn = x;
        now->sum = x;
        return;
    }
    int mid = (now->l + now->r) >> 1;
    //分配空间
    if (now->left == NULL)
    {
        now->left = explorer.add();
        now->left->l = now->l;
        now->left->r = mid;
        now->left->maxn = 0;
        now->left->sum = 0;
        now->left->left = NULL;
        now->left->right = NULL;
    }
    if (now->right == NULL)
    {
        now->right = explorer.add();
        now->right->l = mid + 1;
        now->right->r = now->r;
        now->right->maxn = 0;
        now->right->sum = 0;
        now->right->left = NULL;
        now->right->right = NULL;
    }
    if (p <= mid)setdata(p, x, now->left);
    else setdata(p, x, now->right);
    now->maxn = max(now->left->maxn, now->right->maxn);
    now->sum = now->left->sum + now->right->sum;
    //释放空间
    if (now->left->maxn == 0 && now->right->maxn == 0)
    {
        explorer.del(now->left);
        explorer.del(now->right);
        now->left = NULL;
        now->right = NULL;
    }
}

//区间和
int getsum(int l, int r, node *now)
{
    if (now == NULL)return 0;
    if (now->l == l&&now->r == r)
    {
        return now->sum;
    }
    int mid = (now->l + now->r) >> 1;
    if (r <= mid)
    {
        return getsum(l, r, now->left);
    }
    else if (mid<l)
    {
        return getsum(l, r, now->right);
    }
    else
    {
        return getsum(l, mid, now->left) + getsum(mid + 1, r, now->right);
    }
}

//区间最大值
int getmax(int l, int r, node *now)
{
    if (now == NULL)return 0;
    if (now->l == l&&now->r == r)
    {
        return now->maxn;
    }
    int mid = (now->l + now->r) >> 1;
    if (r <= mid)
    {
        return getmax(l, r, now->left);
    }
    else if (mid<l)
    {
        return getmax(l, r, now->right);
    }
    else
    {
        return max(getmax(l, mid, now->left), getmax(mid + 1, r, now->right));
    }
}

//邻接表，front是通常的to
struct graph_t
{
    int front, nex;
}graph[300001];
int tail = 100000;

void addedge(int u, int v)
{
    int tmp1 = graph[u].nex, tmp2 = graph[v].nex;
    graph[u].nex = ++tail, graph[v].nex = ++tail;
    graph[tail - 1].front = v, graph[tail].front = u;
    graph[tail - 1].nex = tmp1, graph[tail].nex = tmp2;
}

int nchild[100001];
int findorder[100001];
bool vis[100001];
int parent[100001];
int top[100001];
int height[100001];
int nfind = 1;

int belief[100001];
int weight[100001];//评级

void dfs1(int now)
{
    vis[now] = true;
    nchild[now] = 1;
    for (int i = graph[now].nex; i; i = graph[i].nex)
    {
        if (!vis[graph[i].front])
        {
            height[graph[i].front] = height[now] + 1;
            parent[graph[i].front] = now;
            dfs1(graph[i].front);
            nchild[now] += nchild[graph[i].front];
        }
    }
}

void dfs2(int now)
{
    int maxchild = -1;
    int pmaxchild;
    findorder[now] = nfind++;
    for (int i = graph[now].nex; i; i = graph[i].nex)
    {
        if (parent[now] != graph[i].front&&maxchild<nchild[graph[i].front])
        {
            maxchild = nchild[graph[i].front];
            pmaxchild = graph[i].front;
        }
    }
    if (maxchild != -1)
    {
        top[pmaxchild] = top[now];
        dfs2(pmaxchild);
    }
    for (int i = graph[now].nex; i; i = graph[i].nex)
    {
        if (parent[now] != graph[i].front&&graph[i].front != pmaxchild)
        {
            top[graph[i].front] = graph[i].front;
            dfs2(graph[i].front);
        }
    }
}

//初始化函数，完成树链剖分和建树
void init(int v)
{
    height[1] = 1;
    dfs1(1);
    top[1] = 1;
    dfs2(1);
    build(v);
    //友情提醒：空间要开32倍，许多人因此RE，
    explorer.setsize(v * 32);
    for (int i = 1; i <= v; i++)
    {
        setdata(findorder[i], weight[i], &root[belief[i]]);
    }
}

//在树上查询和
int querysum(int x, int y)
{
    int sum = 0;
    node *r = &root[belief[x]];
    while (top[x] != top[y])
    {
        if (height[top[x]]<height[top[y]])swap(x, y);
        sum += getsum(findorder[top[x]], findorder[x], r);
        x = parent[top[x]];
    }
    if (height[x]>height[y])swap(x, y);
    return sum + getsum(findorder[x], findorder[y], r);
}

//在树上查询最大值
int querymax(int x, int y)
{
    int maxn = 0;
    node *r = &root[belief[x]];
    while (top[x] != top[y])
    {
        if (height[top[x]]<height[top[y]])swap(x, y);
        maxn = max(maxn, getmax(findorder[top[x]], findorder[x], r));
        x = parent[top[x]];
    }
    if (height[x]>height[y])swap(x, y);
    return max(maxn, getmax(findorder[x], findorder[y], r));
}

int main()
{
    int v, q;
    read(v); read(q);
    for (int i = 1; i <= v; i++)
    {
        read(weight[i]);
        read(belief[i]);
    }
    for (int i = 1; i<v; i++)
    {
        int from, to;
        read(from); read(to);
        addedge(from, to);
    }
    init(v);
    while (q--)
    {
        char c1, c2;
        read(c1); read(c2);
        if (c1 == 'C')
        {
            if (c2 == 'C')
            {
                int p, b;
                read(p); read(b);
                setdata(findorder[p], weight[p], &root[b]);
                setdata(findorder[p], 0, &root[belief[p]]);
                belief[p] = b;
            }
            else
            {
                int p, w;
                read(p); read(w);
                setdata(findorder[p], w, &root[belief[p]]);
                weight[p] = w;
            }
        }
        else
        {
            if (c2 == 'S')
            {
                int x, y;
                read(x); read(y);
                printf("%d\n", querysum(x, y));
            }
            else
            {
                int x, y;
                read(x); read(y);
                printf("%d\n", querymax(x, y));
            }
        }
    }
    return 0;
}

时间：
标签： , , ,

没有评论:

发表评论

订阅： 博文评论 (Atom)