fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pub push_back
  7. #define pob pop_back
  8. #define mpa make_pair
  9. #define endl '\n'
  10. #define BIT(i) ((1 << i))
  11. const int maxn = 1e5 + 10;
  12. int n, m, q, a[maxn];
  13. int pos[maxn];
  14. int vt[maxn];
  15. bool check[maxn];
  16. vector<int> luu[maxn];
  17. vector<ll> pre[maxn];
  18. int sz[maxn];
  19. ll get(int i, int time)
  20. {
  21.     int c = pos[i];
  22.     int p = vt[i];
  23.     ll sl = time / sz[c];
  24.     time %= sz[c];
  25.     ll ans = 1ll * pre[c][sz[c]] * sl;
  26.     if(p + time - 1 <= sz[c])
  27.     {
  28.         ans += pre[c][p + time - 1] - pre[c][p - 1];
  29.     }
  30.     else
  31.     {
  32.         ans += pre[c][sz[c]] - pre[c][p - 1];
  33.         ans += pre[c][p + time - 1 - sz[c]];
  34.     }
  35.     return ans;
  36. }
  37. int main()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.     #define code code
  43. //    freopen("code.INP","r",stdin);
  44. //    freopen("code.OUT","w",stdout);
  45.     cin >> n >> m;
  46.     for(int i=1; i<=n; i++) cin >> a[i];
  47.     int cnt = 0;
  48.     for(int i=1; i<=n; i++)
  49.     {
  50.         if(check[a[i]] == true) continue;
  51.         luu[cnt].pub(0);
  52.         int val = a[i];
  53.         while(check[val] == false)
  54.         {
  55.             luu[cnt].pub(val);
  56.             check[val] = true;
  57.             val = a[val];
  58.         }
  59.         cnt++;
  60.     }
  61.     for(int i=0; i<cnt; i++)
  62.     {
  63.         pre[i].pub(0);
  64.         sz[i] = luu[i].size() - 1;
  65.         for(int j=1; j<luu[i].size(); j++)
  66.         {
  67.             pre[i].pub(pre[i][j - 1] + luu[i][j]);
  68.             int x = luu[i][j];
  69.             vt[x] = j;
  70.             pos[x] = i;
  71.         }
  72.     }
  73.     cin >> q;
  74.     while(q--)
  75.     {
  76.         int x, y, l, r;
  77.         cin >> x >> y >> l >> r;
  78.         ll ans = 0;
  79.         for(int i=l; i<=r; i++)
  80.         {
  81.             ans += get(a[i], y) - get(a[i], x - 1);
  82.         }
  83.         cout << ans << endl;
  84.     }
  85.     return 0;
  86. }
Success #stdin #stdout 0.01s 8324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QmZyes
language:
C++14 (clang 8.0)
created:
16 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!