首页 > 代码库 > hdu 4605 Magic Ball Game (在线主席树/离线树状数组)
hdu 4605 Magic Ball Game (在线主席树/离线树状数组)
hdu 4605
题意：
有一颗树，根节点为1，每一个节点要么有两个子节点，要么没有，每个节点都有一个权值wi 。然后，有一个球，附带值x 。
球到达某个节点上，如果x==wi，那么球停在这个节点上 。当然，这个点是叶子节点也会停止 。
如果x<wi，那么有1/2的概率走向左子树，有1/2的概率走向右子树 。
如果x>wi，那么有1/8的概率走向左子树，有7/8的概率走向右子树 。
问球经过v节点的概率 。（停在v节点也算）
解法：
在线的话每一个节点建一棵根节点到该节点的线段树，离线的话就先把询问按DFS序排序，然后瞎搞搞就ok了 。。。
在线主席树
#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <queue>#include <set>#include <vector>#include <map>#define ll long longusing namespace std;const int N=100007;int Ls[N*20],Rs[N*20],cnt[N*20][2];int root[N],tot;int e[N][2];int w[N],sort_w[N];int n;inline int Hash(int x){ return upper_bound(sort_w+1,sort_w+n+1,x)-sort_w-1;}inline void init(){ tot=0; memset(e,-1,sizeof(e));}inline int bulidtree(int L,int R){ int k=tot++; cnt[k][0]=cnt[k][1]=0; if (L==R) return k; int mid=(L+R)>>1; Ls[k]=bulidtree(L,mid); Rs[k]=bulidtree(mid+1,R); return k;}inline void copy(int x,int y){ Ls[x]=Ls[y]; Rs[x]=Rs[y]; cnt[x][0]=cnt[y][0]; cnt[x][1]=cnt[y][1];}// to 0 左子树 1 右子树inline int update(int o,int p,int to,int L,int R){ int k=tot++; copy(k,o); cnt[k][to]++; if (L==R) return k; int mid=(L+R)>>1; if (p<=mid) Ls[k]=update(Ls[k],p,to,L,mid); else Rs[k]=update(Rs[k],p,to,mid+1,R); return k;}inline int query(int o,int x,int y,int to,int L,int R){ if (x>y) return 0; if (L==x && R==y) return cnt[o][to]; int mid=(L+R)>>1; if (y<=mid) return query(Ls[o],x,y,to,L,mid); else if (x>mid) return query(Rs[o],x,y,to,mid+1,R); else return query(Ls[o],x,mid,to,L,mid)+query(Rs[o],mid+1,y,to,mid+1,R);}inline void dfs(int u){ for (int i=0;i<=1;i++) if (~e[u][i]) { int v=e[u][i]; root[v]=update(root[u],Hash(w[u]),i,1,n); dfs(v); }}int main(){ int t,m,q; scanf("%d",&t); while (t--){ init(); scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&w[i]); sort_w[i]=w[i]; } sort(sort_w+1,sort_w+n+1); scanf("%d",&m); while (m--){ int u,a,b; scanf("%d %d %d",&u, &a, &b); e[u][0]=a; e[u][1]=b; } root[1]=bulidtree(1,n); dfs(1); scanf("%d",&q); while (q--){ int v,x; scanf("%d %d",&v,&x); int id=Hash(x); if (x==sort_w[id]){ if (query(root[v],id,id,0,1,n) || query(root[v],id,id,1,1,n)){ puts("0"); continue; } } int L_down=query(root[v],1,id,0,1,n); int L_up=query(root[v],id+1,n,0,1,n); int R_down=query(root[v],1,id,1,1,n); int R_up=query(root[v],id+1,n,1,1,n); printf("%d %d\n",R_down,L_up+R_up+3*L_down+3*R_down); } } return 0;}
离线树状数组
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <queue> 7 #include <set> 8 #include <vector> 9 #include <map> 10 #define ll long long 11 12 using namespace std; 13 14 const int N=100007; 15 16 int w[N],e[N][2]; 17 int sort_w[N]; 18 int c[N][2]; // 树状数组 19 int n,Q; 20 int pos[N]; 21 int ans[N][2]; 22 23 struct QUERY{ 24 int v,x,id; 25 int s; 26 bool operator < (const QUERY & t) const { 27 return s<t.s; 28 } 29 }q[N]; 30 31 inline int Hash(int x){ 32 return upper_bound(sort_w+1,sort_w+n+1,x)-sort_w-1; 33 } 34 35 inline void init(){ 36 memset(c,0,sizeof(c)); 37 memset(e,0,sizeof(e)); 38 } 39 40 inline int lowbit(int x){ 41 return x&(-x); 42 } 43 44 inline void add(int x,int d,int to){ 45 while (x<=n){ 46 c[x][to]+=d; 47 x+=lowbit(x); 48 } 49 } 50 51 inline int sum(int x,int to){ 52 int ret=0; 53 while (x){ 54 ret+=c[x][to]; 55 x-=lowbit(x); 56 } 57 return ret; 58 } 59 60 inline int query(int L,int R,int to){ 61 return sum(R,to)-sum(L-1,to); 62 } 63 64 int cnt; 65 inline void dfs1(int u){ 66 pos[u]=++cnt; 67 for (int i=0;i<=1;i++) if (e[u][i]) 68 dfs1(e[u][i]); 69 } 70 71 inline void dfs2(int u){ 72 while (cnt<=Q && q[cnt].v==u){ 73 int id=Hash(q[cnt].x); 74 if (sort_w[id]==q[cnt].x){ 75 if (query(id,id,0) || query(id,id,1)){ 76 ans[q[cnt].id][0]=-1; 77 cnt++; 78 continue; 79 } 80 } 81 82 int L_down=query(1,id,0); 83 int L_up=query(id+1,n,0); 84 int R_down=query(1,id,1); 85 int R_up=query(id+1,n,1); 86 87 ans[q[cnt].id][0]=R_down; 88 ans[q[cnt].id][1]=L_up+R_up+3*L_down+3*R_down; 89 cnt++; 90 } 91 92 int id=Hash(w[u]); 93 for (int i=0;i<=1;i++) if (e[u][i]) { 94 add(id,1,i); 95 dfs2(e[u][i]); 96 add(id,-1,i); 97 } 98 } 99 100 int main(){101 int t,m;102 scanf("%d",&t);103 while (t--){104 init();105 106 scanf("%d",&n);107 for (int i=1;i<=n;i++) {108 scanf("%d",&w[i]);109 sort_w[i]=w[i];110 }111 sort(sort_w+1,sort_w+n+1);112 113 scanf("%d",&m);114 for (int i=1;i<=m;i++){115 int u,a,b;116 scanf("%d %d %d",&u, &a, &b);117 e[u][0]=a;118 e[u][1]=b;119 }120 121 scanf("%d",&Q);122 for (int i=1;i<=Q;i++){123 scanf("%d%d",&q[i].v,&q[i].x);124 q[i].id=i;125 }126 127 cnt=1;128 dfs1(1);129 130 for (int i=1;i<=Q;i++) q[i].s=pos[q[i].v];131 sort(q+1,q+Q+1);132 133 cnt=1;134 dfs2(1);135 136 for (int i=1;i<=Q;i++){137 if (~ans[i][0]) printf("%d %d\n",ans[i][0],ans[i][1]);138 else puts("0");139 }140 }141 142 return 0;143 }
hdu 4605 Magic Ball Game (在线主席树/离线树状数组)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。