#include #include #include #include #include #include #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i)) #define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) using ll = long long; using namespace std; template struct sparse_table { typedef typename Monoid::type T; vector > table; Monoid mon; sparse_table(vector const & init, Monoid const & a_mon = Monoid()) : mon(a_mon) { int n = init.size(); int log_n = sqrt(n) + 1; table.resize(log_n, vector(n, mon.unit)); table[0] = init; for (int k = 0; k < log_n-1; ++ k) { for (int i = 0; i < n; ++ i) { table[k+1][i] = mon.append(table[k][i], i + (1ll<> n; vector s(n); repeat (i,n) cin >> s[i]; int m; ll x, d; cin >> m >> x >> d; // generate queries vector qi(m); vector qj(m); repeat (k,m) { qi[k] = x / (n - 1); qj[k] = x % (n - 1); if (qi[k] > qj[k]) { swap(qi[k], qj[k]); } else { qj[k] += 1; } x = (x + d) % (n *(ll) (n - 1)); } // construct a sparse table vector rank(n); whole(iota, rank, 0); whole(sort, rank, [&](int i, int j) { return s[i] < s[j]; }); vector lcp_0(n-1); repeat (i,n-1) lcp_0[i] = compute_lcp(s[rank[i]], s[rank[i+1]]); sparse_table table(lcp_0); vector rank_of(n); repeat (i,n) rank_of[rank[i]] = i; // compute ll result = 0; repeat (q,m) { int l = rank_of[qi[q]]; int r = rank_of[qj[q]]; if (l > r) swap(l, r); result += table(l, r); } // output cout << result << endl; return 0; }