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

  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 }