fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define LOG 20
  4. #define MASK(i) (1LL<<(i))
  5. #define BIT(x,i) (((x)>>(i))&1)
  6. #define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask))
  7. #define ERASE_BIT(mask) (mask)^((mask)&(-mask))
  8. #define left _left
  9. #define right _right
  10. #define task "t"
  11. using namespace std;
  12. const ll INF=1e18;
  13. const int iat=2e5+9;
  14. const int mod=1e9+7;
  15. const int MAX=15e5;
  16. void fast_IO()
  17. {
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(0);
  20.     cout.tie(0);
  21.     if(fopen(task".inp","r"))
  22.     {
  23.         freopen(task".inp","r",stdin);
  24.         freopen(task".out","w",stdout);
  25.     }
  26. }
  27. int n,q,a[iat];
  28. ll ans[iat];
  29. vector <int> needUpdate[iat];
  30. struct Query
  31. {
  32.     int l,r,d,id;
  33.     bool operator < (const Query &other) const
  34.     {
  35.         return d>other.d;
  36.     }
  37. }query[iat];
  38. struct Fenwick
  39. {
  40.     ll bit[iat];
  41.     void update(int pos, int val)
  42.     {
  43.         for(int i=pos; i<=n; i+=i&-i)bit[i]+=val;
  44.     }
  45.     ll get_sum(int pos)
  46.     {
  47.         ll res=0;
  48.         for(int i=pos; i>0; i-=i&-i)res+=bit[i];
  49.         return res;
  50.     }
  51.     ll get_sum(int l, int r)
  52.     {
  53.         return get_sum(r)-get_sum(l-1);
  54.     }
  55. }tree;
  56. struct RMQ
  57. {
  58.     int rmq[iat][LOG];
  59.     void preprocess()
  60.     {
  61.         for(int i=1; i<=n; i++)rmq[i][0]=a[i];
  62.         for(int j=1; j<LOG; j++)
  63.         {
  64.             for(int i=1; i+MASK(j-1)-1<=n; i++)rmq[i][j]=__gcd(rmq[i][j-1],rmq[i+MASK(j-1)][j-1]);
  65.         }
  66.     }
  67.     int get_gcd(int l, int r)
  68.     {
  69.         int k=__lg(r-l+1);
  70.         return __gcd(rmq[l][k],rmq[r-MASK(k)+1][k]);
  71.     }
  72. }RMQ;
  73. signed main()
  74. {
  75.     fast_IO();
  76.     cin>>n>>q;
  77.     for(int i=1; i<=n; i++)cin>>a[i],needUpdate[1].push_back(i);
  78.     for(int i=1; i<=q; i++)cin>>query[i].l>>query[i].r>>query[i].d,query[i].id=i;
  79.     sort(query+1,query+q+1);
  80.     RMQ.preprocess();
  81.     for(int i=1; i<=q; i++)
  82.     {
  83.         for(int j : needUpdate[i])
  84.         {
  85.             int pos=j;
  86.             for(int k=LOG-1; k>=0; k--)
  87.             {
  88.                 if(pos+MASK(k)<=n && RMQ.get_gcd(j,pos+MASK(k))>query[i].d)pos+=MASK(k);
  89.             }
  90.             if(RMQ.get_gcd(j,pos)>query[i].d)pos++;
  91.             if(pos<=n)
  92.             {
  93.                 int tmp=RMQ.get_gcd(j,pos);
  94.                 int l=i+1,r=q,res=-1;
  95.                 while(l<=r)
  96.                 {
  97.                     int mid=(l+r)/2;
  98.                     if(query[mid].d<tmp)res=mid,r=mid-1;
  99.                     else l=mid+1;
  100.                 }
  101.                 if(res!=-1)needUpdate[res].push_back(j);
  102.             }
  103.             tree.update(j,pos-tree.get_sum(j,j));
  104.         }
  105.         int l=query[i].l,r=query[i].r,pos=-1;
  106.         while(l<=r)
  107.         {
  108.             int mid=(l+r)/2;
  109.             if(tree.get_sum(mid,mid)<=query[i].r)pos=mid,l=mid+1;
  110.             else r=mid-1;
  111.         }
  112.         if(pos!=-1)
  113.         {
  114.             l=query[i].l,r=query[i].r;
  115.             ans[query[i].id]+=1LL*(r+1)*(pos-l+1)-(tree.get_sum(l,pos));
  116.         }
  117.     }
  118.     for(int i=1; i<=q; i++)cout<<ans[i]<<'\n';
  119. }
Success #stdin #stdout 0s 9648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4iiBLJ
language:
C++14 (gcc 8.3)
created:
20 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!