题目链接：点击查看
题目大意：给出一个长度为 n 的数字串 s[ 0 ]，每个位置的赋值初始时为 s[ i ] = i % 10 ( i ∈ [ 0 , n - 1 ] )，现在有一个长度为 n 的排列 p，和一个长度为 n 的数列 d ，相当于 n 次操作，每次操作需要将第 p[ i ] 个位置的数字变为 d[ i ] ，这样一共能得到 n + 1 个数字串，需要给这 n + 1 个数字按照字典序排序
题目分析：显然是不能构造出 n + 1 个串然后排序的，而且数据范围也限制了只能 O( n ) 实现，带个 log 都有可能 T 飞
因为 n 次操作对于每个位置有且仅有一次替换，而且在字典序的排序中，显然在原数列中位置更靠前的替换的影响要大于位置较靠后的替换，这样我们可以分治去做：假设当前分治的排列区间是 [ l , r ]，设 pos 为 p[ l ] ~ p[ r ] 中的最小值
p[ pos ] % 10 > d[ pos ]，替换后数列会变得更小，s[ 0 ] ~ s[ pos ] 的字典序要大于 s[ pos + 1 ] ~ s[ n ] 的字典序 p[ pos ] % 10 < d[ pos ]，替换后数列会变得更大，s[ 0 ] ~ s[ pos ] 的字典序要小于 s[ pos + 1 ] ~ s[ n ] 的字典序 p[ pos ] % 10 == d[ pos ]，替换后数列不变
现在的问题是，如何 O( n ) 求出每个区间的最小值呢？可以用笛卡尔树，无脑跑出笛卡尔树后，就可以dfs遍历每个节点所能覆盖的区间了
我写的笛卡尔树一般喜欢加个哨兵节点当做 root，所以在 dfs 的时候需要特判一下，防止死循环
代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e6+100;const int mod=1000000007;const int Hash=10000019;struct Node
{int l,r;
}tree[N];int p[N],d[N],rk[N],root=N-1,num;stack<int>st;void build(int n)
{for(int i=0;i<n;i++){while(st.size()&&p[st.top()]>p[i])st.pop();tree[i].l=tree[st.top()].r;tree[st.top()].r=i;st.push(i);}
}void dfs(int k,int l,int r)
{if(k==root){if(tree[k].l)dfs(tree[k].l,l,r);elsedfs(tree[k].r,l,r);return;}if(l>r)return;if(l==r){rk[l]=num++;return;}if(p[k]==inf){for(int i=l;i<=r;i++)rk[i]=num++;return;}if(p[k]%10<d[k])dfs(tree[k].l,l,k),dfs(tree[k].r,k+1,r);elsedfs(tree[k].r,k+1,r),dfs(tree[k].l,l,k);
}void init(int n)
{num=0;for(int i=0;i<=n;i++)tree[i].l=tree[i].r=0;tree[root].l=tree[root].r=0;p[root]=-inf;while(st.size())st.pop();st.push(root);
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d",&n);init(n);LL pseed,pa,pb,pmod,dseed,da,db,dmod;scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&pseed,&pa,&pb,&pmod,&dseed,&da,&db,&dmod);for(int i=0;i<n;i++){p[i]=i;d[i]=dseed%10;dseed=(dseed*da+db)%dmod;}for(int i=1;i<n;i++){swap(p[pseed%(i+1)],p[i]);pseed=(pseed*pa+pb)%pmod;}for(int i=0;i<n;i++)if(p[i]%10==d[i])//改变第i个位置没有效果 p[i]=inf;build(n);dfs(root,0,n);LL ans=0,base=1;for(int i=0;i<=n;i++){ans=(ans+base*rk[i])%mod;base=base*Hash%mod;}printf("%lld\n",ans);}return 0;
}
总结
以上是生活随笔 为你收集整理的牛客多校3 - Sort the Strings Revision(笛卡尔树+分治) 的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔 网站内容还不错，欢迎将生活随笔 推荐给好友。
