fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,q,a[100005],lz[400005],st[18][400005];
  4. void BUILD(int id, int l, int r, int i, int v)
  5. {
  6.     if (l>i || r<i) return;
  7.     else if (l==r) 
  8.     {
  9.         st[v][id]++;
  10.         return;
  11.     }
  12.     int mid=(l+r)/2;
  13.     if (i<=mid) BUILD(id*2,l,mid,i,v);
  14.     else BUILD(id*2+1,mid+1,r,i,v);
  15.     st[v][id]=st[v][id*2]+st[v][id*2+1];
  16. }
  17. void UPDATE(int id, int l, int r, int u, int v)
  18. {
  19.     if (l>v || r<u) return;
  20.     if (l>=u && r<=v)
  21.     {
  22.         int temp=st[9][id];
  23.         for (int i=9;i>=1;i--) st[i][id]=st[i-1][id];
  24.         st[0][id]=temp,lz[id]=(lz[id]+1)%10;
  25.         return;
  26.     }
  27.     int mid=(l+r)/2;
  28.     if (lz[id]) 
  29.     {
  30.         for (int i=1;i<=lz[id];i++)
  31.         {
  32.             int templ=st[9][id*2],tempr=st[9][id*2+1];
  33.             for (int j=9;j>=1;j--) st[j][id*2]=st[j-1][id*2],st[j][id*2+1]=st[j-1][id*2+1];
  34.             st[0][id*2]=templ,st[0][id*2+1]=tempr;
  35.         }
  36.         lz[id*2]=(lz[id*2]+lz[id])%10,lz[id*2+1]=(lz[id*2+1]+lz[id])%10,lz[id]=0;
  37.     }
  38.     UPDATE(id*2,l,mid,u,v),UPDATE(id*2+1,mid+1,r,u,v);
  39.     for (int i=0;i<=9;i++) st[i][id]=st[i][id*2]+st[i][id*2+1];
  40. }
  41. int GET(int id, int l, int r, int u, int v)
  42. {
  43.     if (l>v || r<u) return 0;
  44.     else if (l>=u && r<=v)
  45.     {
  46.         int res=0;
  47.         for (int i=1;i<=9;i++) res+=i*st[i][id];
  48.         return res;
  49.     }
  50.     int mid=(l+r)/2;
  51.     if (lz[id]) 
  52.     {
  53.         for (int i=1;i<=lz[id];i++)
  54.         {
  55.             int templ=st[9][id*2],tempr=st[9][id*2+1];
  56.             for (int j=9;j>=1;j--) st[j][id*2]=st[j-1][id*2],st[j][id*2+1]=st[j-1][id*2+1];
  57.             st[0][id*2]=templ,st[0][id*2+1]=tempr;
  58.         }
  59.         lz[id*2]=(lz[id*2]+lz[id])%10,lz[id*2+1]=(lz[id*2+1]+lz[id])%10,lz[id]=0;
  60.     }
  61.     return GET(id*2,l,mid,u,v)+GET(id*2+1,mid+1,r,u,v);
  62. }
  63. signed main()
  64. {
  65.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  66.     cin>>n>>q;
  67.     for (int i=1;i<=n;i++) cin>>a[i];
  68.     for (int i=1;i<=n;i++) BUILD(1,1,n,i,a[i]);
  69.     for (int i=1;i<=q;i++)
  70.     {
  71.         int l,r;
  72.         cin>>l>>r;
  73.         cout<<GET(1,1,n,l,r)<<'\n';
  74.         UPDATE(1,1,n,l,r);
  75.     }
  76.     return 0;
  77. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/W0Ox6G
language:
C++14 (gcc 8.3)
created:
1 day 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!