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

· · 题解

来自搬题人的题解。

形式化题意：定义一个序列的权值为，维护一个栈，使得每次从序列中取一个元素，如果这个元素在栈中，弹栈弹到这个元素不在栈中为止，否则加入这个栈，最后栈中的元素个数，现在给定一个序列，多次询问这个序列一个子段的权值。

这个形式化题意并没有比题面简化多少，但已经把暴力的写法说清楚了，现在考虑优化，观察下面这个序列：

11 1 2 3 4 5 6 7 8 9 10 1 12

发现两个 1 之间的元素没有贡献，直接跳过即可，这启示我们可以用链表维护下一个和这个元素相等的元素来跳过元素，每次如果能跳，就跳到下一个当前元素的下一个位置，然后假装什么也没发生过，否则答案加一。

这样时间复杂度是不对的，我们改变一下对 nxt 的定义，定义 nxt_{i,j} 为从 i 起进行 2^j 次操作后的位置，这样时间复杂度就能优化到 O(V\log n)。

有人可能会问，为什么不直接跳到最后一个，我跳到最后一个赛时过了，来，我给你看组 hack。

1 
8
1 2 3 1 2 3 1 2
1
1 8

手动模拟一下，答案为 0，但是跳到最后一个的话，我们会把前 7 个全都弹掉，导致最后一个弹不掉，使得输出 1，但官方数据没卡这一点，我直接跳到最后一个过了，事实上，我赛时闲的无聊的时候用了不少自己就 hack 掉的错误做法能过掉官方数据，比如上面那个直接只跳一次的做法，不过大家放心，虽然我造的数据比较随机，但绝对强于官方数据。

这是官方的 std。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int a[N];
int nxt[N][30],pos[20];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        memset(pos,0,sizeof pos);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            for(int j=0;j<=20;j++)nxt[i][j]=n+1;
        }
        for(int i=n;i>=1;i--){
            if(!pos[a[i]]){
                nxt[a[i]][0]=n+1;
                pos[a[i]]=i;
            }else{
                nxt[i][0]=pos[a[i]];
                pos[a[i]]=i;
            }
        }
        for(int i=n;i>=1;i--){
            for(int j=1;j<=20;j++){
                if(nxt[i][j-1]+1<=n)
                    nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];
                }
        }
        int q;
        cin>>q;
        while(q--){
            int l,r;
            cin>>l>>r;
            int ii=l;
            int ans=0;
            while(ii<=r){
                while(ii<=r&&nxt[ii][0]>r){
                    ii++;
                    ans++;
                }
                if(ii>r)break;
                for(int j=20;j>=0;j--){
                    if(nxt[ii][j]<=r){
                        ii=nxt[ii][j];
                        break;
                    }
                }
                ii++;
            }
            cout<<ans<<"\n";
        }
    }
}

注意，官方的 std 中第20行应为 nxt[i][0]=n+1; ，而不是 nxt[a[i]][0]=n+1;。

当然，也可以直接把这一行删掉，具体见这个帖子。

感谢 @sapo1o 指出问题和 @sbh2012 提供的 hack。请大家不要盲目相信官方的 std，从这个细节可以看出，官方在写这份程序的时候思路很乱，理由是前面已完成了初始化，所以这行程序没有任何作用。

不过，由于较大且相对比较随机，经测试，保证正确的程序可以通过，可以证明，这个错误在大的随即数据下几乎不可能出错，所以目前未造成影响，不过这也是一件比较可怕的事情，CCF 的官方数据也是这份 std 造的，我没有修改任何一个字符，所以官方数据的正确性和这次 GESP 的成绩值得怀疑，作为 CCF 举办的官方比赛，我认为这件事情的影响重大且极其恶劣，望周知！