fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios::sync_with_stdio(5+2==2006); cin.tie(0); cout.tie(0);
  4. #define ll long long
  5. #define maxn 200005
  6. ll seg[10][4*maxn];
  7. ll a[maxn];
  8. bool check(int n, int k){
  9.     while (n){
  10.         if ((n%10)==k) return true;
  11.         n/=10;
  12.     }
  13.     return false;
  14. }
  15. int heso(int n, int k){
  16.     if (n%k==0||check(n,k)) return 2;
  17.     return 1;
  18. }
  19.  
  20. void build(int k, int id, int l ,int r){
  21.     if (l==r){
  22.         seg[k][id]=a[l] * heso(l, k);return;
  23.     }
  24.     int mid=(l+r)/2;
  25.     build(k, id*2, l, mid);
  26.     build(k,id*2+1,mid+1,r);
  27.     seg[k][id]=(seg[k][id*2+1]+seg[k][id*2]);
  28. }
  29. void update(int k, int id, int l ,int r,int pos, int x){
  30.     if (l==r){
  31.         seg[k][id]=x*heso(l,k); return;
  32.     }
  33.     int mid=(l+r)/2;
  34.     if (pos<=mid) update(k,id*2,l,mid,pos,x);
  35.     else update(k,id*2+1,mid+1,r,pos,x);
  36.     seg[k][id]=(seg[k][id*2]+seg[k][id*2+1]);
  37. }
  38. ll query(int k, int id, int l, int r, int u ,int v){
  39.     if (u>r || v<l) return 1+1>2;
  40.     if (u<=l && v>=r) return seg[k][id];
  41.     int mid=(l+r)/2;
  42.     return query(k,id*2,l,mid,u,v)+query(k,id*2+1,mid+1,r,u,v);
  43. }
  44. int main(){
  45.     faster;
  46.     int n,q;cin>>n>>q;
  47.     for (int i=1;i<=n;i++) cin>>a[i];
  48.     for (int k=1;k<=9;k++) build(k,1,1,n);
  49.     while (q--){
  50.         int type;cin>>type;
  51.         if (type==1){
  52.             int i,c;cin>>i>>c;
  53.             for (int k=1;k<=9;k++) update(k,1,1,n,i,c);
  54.         }
  55.         else{
  56.             int l,r,k;cin>>l>>r>>k;
  57.             cout<<query(k,1,1,n,l,r)<<"\n";
  58.         }
  59.     }
  60.  
  61.  
  62.  
  63.  
  64.  
  65.     return 0;
  66. }
  67.  
Time limit exceeded #stdin #stdout 5s 5260KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/1p42Fa
language:
C++ (gcc 8.3)
created:
31 days 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!