题解：P1311 [NOIP2011 提高组] 选择客栈

Shunpower · 2025-01-08 02:17:56 · 题解

Fun fact：本题题解区在清理前有 92 篇题解。

因为这道题是经典的一题多解题目，对计数子区间类的问题有重大的启发意义，所以在排除一些故弄玄虚故意复杂化问题的做法后，这篇题解将尽可能多地提供这个题题解区曾经有的不同做法。

那些题解有很多写得几乎使人无法阅读，我加上了自己的思考整理出这篇题解。

枚举咖啡店

时间复杂度 \mathcal O(nk)，空间复杂度 \mathcal O(nk)。

考虑枚举咖啡店，那么问题是同一种住宿方案可能有很多种咖啡店的选择方案，这样就会算重。于是我们不妨钦定一个可行的住宿方案在最靠左的咖啡店选择中被计算到。

假设我们枚举的 b_i\le p 的咖啡店是 i，上一个满足条件的咖啡店是 las（初始设置为 0），那么意味着两个人的客栈需要分别在 (las,i] 和 [i,n] 中选择。

因为左边那个人的住宿必须满足这个咖啡店是最靠左的满足条件的咖啡店，右边那个人就没什么限制，只要保证咖啡店在他们中间就行了。

所以直接对所有颜色做前缀和即可。注意要减去两个人同时住在 i 的方案。

int n,k,p;
int a[N],b[N];
int pre[N][51],suf[N][51];
int lst;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k>>p;
    fr1(i,1,n) cin>>a[i]>>b[i];
    fr1(i,1,n){
        if(b[i]<=p){
            fr1(j,lst+1,i) pre[i][a[j]]++;
            lst=i;
        }
    }
    fr2(i,n,1){
        fr1(j,0,k-1) suf[i][j]=suf[i+1][j];
        suf[i][a[i]]++;
    }
    ll ans=0;
    fr1(i,1,n){
        if(b[i]<=p){
            fr1(j,0,k-1) ans+=pre[i][j]*suf[i][j];
            ans--;
        }
    }
    cout<<ans<<'\n';
    ET;
}

枚举右边的客栈

时间复杂度 \mathcal O(n)，空间复杂度 \mathcal O(k)。

考虑枚举右边的客栈，那么我们完全可以维护它及它前面第一个可行的咖啡店，也就是当前最靠右的合法咖啡店。很明显，这个咖啡店及其前面的客栈是可以供左边那个人随意选择的。

那么我们只需维护每种颜色在当前最靠右的合法咖啡店前面有多少种选择就可以了。可以在向右移动该咖啡店的同时维护掉。

注意也要去掉两个人同时住在咖啡店那个客栈的情况。

int n,k,p;
int a[N],b[N];
int sum[51];
int lst;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k>>p;
    fr1(i,1,n) cin>>a[i]>>b[i];
    ll ans=0;
    fr1(i,1,n){
        if(b[i]<=p){
            fr1(j,lst+1,i) sum[a[j]]++;
            lst=i;
        }
        ans+=sum[a[i]]-(b[i]<=p);
    }
    cout<<ans<<'\n';
    ET;
}

枚举左边的客栈（二分/双指针）

时间复杂度 \mathcal O(n)，空间复杂度 \mathcal O(n)。

其实也可以把上面枚举右边客栈的方法倒过来做，但是这里介绍另外一种更自然的想法。我们先按照颜色拆开，然后每种颜色独立做。

考虑对于某种颜色枚举左边的客栈，那么显然右边的可选客栈应该是单调的（前一半不合法，后一半合法）。因为只要存在一个合法咖啡店它右边的客栈就全部可选了。

所以找出第一个合法的客栈之后，这个客栈后面的全部同色客栈都可以计入答案。

考虑我们可以 \mathcal O(1) 地判断一个客栈区间 [l,r] 是否合法：我们可以维护每个点右边第一个合法咖啡店 nxt_i，检验 nxt_l\le r 即可。

于是二分加这个判定即可做到 \mathcal O(n\log n)。

也可以使用双指针。显然随着枚举的左边的客栈向右移动，第一个可选的右边的客栈一定也是向后移动的（区间内的咖啡店在越来越少）。那么我们只需要移动右边的客栈这个指针，维护区间是否合法即可。

于是可以做到 \mathcal O(n)。

代码写的是双指针。

int n,k,p;
int a[N],b[N];
int nxt[N];
vector <int> col[55];
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n>>k>>p;
    fr1(i,1,n) cin>>a[i]>>b[i];
    nxt[n+1]=n+1;
    fr2(i,n,1) {
        if(b[i]<=p) nxt[i]=i;
        else nxt[i]=nxt[i+1];
    }
    fr1(i,0,k-1) col[i].pb(0);
    fr1(i,1,n) col[a[i]].pb(i);
    ll ans=0;
    fr1(i,0,k-1){
        if(col[i].size()<=2) continue; 
        int m=col[i].size()-1;
        int r=0;
        fr1(l,1,m){
            while(nxt[col[i][l]]>col[i][r]||l>r){
                if(r>=m) break;
                r++;
            }
            if(nxt[col[i][l]]<=col[i][r]) ans+=m-r+1-(l==r);
            else break;
        }
    }
    cout<<ans<<'\n';
    ET;
}

Bonus：

其实也可以不用这么麻烦。考虑枚举左侧客栈 i 之后，[nxt_i,n] 之间全部的同色点都可以选择，如果我们能够直接查询这中间颜色为 a_i 的点数也做完了。使用前缀和就可以以 \mathcal O(nk) 的空间完成。

事实上可以发现 nxt_i 单调不减，所以用类似双指针的方式扫过去也可以做到线性空间，但是和双指针做法本质上区别不大了。

分治

时间复杂度 \mathcal O(n\log n)，空间复杂度 \mathcal O(n\log n+k)。

数合法子区间数！可以考虑分治。

我们考虑分治区间 [l,r]，需要计数跨越 mid 的合法区间数。

考虑左半边 [l,mid] 的最靠右的合法咖啡店 x，右半边 (mid,r] 的最靠左的合法咖啡店 y。那么考虑只要子区间左半边包含 x 或者子区间右半边包含 y 就一定合法。

可以正向统计，但是不如把不合法的斥掉。可以发现不合法的方案就是左边的客栈选在了 (x,mid]，右边的客栈选在了 (mid,y)。我们用这一层的总方案数减掉这种方案数就可以了。

注意每种颜色还是要分开统计，以及要处理一下某一半没有合法咖啡店的情况。

注意这里的代码我写成了 \mathcal O(nk\log n)，事实上在分治的时候如果只考虑两边存在的颜色而不是扫完所有颜色就可以轻易做到 \mathcal O(n\log n)。

int n,k,p;
int a[N],b[N];
int lef[51],rig[51];
ll divide(int l,int r){
    if(l==r) return 0;
    ll ans=0;
    int mid=(l+r>>1);
    fr1(i,0,k-1) lef[i]=rig[i]=0;
    fr1(i,l,mid) lef[a[i]]++;
    fr1(i,mid+1,r) rig[a[i]]++;
    fr1(i,0,k-1) ans+=lef[i]*rig[i];
    int x=l-1;
    fr2(i,mid,l){
        if(b[i]<=p){
            x=i;
            break;
        }
    }
    int y=r+1;
    fr1(i,mid+1,r){
        if(b[i]<=p){
            y=i;
            break;
        }
    }
    fr1(i,0,k-1) lef[i]=rig[i]=0;
    fr1(i,x+1,mid) lef[a[i]]++;
    fr1(i,mid+1,y-1) rig[a[i]]++;
    fr1(i,0,k-1) ans-=lef[i]*rig[i];
    ans+=divide(l,mid);
    ans+=divide(mid+1,r);
    return ans;
}
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n>>k>>p;
    fr1(i,1,n) cin>>a[i]>>b[i];
    cout<<divide(1,n)<<'\n';
    ET;
}

容斥

时间复杂度 \mathcal O(n)，空间复杂度 \mathcal O(n)。

一个比较厉害的做法。

考虑所有颜色可以产生的所有可能性是 \sum\limits_{i=0}^{k-1}{cnt_i\choose 2}，其中 cnt_i 表示第 i 种颜色的出现次数。

然后我们考虑去掉其中不可行的客栈选法。这些客栈选法的共同点是不存在任何 b_i\le p 也就是合法咖啡店在中间。所以我们不妨用合法咖啡店把原序列切开（合法咖啡店所在的客栈就可以看成消失了）成若干段，那么不合法的方案等价于选择一个不跨越段的方案。

所以对于每一段的每一种颜色又统计一次 \sum\limits_{i=0}^{k-1}{cnt'_i\choose 2}，其中 cnt'_i 表示第 i 种颜色在这一段的出现次数。把这个从所有可能性中扣掉就可以了。

实现精美一点就可以轻易做到时间和空间都线性了。

int n,k,p;
int a[N],b[N];
int sum[51];
ll ans;
ll C(int n){
    if(n<2) return 0;
    return 1ll*n*(n-1)/2;
}
stack <int> st;
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n>>k>>p;
    fr1(i,1,n) cin>>a[i]>>b[i];
    fr1(i,1,n) sum[a[i]]++;
    fr1(i,0,k-1) ans+=C(sum[i]);
    memset(sum,0,sizeof sum);
    fr1(i,1,n){
        if(b[i]>p) sum[a[i]]++,st.push(a[i]);
        if(i==n||b[i]<=p){
            while(!st.empty()){
                ans-=C(sum[st.top()]);
                sum[st.top()]=0;
                st.pop();
            }
        }
    }
    cout<<ans<<'\n';
    ET;
}

分块

时间复杂度 \mathcal O(n\sqrt n)，空间复杂度 \mathcal O(n)。

原题解里面有一个分块做法，看似是分块实则不是分块。

考虑分块怎么计数子区间。块内我们可以直接暴力枚举两端，在扫的同时维护区间最小值就可以了，两端合不合法直接看是否 \le p 就好了。时间复杂度 \mathcal O(nB)。

考虑怎么统计跨块区间的贡献。考虑枚举两个块 b_1,b_2，那么这两个块中间（即 (b_1,b_2)）的最小值也可以在维护好块的整体最小值后边扫边知道。假设这个最小值是 mn，那么：

所以这部分的时间复杂度 \mathcal O(\frac{n^2}{B})。

平衡取 B=\sqrt n，就有总时间复杂度 \mathcal O(n\sqrt n) 了。