fork download
copy 
  1. ///TRAN THAI BAO :3
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8.  
  9. using namespace std;
  10.  
  11. #define maxN 200007
  12. long long ans[maxN] = {0};
  13. long long BIT[maxN] = {0};
  14. int n, m;
  15. int p[maxN];
  16. int pos[maxN];
  17. vector<int>divs[maxN];
  18.  
  19. void add(int x, int val)
  20. {
  21.     for(; x <= n; x += (x & -x))
  22.         BIT[x] += val;
  23. }
  24.  
  25. long long sum(int x)
  26. {
  27.     long long ans = 0;
  28.     for(; x > 0; x -= (x & -x))
  29.         ans += BIT[x];
  30.     return ans;
  31. }
  32.  
  33. struct que
  34. {
  35.     int l, r, id;
  36.     bool operator < (const que &other) const
  37.     {
  38.         if(r != other.r) return r < other.r;
  39.         return l < other.l;
  40.     }
  41. };
  42. que q[maxN];
  43.  
  44. void solve()
  45. {
  46.     cin >> n >> m;
  47.     for(int i = 1; i <= n; i++)
  48.     {
  49.         cin >> p[i];
  50.         pos[p[i]] = i;
  51.     }
  52.     for(int i = 1; i <= n; i++)
  53.         for(int d = i; d <= n; d+=i)
  54.             divs[d].push_back(i);
  55.     for(int i = 1; i <= m; i++)
  56.     {
  57.         cin >> q[i].l >> q[i].r;
  58.         q[i].id = i;
  59.     }
  60.     sort(q+1, q+m+1);
  61.     int cur = 0;
  62.     for(int i = 1; i <= m; i++)
  63.     {
  64.         while(cur < q[i].r)
  65.         {
  66.             cur++;
  67.             for(int j = 0; j < divs[p[cur]].size(); j++)
  68.             {
  69.                 int pPos = pos[divs[p[cur]][j]];
  70.                 if(pPos <= cur)
  71.                     add(pos[divs[p[cur]][j]], 1);
  72.             }
  73.         }
  74.         ans[q[i].id] = sum(q[i].r) - sum(q[i].l-1);
  75.     }
  76.     for(int i = 1; i <= m; i++)
  77.         cout << ans[i] << '\n';
  78. }
  79.  
  80. int main()
  81. {
  82.     ios_base::sync_with_stdio(0);
  83.     cin.tie(0);
  84.     cout.tie(0);
  85.     solve();
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 9696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cy0aVo
language:
C++14 (gcc 8.3)
created:
10 hours 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!