CF1849C题解

zfx_VeXl6 · 2023-07-28 10:56:53 · 题解

先来看这样一个例子。

原串：001101，l_1=2，r_1=6。排完序后变成 000111。

设原串为 s，排序后的串为 s'，可以发现 s_2=s_2'，s_6=s_6'。

这是因为 s_2 为 0，而 [2,6] 这一区间中有 0 存在，当这一区间被排序后，s_2' 必为 0，就与 s_2 相等。s_6 与 s_6' 同理。所以对区间 [2,6] 排序等价于对区间 [3,5] 排序。

那么，当排序区间是 [1,6] 时，也相当于对区间 [3,5] 排序。

所以可以记录下每一个 0 右边第一个 1 的位置 nxt_i 和每一个 1 左边第一个 0 的位置 pre_i，那么对区间 [l,r] 排序就相当于对区间 [nxt_l,pre_r] 排序。对于一组数据，最终的答案就是不同的 [nxt_{l_i},pre_{r_i}] 的数量。

但这样做会遇到一个问题。还是上面的例子，对 [1,3] 和 [5,6] 排序，排序后的串是相同的。但按照上述的算法，[1,3] 相当于 [3,2]，[5,6] 相当于 [6,5]，在统计答案时会被算成两个。但是很明显，当 nxt_l>pre_r 时，相当于没排序，因此看作 [0,0] 就行了。

统计区间时可使用 unordered_map，需要手写哈希函数。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+2;
int t,n,m,nxt[N],pre[N],ans;
char s[N];
LL hsh(int x,int y){return 1LL*(n+1)*x+y;}
unordered_map<LL,int>vis;
int main()
{
    cin>>t;
    while(t--)
    {
        vis.clear();
        ans=0;
        cin>>n>>m;
        nxt[n+1]=n+1;
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)
            if(s[i]=='1')
                pre[i]=pre[i-1];
            else
                pre[i]=i;
        for(int i=n;i;i--)
            if(s[i]=='0')
                nxt[i]=nxt[i+1];
            else
                nxt[i]=i;
        for(int i=1;i<=m;i++)
        {
            int l,r;
            cin>>l>>r;
            l=nxt[l];
            r=pre[r];
            if(l>r)
                l=r=0;
            if(!vis[hsh(l,r)])
            {
                ans++;
                vis[hsh(l,r)]=1;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}