fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define name "test"
  4. #define FOR(i, a, b) for (int i = a; i <= b; i++)
  5. #define ll long long
  6. #define int ll
  7.  
  8. using namespace std;
  9.  
  10. const int N = 1e5 + 5;
  11. int a[N], n, m;
  12. int vis[N], cyc[N], pos_cyc[N];
  13. vector<vector<int>> cycles;
  14. vector<vector<ll>> pre;
  15. vector<ll> sum;
  16.  
  17. void nhap() {
  18.     cin >> n >> m;
  19.     FOR(i, 1, n) cin >> a[i];
  20. }
  21.  
  22. int calc(int zi, int zf, int cl, int cr) {
  23.     int ans = 0;
  24.     int L = zf - zi + 1;
  25.     FOR(i, cl, cr) {
  26.         int id = cyc[i];
  27.         int pos = pos_cyc[i];
  28.         int k = cycles[id].size();
  29.         ans += (L / k) * sum[id];
  30.         int rem = L % k;
  31.         int st = 1 + (pos + (zi - 1) % k) % k;
  32.         if (rem) {
  33.             if (st + rem <= k) ans += pre[id][st + rem] - pre[id][st];
  34.             else ans += (pre[id][k] - pre[id][st]) + pre[id][(st + rem) % k];
  35.         }
  36.     }
  37.     return ans;
  38. }
  39.  
  40. void giai() {
  41.     int q; cin >> q;
  42.     while(q--) {
  43.         int zi, zf, cl, cr;
  44.         cin >> zi >> zf >> cl >> cr;
  45.         cout << calc(zi, zf, cl, cr) << '\n';
  46.     }
  47. }
  48.  
  49. void init() {
  50.     int idx = 0;
  51.     FOR(i, 1, n) if (!vis[i]) {
  52.         vector<int> tmp;
  53.         int x = i;
  54.         while (!vis[x]) {
  55.             vis[x] = 1;
  56.             tmp.push_back(x);
  57.             x = a[x];
  58.         }
  59.         cycles.push_back(tmp);
  60.         int k = tmp.size();
  61.         FOR(j, 0, k-1) {
  62.             cyc[tmp[j]] = idx;
  63.             pos_cyc[tmp[j]] = j;
  64.         }
  65.         pre.push_back(vector<int>(k+1, 0));
  66.         FOR(j, 0, k-1) pre[idx][j+1] = pre[idx][j] + tmp[j];
  67.         sum.push_back(pre[idx][k]);
  68.         idx++;
  69.     }
  70. }
  71.  
  72. signed main() {
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0); cout.tie(0);
  75.  
  76.     if (fopen(name".inp", "r")) {
  77.         freopen(name".inp", "r", stdin);
  78.         freopen(name".out", "w", stdout);
  79.     }
  80.  
  81.     nhap();
  82.     init();
  83.     giai();
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/FbNuij
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!