G8004 [GESP202403 八级] 接竹竿 题解

知识点：栈、倍增、预处理、区间查询。

解题思路

预处理每个位置右侧下一张同点数牌的位置，jump[0][i]指向该位置后一格，表示从空栈出发的一整段被消去。倍增跳过连续可消去段，区间内无法消去的首张记为一张残留并继续。

为什么正确

从首张到下张同点数之间无相同首牌，后者到来时会把这一整段从栈中移除；无法匹配的首牌永久保留，递归处理后缀即可。残留牌点数互异，最多13张。

易错点

倍增落点可为r+1，表示正好消光；点数范围1到13是查询循环次数上界的重要前提。

复杂度

预处理O(n log n)，每次查询O(13 log n)，空间O(n log n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--) {
        int n;
        cin>>n;
        vector<int>a(n+2);
        for(int i=1;i<=n;i++)cin>>a[i];
        int lg=1;
        while((1<<lg)<=n+2)lg++;
        vector<vector<int>>jump(lg,vector<int>(n+3,n+2));
        vector<int>last(14,n+1);
        for(int i=n;i>=1;i--) {
            jump[0][i]=last[a[i]]+1;
            last[a[i]]=i;
        }
        for(int k=1;k<lg;k++)for(int i=1;i<=n+2;i++)         jump[k][i]=jump[k-1][jump[k-1][i]];
        int q;
        cin>>q;
        while(q--) {
            int l,r;
            cin>>l>>r;
            int x=l,answer=0;
            while(x<=r) {
                for(int k=lg-1;k>=0;k--)if(jump[k][x]<=r+1)x=jump[k][x];
                if(x<=r) {
                    answer++;
                    x++;
                }
            }
            cout<<answer<<"\n";
        }
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。