fork download
copy 
  1. /*
  2. ID: untamed
  3. PROG: COOLPROBLEM
  4. LANG: C++
  5. */
  6.  
  7. #include<iostream>
  8. #include<string>
  9.  
  10. using namespace std;
  11.  
  12. string s;
  13.  
  14. int tree[1<<19];
  15. int lazy[1<<19];
  16.  
  17. int n,q;
  18.  
  19. int sum_of_digits(int p)//Returns the sum of digits of a number
  20. {
  21.     int h=0;
  22.     while(p)
  23.     {
  24.         h+=p%10;
  25.         p/=10;
  26.     }
  27.     return h;
  28. }
  29.  
  30. void input()//Reading the string and the number of queries
  31. {
  32.     cin>>s;
  33.     n=s.size();
  34.     s="A"+s;//Let's make it 1-based
  35.     cin>>q;
  36. }
  37.  
  38. void Build_tree(int a, int b, int node)
  39. {
  40.     if(a>b)//Bad
  41.         return;
  42.     if(a==b)//Leaf node
  43.     {
  44.         int d=((s[a]-'0')<<1);//Multiplying the digit by 2
  45.         tree[node]=sum_of_digits(d);
  46.         return;
  47.     }
  48.     Build_tree(a,(a+b)>>1,node<<1);
  49.     Build_tree(((a+b)>>1)+1,b,(node<<1)|1);
  50.     tree[node]=tree[node<<1]+tree[(node<<1)|1];
  51. }
  52.  
  53. void Update_tree(int a, int b, int i, int j, int node, int value)
  54. {
  55.     if(lazy[node])//We have to change all digits to lazy[node]
  56.     {
  57.         tree[node]=(b-a+1)*(lazy[node]<<1);
  58.         if(a!=b)//It has got children
  59.         {
  60.             lazy[node<<1]=lazy[node];
  61.             lazy[(node<<1)|1]=lazy[node];
  62.         }
  63.         lazy[node]=0;
  64.     }
  65.     if(a>b || a>j || b<i)//Out of range
  66.         return;
  67.     if(a>=i && b<=j)//Totally fits in the range
  68.     {
  69.         tree[node]=(b-a+1)*sum_of_digits(value<<1);
  70.         if(a!=b)//It has got children
  71.         {
  72.             lazy[node<<1]=value;
  73.             lazy[(node<<1)|1]=value;
  74.         }
  75.         return;
  76.     }
  77.     Update_tree(a,(a+b)>>1,i,j,node<<1,value);
  78.     Update_tree(((a+b)>>1)+1,b,i,j,(node<<1)|1,value);
  79.     tree[node]=tree[node<<1]+tree[(node<<1)|1];
  80. }
  81.  
  82. int Query_tree(int a, int b, int i, int j, int node)
  83. {
  84.     if(a>b || a>j || b<i)//Out of range
  85.         return 0;
  86.     if(lazy[node])//We have to change all digits to lazy[node]
  87.     {
  88.         tree[node]=(b-a+1)*(lazy[node]<<1);
  89.         if(a!=b)//It has got children
  90.         {
  91.             lazy[node<<1]=lazy[node];
  92.             lazy[(node<<1)|1]=lazy[node];
  93.         }
  94.         lazy[node]=0;
  95.     }
  96.     if(a>=i && b<=j)//Totally fits in the range
  97.         return tree[node];
  98.     int q1,q2;
  99.     q1=Query_tree(a,(a+b)>>1,i,j,node<<1);
  100.     q2=Query_tree(((a+b)>>1)+1,b,i,j,(node<<1)|1);
  101.     return q1+q2;
  102. }
  103.  
  104. void solve()
  105. {
  106.     Build_tree(1,n,1);
  107.     int type,i,a,b,v;
  108.     //type=0 means update
  109.     //type=1 means query
  110.     for(i=1;i<=q;i++)
  111.     {
  112.         cin>>type;
  113.         if(type==0)
  114.         {
  115.             cin>>a>>b>>v;
  116.             a++;b++;//It's 1-based
  117.             Update_tree(1,n,a,b,1,v);
  118.         }
  119.         else
  120.         {
  121.             cout<<Query_tree(1,n,1,n,1)<<'\n';
  122.         }
  123.     }
  124. }
  125.  
  126. int main()
  127. {
  128.     ios_base::sync_with_stdio(false);
  129.     cin.tie(NULL);
  130.     input();
  131.     solve();
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0s 7376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IMmKRa
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!