#include #include #include #include using namespace std; #define int long long //区間内の最小値、最大値のインデックスを持つテーブル struct sparce_table { vector A, B, log_table; vector> tableA, tableB; int N; sparce_table(int n) { N = n; A.resize(N-1); B.resize(N-1); //for (int i = 0; i < N; i++)cin >> A[i]; //for (int i = 0; i < N; i++)cin >> B[i]; //対数計算は先にやっておく log_table.resize(N); for (int i = 2; i < N; i++) { log_table[i] = log_table[i >> 1] + 1; } tableA.resize(N-1); tableB.resize(N-1); for (int i = 0; i < N-1; i++) { tableA[i].resize(log_table[N-1] + 1); tableB[i].resize(log_table[N-1] + 1); } //区間[i,i] for (int i = 0; i < N-1; i++) { tableA[i][0] = i; tableB[i][0] = i; } } void update(){ //区間[i,i+2^k)の計算 for (int k = 1; (1 << k) <= N-1; k++) { for (int i = 0; i + (1 << k) <= N-1; i++) { //区間[i,i+2^(k-1))と区間[i+2^(k-1),i+2^k)の最小値、最大値のインデックス int firstA = tableA[i][k - 1]; int secondA = tableA[i + (1 << (k - 1))][k - 1]; int firstB = tableB[i][k - 1]; int secondB = tableB[i + (1 << (k - 1))][k - 1]; //最後に出てきた最大値 if (A[firstA] > A[secondA]) { tableA[i][k] = firstA; } else { tableA[i][k] = secondA; } //最後に出てきた最小値 if (B[firstB] < B[secondB]) { tableB[i][k] = firstB; } else { tableB[i][k] = secondB; } } } } void push(int k, int a) { B[k] = a; } //区間[s,t]内の最小値、最大値のインデックスを返す int query(int s, int t) { int d = t - s + 1; int k = log_table[d]; pairres = make_pair(0, 0); //区間[s,t]は区間[s,s+2^k)と[t-2^k+1,t)でカバーできる if (A[tableA[s][k]] > A[tableA[t - (1 << k) + 1][k]]) { res.first = tableA[s][k]; } else { res.first = tableA[t - (1 << k) + 1][k]; } if (B[tableB[s][k]] < B[tableB[t - (1 << k) + 1][k]]) { res.second = tableB[s][k]; } else { res.second = tableB[t - (1 << k) + 1][k]; } return B[res.second]; } }; vector> ready(int n, int M, int x, int d) { vector>ij(M); for (int k = 0; k ij[k].second) { swap(ij[k].first, ij[k].second); } else { ij[k].second = ij[k].second + 1; } x = (x + d) % (n * (n - 1)); } return ij; } signed main() { int N; cin >> N; vector>S(N); for (int i = 0; i> S[i].first; S[i].second = i; } int M, x, d; cin >> M >> x >> d; long long sum = 0; vector>ij = ready(N, M, x, d); sort(S.begin(), S.end()); vectororder(N); for (int i = 0; i < N; i++) { order[S[i].second] = i; } sparce_table st(N); for (int i = 0; i < N - 1; i++) { bool flag = true; for (int j = 0; j < min(S[i].first.size(), S[i + 1].first.size());j++) { if (S[i].first[j] != S[i + 1].first[j]) { st.push(i, j); flag = false; break; } } if (flag)st.push(i, min(S[i].first.size(), S[i + 1].first.size())); } st.update(); for (int k = 0; k j)swap(i, j); sum += st.query(i, j-1); } cout << sum << endl; return 0; }