考虑将两个单词变成有序，我们可以得到一个或者两个旋转次数的区间。
然后考虑将两组单词变成有序，比如[l,mid]和[mid+1,r]，对于mid和mid+1这两个单词我们可以求出使他们有序的旋转次数的区间。
然后将这个区间与[l,mid]的区间以及[mid+1,r]的区间求交，就可以得到使[l,r]有序的旋转次数的区间。
上面这个过程我们可以用分治来进行，区间求交可以用扫描线法。
#include <bits/stdc++.h> using namespace std;vector<int> words[500010]; int cnt[1000010]; int n, c; int tot = 0;void calc(int a, int b) {int idx = 0;while (idx < words[a].size() && idx < words[b].size()){if (words[a][idx] != words[b][idx])break;idx++;}if (idx < words[a].size() && idx < words[b].size()){if (words[a][idx] < words[b][idx]){cnt[0]++;cnt[c - words[b][idx] + 1]--;cnt[c + 1 - words[a][idx]]++;cnt[c]--;tot++;}else{cnt[c + 1 - words[a][idx]]++;cnt[c - words[b][idx] + 1]--;tot++;}}else if (idx == words[a].size() && idx != words[b].size()){cnt[0]++;cnt[c]--;tot++;}else if (idx != words[a].size() && idx == words[b].size())tot++;else{cnt[0]++;cnt[c]--;tot++;} }void divideConquer(int l, int r) {if (l == r)return;int mid = (l + r) >> 1;divideConquer(l, mid);divideConquer(mid + 1, r);calc(mid, mid + 1); }int main() {scanf("%d%d", &n, &c);for (int i = 0; i < n; i++){int l, w;scanf("%d", &l);while (l--){scanf("%d", &w);words[i].push_back(w);}}divideConquer(0, n - 1);bool ok = false;int sum = 0;for (int i = 0; i < c; i++){sum += cnt[i];if (sum == tot){ok = true;printf("%d", i);break;}}if (!ok)printf("-1");return 0; }
