首页 > 代码库 > HDU 4942 Game on S♂play（线段树、模拟、扩栈）

HDU 4942 Game on S♂play（线段树、模拟、扩栈）

2024-07-17 10:55:29   219人阅读

比赛的时候想到这题的大概做法，但由于卡别的水题。。。就赛后做了。。。

 

题意：给一个二叉树，每个结点有一个w[i]，有3种操作，0 x表示左旋x，1 x表示右旋x，3 x表示询问x结点的价值，其中，价值为x子树结点的累加价值的累乘，其中，结点的累加价值为结点子树的Σw[i]。即询问是，∏Σw。

好像题意被我说得好渣好乱。。。。还是忽略上面2行吧。。。

 

首先，左旋右旋不影响中序遍历的index，即，可以把题目那2个图进行中序遍历，结果都是αXβYγ。由此，可以建立线段树。

而左旋右旋的过程模拟即可，可画示意图，将所有改变的一一写上。

要注意的是记得要改原本x跟父亲那条边，一开始没这个然后RE。。。。

 

  1 #pragma comment (linker,"/STACK:102400000,102400000")  2 #include <cstdio>  3 #include <cstring>  4 #include <iostream>  5 using namespace std;  6   7 #define ll long long  8 #define maxn 100010  9 #define mod 1000000007 10  11 int son[maxn][2]; 12 int fa[maxn]; 13 int idx[maxn]; 14 int real[maxn]; 15 int lr[maxn][2]; 16 int w[maxn]; 17 ll val[maxn]; 18 ll mul[maxn<<2]; 19 void dfs(int x,int& dfn){ 20     val[x] = w[x]; 21     if(son[x][0]) dfs(son[x][0],dfn), lr[x][0]=lr[son[x][0]][0], val[x]+=val[son[x][0]]; 22     else lr[x][0]=dfn+1; 23     idx[x] = ++dfn; 24     real[dfn]=x; 25     if(son[x][1]) dfs(son[x][1],dfn), lr[x][1]=lr[son[x][1]][1], val[x]+=val[son[x][1]]; 26     else lr[x][1]=dfn; 27     val[x]%=mod; 28 } 29 void pushUp(int u){ 30     mul[u] = mul[u<<1]*mul[u<<1|1]%mod; 31 } 32 void build(int u,int l,int r){ 33     if(l==r){ 34         mul[u] = val[real[l]]; 35         return ; 36     } 37     int mid = (l+r)>>1; 38     build(u<<1,l,mid); 39     build(u<<1|1,mid+1,r); 40     pushUp(u); 41 } 42 ll query(int u,int l,int r,int L,int R){ 43     if(l==L&&r==R) return mul[u]; 44     int mid = (l+r)>>1; 45     if(R<=mid) return query(u<<1,l,mid,L,R); 46     else if(L>mid) return query(u<<1|1,mid+1,r,L,R); 47     return query(u<<1,l,mid,L,mid)*query(u<<1|1,mid+1,r,mid+1,R)%mod; 48 } 49 void update(int u,int l,int r,int pos,ll v){ 50     if(l==r){ 51         mul[u] = v; 52         return ; 53     } 54     int mid = (l+r)>>1; 55     if(pos<=mid) update(u<<1,l,mid,pos,v); 56     else update(u<<1|1,mid+1,r,pos,v); 57     pushUp(u); 58 } 59 void LR(int x,int op,int n){ 60     if(son[x][op]==0) return ; 61     int y = son[x][op]; 62     int bb = son[y][op^1], cc=son[y][op]; 63     son[x][op]=bb; 64     fa[bb]=x; 65     int xx=fa[x]; 66     if(son[xx][0]==x) son[xx][0]=y; 67     else son[xx][1]=y; 68     fa[y]=xx; 69     son[y][op^1]=x; 70     fa[x]=y; 71     if(bb) lr[x][op] = lr[bb][op]; 72     else lr[x][op] = idx[x]; 73     lr[y][op^1] = lr[x][op^1]; 74     if(bb) val[x] = val[x]-val[y]+val[bb]; 75     else val[x] = val[x]-val[y]; 76     if(cc) val[y] = val[x]+val[cc]+w[y]; 77     else val[y] = val[x]+w[y]; 78     update(1,1,n,idx[x],val[x]); 79     update(1,1,n,idx[y],val[y]); 80 } 81 int main(){ 82     int t,n,m,ca=0; 83     scanf("%d",&t); 84     while(t--){ 85         printf("Case #%d:\n",++ca); 86         scanf("%d%d",&n,&m); 87         memset(fa,0,sizeof(fa)); 88         son[0][0]=son[0][1]=0; 89         for(int i=1;i<=n;++i){ 90             scanf("%d%d%d",w+i,son[i],son[i]+1); 91             fa[son[i][0]]=fa[son[i][1]]=i; 92         } 93         int dfn=0; 94         dfs(1,dfn); 95         build(1,1,n); 96         for(int i=0;i<m;++i){ 97             int op,x; 98             scanf("%d%d",&op,&x); 99             if(op==2) printf("%I64d\n",query(1,1,n,lr[x][0],lr[x][1]));100             else LR(x,op,n);101         }102     }103     return 0;104 }
View Code

 


联系
我们