题解：P10264 [GESP202403 八级]接竹竿

wrh316 · 2024-03-23 12:01:34 · 题解

备注：因为加强数据后我的题解不能通过，所以优化后重新提交审核。

这道题类似滑动窗口。

思路：初始化 f _ {x} 和 r _ {f _ {x}} 数组为 i，q 次查询，每次遍历 x 至 y，如果 r _{i} 不在 x 至 y 范围内，计数器 ans \gets ans+1，否则跳到 r _ {i}。

上代码：

#include <bits/stdc++.h>
#define int register unsigned
using namespace std;
//define 是二重优化
unsigned t,n,q;
signed main(){
    //第一优化
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        int f[15] = {0},r[150005] = {0};//r[i]表示第i个元素在其后第一次出现的位置，f[i]表示第i个元素当前出现的位置
        for(int i = 1,x;i <= n;i++){
            cin>>x;
            r[f[x]] = i;
            f[x] = i;
        }
        cin>>q;
        while(q--){
            int x,y;
            cin>>x>>y;
            int ans = 0;
            for(int i = x;i <= y;i++){
                if(r[i] < x || r[i] > y) ans++;//不在范围内
                else i = r[i]; //快速地跳
            }
            cout<<ans<<"\n";
        }
    }
    return 0;
}