P10264 接竹竿 题解

· · 题解

注意到数据不是很大，所以可以用一种简单的方法过。

我们存下每一个 A_i 后第一个与它相等的元素的位置。对于每一次询问，我们从询问的左端点开始遍历，如果遇到一个在此区间内出现两次的元素，就跳到它第二次出现的位置上，并不计数；否则按顺序往后遍历，并按位计数。最后输出结果即可。

由于 A_i\le13，所以根据抽屉原理，最多每 13 个位置就会有一个重复的元素，所以这样时间不会被卡。如果一组数据像这样：

15000
1 1 2 2 1 1 2 2 1 1 ...
15000
1 15000
1 15000
...

此时每次询问平均就需要遍历 \frac n2 次，在数据范围下 q 次询问的总时间刚到 10^8。

为了避免超时，考虑进行优化：存储下每个区间的答案，对于重复的询问直接输出，这样就避免全程搜索整个序列的时间浪费，让极限情况下的总查询次数不超过 \frac {n^2} 2，从而让时间降到 10^8 以下，配合 O2 优化，可以通过本题。

#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> ma;
int t,n,m,l,r,a[20005],f[100005];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int flag[15]={0};
        for(int i=n;i>=1;i--) f[i]=flag[a[i]],flag[a[i]]=i;//f[i]表示第i个元素在其后第一次出现的位置 
        scanf("%d",&m);
        ma.clear();
        for(int i=1;i<=m;i++){
            scanf("%d %d",&l,&r);
            int cnt=0;
            if(ma.count({l,r})){//这里存储的是上一次在序列中查询此区间的结果 
                printf("%d\n",ma[{l,r}]);
                continue;
            }
            for(int j=l;j<=r;j++){
                if(f[j]>=l&&f[j]<=r) j=f[j];
                else cnt++;
            }
            ma[{l,r}]=cnt;
            printf("%d\n",cnt);
        }
    }
    return 0;
}