fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef vector<int> vi;
  6. typedef vector<ll> vll;
  7. #define FOR(i, a) for (int i=0; i<(a); i++)
  8. #define all(x) x.begin(), x.end()
  9. #define gcd __gcd
  10. #define pll pair<ll, ll>
  11. #define pii pair<int, int>
  12. #define fi first
  13. #define se second
  14. //const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
  15.  
  16. const int N = 2e5 + 5, LOG = 18;
  17. int n, q;
  18. int st[N][LOG], lg[N];  // sparse table
  19.  
  20. int f[N];               // f() and fenwick
  21. ll fen[N];
  22.  
  23. vi have[N]; // precompute all possible gcd value
  24.  
  25. int get_gcd(int l, int r){
  26.     int k = lg[r - l + 1];
  27.     return gcd(st[l][k], st[r - (1 << k) + 1][k]);
  28. }
  29.  
  30. void build_st(){
  31.     lg[1] = 0;
  32.     for(int i = 2; i <= n; ++i)
  33.         lg[i] = lg[i / 2] + 1;
  34.  
  35.     for(int j = 1; j < LOG; ++j)
  36.         for(int i = 1; i + (1 << j) - 1 <= n; ++i)
  37.             st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  38. }
  39.  
  40. inline void upd_fen(int id, int val){
  41.     for(; id <= n; id += id & -id)
  42.         fen[id] += val;
  43. }
  44.  
  45. inline ll get(int id){
  46.     ll ans = 0;
  47.     for(; id > 0; id -= id & -id)
  48.         ans += fen[id];
  49.     return ans;
  50. }
  51.  
  52. inline ll sum(int l, int r){
  53.     return get(r) - get(l - 1);
  54. }
  55.  
  56. void upd(int id, int val){
  57.     upd_fen(id, val - f[id]);
  58.     f[id] = val;
  59. }
  60.  
  61. int main(){
  62.     ios_base::sync_with_stdio(0);
  63.     cin.tie(0);
  64.     cin >> n >> q;
  65.     for(int i = 1; i <= n; ++i)
  66.         cin >> st[i][0];
  67.  
  68.     build_st();
  69.  
  70.     vector<array<int, 4>> query(q);
  71.     vll ans(n);
  72.  
  73.     FOR(i, q){
  74.         int l, r, d; cin >> l >> r >> d;
  75.         query[i] = {d, l, r, i};
  76.     }
  77.  
  78.     sort(all(query));
  79.  
  80.     vector<pii> possible;
  81.  
  82.     for(int i = 1; i <= n; ++i){
  83.         have[i].push_back(0);
  84.         int pos = i;
  85.         while(pos <= n){
  86.             have[i].push_back(pos);
  87.             int cur = get_gcd(i, pos);
  88.             possible.emplace_back(cur, i);
  89.             int lo = pos, hi = n;
  90.             while(lo <= hi){
  91.                 int mid = (lo + hi) / 2;
  92.                 if(get_gcd(i, mid) == cur){
  93.                     pos = mid;
  94.                     lo = mid + 1;
  95.                 }
  96.                 else hi = mid - 1;
  97.             }
  98.             pos++;
  99.         }
  100.     }
  101.  
  102.     sort(all(possible)); reverse(all(possible));
  103.  
  104.     for(int i = 1; i <= n; ++i)
  105.         upd(i, have[i].back());
  106.  
  107.     for(auto &it : query){
  108.         int d = it[0], l = it[1], r = it[2], id = it[3];
  109.  
  110.         while(possible.size()){
  111.             auto it = possible.back();
  112.             int val = it.fi, id = it.se;
  113.             if(val > d) break;
  114.             upd(id, have[id].back());
  115.             possible.pop_back();
  116.             have[id].pop_back();
  117.         }
  118.  
  119.         int lo = l, hi = r, pos = -1;
  120.         while(lo <= hi){
  121.             int mid = (lo + hi) / 2;
  122.             if(get_gcd(mid, f[mid]) <= d){
  123.                 pos = mid;
  124.                 lo = mid + 1;
  125.             }
  126.             else hi = mid - 1;
  127.         }
  128.  
  129.         if(pos == -1) continue;
  130.         int actual_r = pos;
  131.  
  132.         lo = l, hi = actual_r, pos = -1;
  133.         while(lo <= hi){
  134.             int mid = (lo + hi) / 2;
  135.             if(f[mid] <= r){
  136.                 pos = mid;
  137.                 lo = mid + 1;
  138.             }
  139.             else hi = mid - 1;
  140.         }
  141.  
  142.         if(pos != -1)
  143.             ans[id] = (r + 1) * 1LL * (pos - l + 1) - sum(l, pos);
  144.     }
  145.  
  146.     FOR(i, q) cout << ans[i] << "\n";
  147.  
  148.     return 0;
  149. }
Success #stdin #stdout 0.01s 11024KB
comments (?)
stdin
copy 
0 0
stdout
copy 
Standard output is empty
https://ideone.com/nx6E8l
language:
C++14 (clang 8.0)
created:
2 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!