HDU 4605 Magic Ball Game(可持续化线段树,树状数组,离散化)

Magic Ball Game

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 2489    Accepted Submission(s): 759

Problem Description

When the magic ball game turns up, Kimi immediately falls in it. The interesting game is made up of N balls, each with a weight of w[i]. These N balls form a rooted tree, with the 1st ball as the root. Any ball in the game has either 0 or 2 children ball. If a node has 2 children balls, we may define one as the left child and the other as the right child. The rules are simple: when Kimi decides to drop a magic ball with a weight of X, the ball goes down through the tree from the root. When the magic ball arrives at a node in the tree, there's a possibility to be catched and stop rolling, or continue to roll down left or right. The game ends when the ball stops, and the final score of the game depends on the node at which it stops. After a long-time playing, Kimi now find out the key of the game. When the magic ball arrives at node u weighting w[u], it follows the laws below: 1  If X=w[u] or node u has no children balls, the magic ball stops. 2  If X<w[u], there's a possibility of 1/2 for the magic ball to roll down either left or right. 3  If X>w[u], the magic ball will roll down to its left child in a possibility of 1/8, while the possibility of rolling down right is 7/8. In order to choose the right magic ball and achieve the goal, Kimi wonders what's the possibility for a magic ball with a weight of X to go past node v. No matter how the magic ball rolls down, it counts if node v exists on the path that the magic ball goes along. Manual calculating is fun, but programmers have their ways to reach the answer. Now given the tree in the game and all Kimi's queries, you're required to answer the possibility he wonders.

Input

The input contains several test cases. An integer T(T≤15) will exist in the first line of input, indicating the number of test cases. Each test case begins with an integer N(1≤N≤105), indicating the number of nodes in the tree. The following line contains N integers w[i], indicating the weight of each node in the tree. (1 ≤ i ≤ N, 1 ≤ w[i] ≤ 109, N is odd) The following line contains the number of relationships M. The next M lines, each with three integers u,a and b(1≤u,a,b≤N), denotes that node a and b are respectively the left child and right child of node u. You may assume the tree contains exactly N nodes and (N-1) edges. The next line gives the number of queries Q(1≤Q≤105). The following Q lines, each with two integers v and X(1≤v≤N,1≤X≤109), describe all the queries.

Output

If the magic ball is impossible to arrive at node v, output a single 0. Otherwise, you may easily find that the answer will be in the format of 7x/2y . You're only required to output the x and y for each query, separated by a blank. Each answer should be put down in one line.

Sample Input

1
3
2 3 1
1
1 2 3
3
3 2
1 1
3 4

Sample Output

0
0 0
1 3
这道题目和HDU 5877 差不多。两道题目都是在一棵树上进行操作,从树的根节点到某个节点的路径是唯一的,这个路径的所有节点形成的序列。如果要在这个序列里进行各种操作,那么就要用树状数组或者线段树来解决。用树状数组要注意,在dfs回朔的时候要删除点。如果用线段树来解决,那么可以有两种方式,一个是把线段树当做树状数组来用,毕竟树状数组能实现的东西线段树都能实现。另外一种方式可以用可持续化线段树,就是在树的每一个点上面建立一个线段树,那么每个点上的线段树就表示从根节点到这个节点的路径上所有点插到线段树里。
可持续化线段树:#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <map>
#include <vector>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
vector<int> e[maxn+5];
map<LL,int> mm;
LL rt[maxn+5];
LL ls[maxn*20+5];
LL rs[maxn*20+5];;
LL p2;
LL p;
int n,m,q;
LL num[maxn*20+5][2];
LL a[maxn+5];
LL w[maxn+5];
int Hash(LL x)
{
    return upper_bound(a+1,a+n+1,x)-a-1;
}
int newnode()
{
    ls[p]=rs[p]=num[p][0]=num[p][1]=0;
    return p++;
}
void update(LL &node,int l,int r,LL tag,int flag)
{

    if(node==0)
        node=newnode();
    else
    {
        ls[p]=ls[node];
        rs[p]=rs[node];
        num[p][0]=num[node][0];
        num[p][1]=num[node][1];
        node=p++;
    }
    if(l==r)
    {
        num[node][flag]++;
        return;
    }
    num[node][flag]++;
    int mid=(l+r)>>1;
    if(tag<=mid) update(ls[node],l,mid,tag,flag);
    else update(rs[node],mid+1,r,tag,flag);

}
LL query(LL node,int l,int r,LL L,LL R,int flag)
{
    if(L>R) return 0;
    if(!node) return 0;
    if(L<=l&&r<=R)
        return num[node][flag];
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid)  ret+=query(ls[node],l,mid,L,R,flag);
    if(R>mid)  ret+=query(rs[node],mid+1,r,L,R,flag);
    return ret;
}
void dfs(int root)
{
    int len=e[root].size();
    for(int i=0;i<len;i++)
    {
        int v=e[root][i];
        update(rt[v]=rt[root],1,n,Hash(w[root]),i);
        dfs(v);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    LL x,y,z;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            e[i].clear();
            scanf("%lld",&w[i]);
            a[i]=w[i];
        }
        sort(a+1,a+n+1);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%lld%lld%lld",&x,&y,&z);
            e[x].push_back(y);
            e[x].push_back(z);

        }
        memset(rt,0,sizeof(rt));
        memset(num,0,sizeof(num));
        p=1;
        dfs(1);
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%lld%lld",&x,&y);
            if(x==1) {printf("0 0\n");continue;}

            int xx=Hash(y);
            if(a[xx]==y)
            {
                int num2=query(rt[x],1,n,xx,xx,0);
                int num5=query(rt[x],1,n,xx,xx,1);


                if(num2||num5)
                {
                    printf("0\n");
                    continue;
                }


            }

            LL num1=query(rt[x],1,n,1,xx,0);

            LL num3=query(rt[x],1,n,xx+1,n,0);

            LL num4=query(rt[x],1,n,1,xx,1);

            LL num6=query(rt[x],1,n,xx+1,n,1);

            LL ans1=3*(num1+num4)+num3+num6;
            LL ans2=num4;

            printf("%lld %lld\n",ans2,ans1);




        }
    }
    return 0;
}

树状数组:
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;
const int maxn=1e5;
typedef long long int LL;
int e[maxn+5][2];
int c0[maxn+5];
int c1[maxn+5];
int n,m,q;
int lowbit(int x) {return x&(-x);}
int w[maxn+5];
int vis[maxn+5];
int a[maxn+5];
vector<pair<int,int> > b[maxn+5];
int ans1[maxn+5];
int ans2[maxn+5];
int Hash(int x)
{
    return upper_bound(a+1,a+n+1,x)-a-1;
}
void update0(int x,int tag)
{
    while(x<=n)
    {
        c0[x]+=tag;
        x+=lowbit(x);
    }
}
int sum0(int x)
{
    int num=0;
    for(int i=x;i>=1;i-=lowbit(i))
    {
        num+=c0[i];
    }
    return num;
}
void update1(int x,int tag)
{
    while(x<=n)
    {
        c1[x]+=tag;
        x+=lowbit(x);
    }
}
int sum1(int x)
{
    int num=0;
    for(int i=x;i>=1;i-=lowbit(i))
    {
        num+=c1[i];
    }
    return num;
}
void init()
{
    memset(c0,0,sizeof(c0));
    memset(c1,0,sizeof(c1));
    memset(vis,0,sizeof(vis));
    memset(e,-1,sizeof(e));
    memset(ans1,0,sizeof(ans1));
    memset(ans2,0,sizeof(ans2));
    for(int i=1;i<=n;i++)
    {
        b[i].clear();
    }
}
void dfs(int root)
{
    for(int i=0;i<=1;i++)
    {
        if(e[root][i]==-1) continue;
        int v=e[root][i];
        if(!i) update0(Hash(w[root]),1);
        else update1(Hash(w[root]),1);
        if(vis[v])
        {
            int len=b[v].size();
            for(int j=0;j<len;j++)
            {
                int y=b[v][j].first;
                int x=b[v][j].second;
                int xx=Hash(y);
                if(a[xx]==y)
                {
                    if((sum0(xx)-sum0(xx-1))!=0||(sum1(xx)-sum1(xx-1))!=0)
                    {
                        ans1[x]=-1;
                        continue;
                    }
                }
                    int left_low=sum0(xx);
                    int left_up=sum0(n)-sum0(xx);
                    int right_low=sum1(xx);
                    int right_up=sum1(n)-sum1(xx);
                    ans1[x]=right_low;
                    ans2[x]=3*(left_low+right_low)+left_up+right_up;

            }
        }
        dfs(v);
        if(!i) update0(Hash(w[root]),-1);
        else update1(Hash(w[root]),-1);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int x,y,z;
        scanf("%d",&n);
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
            a[i]=w[i];
        }
        sort(a+1,a+n+1);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            e[x][0]=y;
            e[x][1]=z;
        }
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&x,&y);
            vis[x]=1;
            b[x].push_back(make_pair(y,i));
        }
        dfs(1);
        for(int i=1;i<=q;i++)
        {
            if(ans1[i]==-1) {printf("0\n");continue;}
            else
            {
                printf("%d %d\n",ans1[i],ans2[i]);
            }
        }


    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

UESTC 482 Charitable Exchange(优先队列+bfs)

Charitable Exchange Time Limit: 4000/2000MS (Java/Others)     Memory Limit: 65...

3405
来自专栏算法修养

ZOJ 3605 Find the Marble(dp)

Find the Marble ---- Time Limit: 2 Seconds      Memory Limit: 65536 KB ---- Alic...

3717
来自专栏小樱的经验随笔

POJ 3264 Balanced Lineup【线段树区间查询求最大值和最小值】

Balanced Lineup Time Limit: 5000MS Memory Limit: 65536K Total Submission...

3624
来自专栏小樱的经验随笔

HDU 1412 {A} + {B}

{A} + {B} Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K...

37715
来自专栏算法修养

POJ-2329 Nearest number - 2(BFS)

Nearest number - 2 Time Limit: 5000MS Memory Limit: 65536K Total Submis...

2474
来自专栏ml

HDUOJ --2566

统计硬币 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

2787
来自专栏小樱的经验随笔

HDU 2092 整数解

整数解 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

2766
来自专栏算法修养

PAT 甲级 1104 sum of Number Segments

1104. Sum of Number Segments (20) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16...

2835
来自专栏ml

HDUOJ---1195Open the Lock

Open the Lock Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

2856
来自专栏ml

HDUOJ-------1753大明A+B(大数之小数加法)

大明A+B Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

36012

扫码关注云+社区

领取腾讯云代金券