【DFS序+树状数组】BNUOJ 52733 Random Numbers

http://acm.bnu.edu.cn/v3/problem_show.php?pid=52733

【题意】

给定一棵树，这棵树每个点都有一个点权，标号从0开始，0是根结点
修改操作：
```
SEED 1 13
```
把结点1的点权乘上13
查询操作：
```
RAND 1
```
查询结点1为根的子树所有结点权的总乘积，以及这个总乘积有多少个因子
题目保证结果的质因子最大为13

【思路】

质因子最大为13，那么我们可以枚举质因子2 3 5 7 11 13，共6个
只要我们知道子树乘积这六个质因子的个数，我们就能算出子树的总乘积为2^p1*3^p2*5^p3*7^p4*11^p5*13^p6,而且这个数共有(p1+1)*(p2+1)*(p3+1)*(p4+1)*(p5+1)*(p6+1)个因子
我们可以为每个质因子维护一个树状数组，统计因子个数和

【AC】

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;;

 const int maxm=*maxn;

 const ll mod=1e9+;

 int n;

 struct edge

 {

     int to;

     int nxt;

 }e[maxm];

 int head[maxn];

 int tot;

 int l[maxn],r[maxn];

 int cid;

 ll tree[][maxm];

 int p[];

 ll fpow(ll x,ll n)

 {

     ll res=;

     while(n)

     {

         if(n&) res=(res*x)%mod;

         x=(x*x)%mod;

         n>>=;

     }

     return res;

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 void add(int i,int k,int cnt)

 {

     while(k<=cid)

     {

         tree[i][k]+=cnt;

         k+=lowbit(k);

     }

 }

 ll query(int i,int k)

 {

     int res=;

     while(k)

     {

         res+=tree[i][k];

         k-=lowbit(k);

     }

     return res;

 }

 void init()

 {

     memset(head,-,sizeof(head));

     tot=;

     cid=;

     memset(tree,,sizeof(tree));

 }

 void addedge(int u,int v)

 {

     e[tot].to=v;

     e[tot].nxt=head[u];

     head[u]=tot++;

 }

 void dfs(int u,int pa)

 {

     l[u]=++cid;

     for(int i=head[u];i!=-;i=e[i].nxt)

     {

         int v=e[i].to;

         if(v==pa) continue;

         dfs(v,u);

     }

     r[u]=++cid;

 }

 void update(int i,ll x)

 {

     for(int j=;j<=;j++)

     {

         int cnt=;

         while(x%p[j]==)

         {

             cnt++;

             x/=p[j];

         }

         add(j,l[i],cnt);

     }

 }

 int main()

 {

     p[]=,p[]=,p[]=,p[]=,p[]=,p[]=;

     while(~scanf("%d",&n))

     {

         init();

         int u,v;

         for(int i=;i<=n-;i++)

         {

             scanf("%d%d",&u,&v);

             u++;v++;

             addedge(u,v);

             addedge(v,u);

         }

         dfs(,-);

         for(int i=;i<=n;i++)

         {

             ll x;

             scanf("%I64d",&x);

             update(i,x);

         }

         int q;

         scanf("%d",&q);

         char str[];

         while(q--)

         {

             scanf("%s",str);

             if(str[]=='R')

             {

                 int x;

                 scanf("%d",&x);

                 x++;

                 ll cnt=;

                 ll ans=;

                 for(int i=;i<=;i++)

                 {

                     int tmp=query(i,r[x])-query(i,l[x]-);

                     cnt=cnt*(ll)(tmp+)%mod;

                     ans=(ans*fpow(p[i],tmp))%mod;

                 }

                 printf("%I64d %d\n",ans,cnt);

             }

             else

             {

                 int k;

                 ll x;

                 scanf("%d%I64d",&k,&x);

                 k++;

                 update(k,x);

             } 

         }

     }

     return ;

 }

树状数组

巴特西

【DFS序+树状数组】BNUOJ 52733 Random Numbers

最新文章

热门文章