fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  3. #define down(i,a,b) for (int i = (int)a; i >= (int)b; i--)
  4. #define int long long
  5. #define all(x) x.begin(), x.end()
  6. using namespace std;
  7.  
  8. const int maxn = 2e5 + 10;
  9. const int LOG = log2(maxn) + 1;
  10. int a[maxn];
  11. int logg[maxn];
  12. int sp[LOG][maxn];
  13. int n,q;
  14.  
  15. void build_gcd(int n){
  16.     sp[0][1] = a[1];
  17.     up(i,2,n){
  18.         logg[i] = logg[(i >> 1)] + 1;
  19.         sp[0][i] = a[i];
  20.     }
  21.     for (int i = 1; (1 << i) <= n; i++){
  22.         for (int j = 1; j + (1 << i) - 1 <= n; j++){
  23.             sp[i][j] = __gcd(sp[i-1][j], sp[i-1][j + (1 << (i-1))]);
  24.         }
  25.     }
  26. }
  27.  
  28. int get(int l, int r){
  29.     int k = logg[r - l + 1];
  30.     return __gcd(sp[k][l], sp[k][r - (1 << k) + 1]);
  31. }
  32.  
  33. struct Query{
  34.     int d, l, r, type;
  35.     bool operator < (const Query& O){
  36.         if (d == O.d) return type < O.type;
  37.         return d < O.d;
  38.     }
  39. };
  40.  
  41. vector<Query> Q;
  42. int F[maxn];
  43. /**
  44. Gọi F[i] là vị trí xa nhất về phía bên phải của i
  45. F[i] >= i;
  46. sao cho gcd(i, F[i]) <= d
  47. **/
  48.  
  49. int BIT[maxn];
  50. void update(int x, int val){
  51.     while (x <= n){
  52.         BIT[x] += val;
  53.         x += (x & (-x));
  54.     }
  55. }
  56. int get(int x){
  57.     int res = 0;
  58.     while (x){
  59.         res += BIT[x];
  60.         x -= (x & (-x));
  61.     }
  62.     return res;
  63. }
  64.  
  65. void make_prefix_sum(){
  66.     up(i,1,n){
  67.         BIT[i] = BIT[i-1] + n+1;
  68.         F[i] = n+1;
  69.     }
  70.     down(i,n,1){
  71.         BIT[i] -= BIT[i - (i & (-i))];
  72.     }
  73. }
  74.  
  75. void init_offline(){
  76.     up(i,1,n){
  77.         int pos = i;
  78.         up(loop, 0, 29){
  79.             int L = pos;
  80.             int R = n+1;
  81.             int cur_GCD = get(i, pos);
  82.             while (R - L > 1){
  83.                 int MID = (L+R) >> 1;
  84.                 if (get(i, MID) == cur_GCD) L = MID;
  85.                 else R = MID;
  86.             }
  87.             Q.push_back({cur_GCD, i, pos, -1});
  88.             pos = L+1;
  89.             if (pos > n) break;
  90.         }
  91.     }
  92. }
  93.  
  94. int res[maxn];
  95. void solve(){
  96.     for (auto& que : Q){
  97.         int l = que.l;
  98.         int r = que.r;
  99.         int type = que.type;
  100.         if (type < 0){
  101.             update(l, -F[l]);
  102.             F[l] = r;
  103.             update(l, F[l]);
  104.         }
  105.         else{
  106.             int L = l;
  107.             int R = r+1;
  108.             while (R - L > 1){
  109.                 int MID = (L+R) >> 1;
  110.                 if (F[MID] <= r) L = MID;
  111.                 else R = MID;
  112.             }
  113.             if (F[L] > r) res[type] = 0;
  114.             else res[type] = (r + 1)*(L - l + 1) - (get(L) - get(l-1));
  115.         }
  116.     }
  117. }
  118.  
  119. signed main(){
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(0);
  122.     #define Task "A"
  123.     if (fopen(Task".inp", "r")){
  124.         freopen(Task".inp", "r", stdin);
  125.         freopen(Task".out", "w", stdout);
  126.     }
  127.  
  128.     cin >> n >> q;
  129.     up(i,1,n) cin >> a[i];
  130.     build_gcd(n);
  131.  
  132.     init_offline();
  133.     up(i,1,q){
  134.         int l,r,d;
  135.         cin >> l >> r >> d;
  136.         Q.push_back({d, l, r, i});
  137.     }
  138.     sort(all(Q));
  139.  
  140.     make_prefix_sum();
  141.  
  142.     solve();
  143.     up(i,1,q) cout << res[i] << "\n";
  144. }
  145.  
Success #stdin #stdout 0.01s 15960KB
comments (?)
stdin
copy 
6 5
3 9 6 2 8 4
1 5 3
2 4 3
1 5 4
2 6 2
1 6 1
stdout
copy 
12
4
12
9
6
https://ideone.com/6Oq8U6
language:
C++14 (gcc 8.3)
created:
1 year 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!