【2025牛客暑期多校训练营9】L Ping Pong

由读题和打表发现，最后一定会形成一个循环，那么可以用字符串哈希来记录每次队列状态，遇到重复状态就代表找到循环节，记录下循环开始的地方和循环节长度。然后处理一下循环节开始之前和结束之后的地方就完成了。

#include <bits/stdc++.h>// from: cpp.json
#define INF 8e18
#define LD long double
#define i128 __int128_t
#define int long long
using namespace std;
using ull = unsigned long long;
using u128 = __uint128_t;const ull BASE = 114514191981ULL;
const ull C1 = 1000003ULL, C2 = 1000000009ULL;void solve() {int n, k;cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}deque<int> q;for (int i = 1; i < n; i++) {q.push_back(i);}int cur = 0;int cnt = 0;vector<int> ans(n);int m = n - 1;vector<ull> pw(m);pw[0] = 1ULL;for (int i = 1; i < m; i++) {pw[i] = (u128) pw[i - 1] * (u128) BASE;}u128 h = 0;for (int i = 0; i < m; i++) {int val = q[i];u128 add = (u128) val * (u128) pw[m - 1 - i];h += add;}auto update = [&](int popv, int pushv) {u128 sub = (u128) popv * (u128) pw[m - 1];h -= sub;u128 tmp = (u128) h * (u128) BASE + (u128) pushv;h = tmp;};vector<pair<int, int>> eve;auto run = [&]() -> void {int ft = q.front();q.pop_front();eve.emplace_back(cur, ft);if (cnt == n - 1) {q.push_back(cur);update(ft, cur);cur = ft;cnt = 1;} else {if (a[cur] > a[ft]) {q.push_back(ft);update(ft, ft);cnt++;} else {q.push_back(cur);update(ft, cur);cur = ft;cnt = 1;}}};unordered_map<ull, int> vis;int s = 0, start = -1, len = -1;while (s < k) {ull key = h ^ ((ull)cur * C1) ^ ((ull)cnt * C2);auto it = vis.find(key);if (it != vis.end()) {start = it->second;len = s - start;break;}vis[key] = s;run();s++;}if (start == -1) {int siz = eve.size();for (int i = 0; i < siz; i++) {ans[eve[i].first]++;ans[eve[i].second]++;}for (int i = 0; i < n; i++) {cout << ans[i] << ' ';}cout << '\n';return;}for (int i = 0; i < start; i++) {ans[eve[i].first]++;ans[eve[i].second]++;}vector<int> cycle(n);for (int i = start; i < start + len; i++) {cycle[eve[i].first]++;cycle[eve[i].second]++;}int need = k - start;int full = need / len;int res = need % len;for (int i = 0; i < n; i++) {ans[i] += cycle[i] * full;}for (int i = 0; i < res; i++) {int idx = i + start;ans[eve[idx].first]++;ans[eve[idx].second]++;}for (int i = 0; i < n; i++) {cout << ans[i] << ' ';}cout << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}