【模拟 + 离线】CF1719 C

喜欢ヅ旅行 2024-03-23 19:46 5阅读 0赞

[Problem - C - Codeforces][]

题意：

![9abf9ba5e4b54603a679589d25f8b02d.png][]

![744ad23a39974f63a4841cb9e35a21ab.png][]

思路：

手摸以下样例容易发现

对于最大值左边的数，答案可以直接模拟轮数得到

对于最大值，答案直接就是pos

对于最大值右边的数，答案就是0

接下来就是如何模拟轮数的问题了

一开始开了个前缀和数组直接模拟然后统计，T了，因为空间直接是N\*Q的

所以我们需要离线

离线操作，其实就是把询问保存下来，按关键字排序，然后按关键字模拟，保存答案

这道题我们按轮数模拟，因此我们可以把询问保存下来，按轮数排序

然后用双端队列模拟的过程中统计答案，用指针idx指向当前是哪个询问，然后idx ++保存答案

模拟完n轮之后，可能会有询问的轮数很大，因此需要额外处理这些轮数很大的询问

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int a[N], ans[N];
    
    void solve() {
        int n, Q;
        cin >> n >> Q;
        for (int i = 1; i <= n; i ++) {
            cin >> a[i];
            ans[i] = 0;
        }
    
        vector<array<int, 3> > q;
        for (int i = 1; i <= Q; i ++) {
            int x, k;
            cin >> x >> k;
            q.push_back({k, x, i});
        }
    
        sort(q.begin(), q.end());
    
        int idx = 0;
        deque<int> d;
        for (int i = 1; i <= n; i ++) {
            d.push_back(i);
        }
    
        vector<int> win(n + 1, 0);
        for (int i = 1; i <= n; i ++) {
            int x = d.front();
            d.pop_front();
            int y = d.front();
            d.pop_front();
            if (a[x] < a[y]) swap(x, y);
            win[x] ++;
            d.push_front(x);
            d.push_back(y);
            while (idx < Q && q[idx][0] == i) {
                ans[q[idx][2]] = win[q[idx][1]];
                idx ++;
            }
        }
    
        while(idx < Q) {
            auto [k, x, id] = q[idx];
            if (x != d.front()) {
                ans[id] = win[x];
            }else {
                ans[id] = win[x] + k - n;
            }
            idx ++;
        }
        for (int i = 1; i <= Q; i ++) {
            cout << ans[i] << "\n";
        }
    }
    signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int t = 1;
        cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1719/problem/C
[9abf9ba5e4b54603a679589d25f8b02d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6ee4c04de7e544cd85211870d56566e9.png
[744ad23a39974f63a4841cb9e35a21ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/50ab845c27714b5ba19d1629f2b9be7c.png