H. Sort the Strings Revision (笛卡尔树)

参考博客

  • 题意:
    一个s串满足s[i] = i % 10,给出p,d数组的构造方法,每次将s串p[i]位换成d[i], 总共得到n + 1个串,对它们进行排名。第i次操作后的排名为r[i];
    输出 \((\sum_{i=0}^{n}(r_{i}*10000019^{i}))\%(1e9+7)\)

  • 题解:

    • 很关键的一点是p[]是一个排列,所以对s串每一位只修改一次。我们从低位到高位去修改,如果修改p[i]位要变成的数小于该位原来的数(p[i]%10>d[i]),那么修改p[i]之后位得到的的串字典序一定小于修改p[i]前得到的字符串。所以可以用这一次修改将字符串排名分成两类,一类占字典序大的部分,一类占字典序小的部分。再继续分治对每个部分用其P[i]最小的位进行划分。一直划分下去就能得到所有的排名。

    • 关键是当划分成两部分后怎么快速确定这个处理区间的最小值位置,RMQ问题。这里可以用O(n)的笛卡尔树来处理。笛卡尔树根节点是整个区间最小值的位置。左子节点是最小位置左边区间的最小值的位置,右子节点是最小值右边区间最小值所在位置。

    • 分治时,如果 \(p[i]\%10>d[i]​\) , 其中i是当前区间最小值所在位置,那么其左边的区间操作形成的字符串rk+右边个数(占rk高位)。右边不影响(占rk低位)

       dfs(ls[index], l, index, rank + (p[index] % 10 > d[index]) * (r - index));
      
    • 如果 \(p[i]\%10<d[i]​\) 那i右边区间操作形成的字符串rk+左边个数(占rk高位),左边不受影响(占rk低位)

      dfs(rs[index], index + 1, r, rank + (p[index] % 10 < d[index]) * (index - l + 1));
      
    • 如果 \(p[i]\%10=d[i]\) 时,这一位操作不会影响任何其他位的rk, 一个技巧,让p[i]=INF, 这样这一位就在迪卡尔树的叶子节点上,最后处理时直接确定rk就行。同时如果处理到边界,及叶子节点,说明这个操作处理这个区间的所能处理的最高位,能影响它的低位都处理了,根据前面的rk累计可以直接确定其rk。

      if(p[index] == INF || l >= r) {
         for(int i = l; i <= r; ++ i) rk[i] = rank + (i - l);
         return;
      }
      
  • 代码:

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 2e6+10;
    const ll mod = 1e9 + 7;
    const ll INF = 1 << 30;
    //
    
    int T, n;
    ll p[N], d[N];
    int rk[N];
    int ls[N], rs[N];
    int st[N], top;
    
    void Build() 
    {
    	st[0]=0;
    	for(int i=0;i<n;i++){
            int k=st[0];
            while(k>0&&p[st[k]]>p[i]) k--;
            if(k) rs[st[k]]=i;
            if(k<st[0]) ls[i]=st[k+1];
            st[++k]=i; st[0]=k;
        }
    }
    
    void dfs(int index, int l, int r, int rank){
        if(p[index] == INF || l >= r) {
            for(int i = l; i <= r; ++ i) rk[i] = rank + (i - l);
            return;
        }
        dfs(ls[index], l, index, rank + (p[index] % 10 > d[index]) * (r - index));
        dfs(rs[index], index + 1, r, rank + (p[index] % 10 < d[index]) * (index - l + 1));
    }
    
    int main()
    {
        scanf("%d",&T);
        while(T --){
            scanf("%d",&n);
            ll pseed, pa, pb, pmod;
            ll dseed, da, db, dmod;
            scanf("%lld%lld%lld%lld",&pseed, &pa, &pb, &pmod);
            scanf("%lld%lld%lld%lld",&dseed, &da, &db, &dmod);
    
            for(int i = 0; i < n; ++ i) p[i] = i;
            for(int i = 1; i < n; ++ i){
                swap(p[pseed % (i + 1)], p[i]);
                pseed = (1ll * pseed * pa % pmod + 1ll * pb) % pmod;
            }
            for(int i = 0; i < n; ++ i){
                d[i] = dseed % 10;
                dseed = (1ll * dseed * da % dmod + 1ll * db) % dmod;
                if(p[i] % 10 == d[i]) p[i] = INF;
            }
            Build();
            for(int i = 0; i <= n; ++ i) rk[i] = 0;
            dfs(st[1], 0, n, 0);
            ll res = 0, temp = 1;
            for(int i = 0; i <= n; ++ i){
                res = (res + 1ll * rk[i] * temp % mod) % mod;
                temp = temp * 10000019ll % mod;
            }
            printf("%lld\n",res);
        }
        return 0;
    }
    
上一篇:Vue - 基础(3)


下一篇:k8s部署tomcat