考虑对于$p_{i}=0$，那么可以快速比较出$s_{0},s_{1},...,s_{i-1}$与$s_{i},s_{i+1},...,s_{n}$之间的大小关系，然后对两边分别找到最小的$p_{i}$即可，用线段树维护复杂度多了一个log无法通过，因此需要用笛卡尔树来维护
笛卡尔树：https://oi-wiki.org/ds/cartesian-tree/
搜索时维护在其前面的数量，即要求出笛卡尔树的子树大小，另外需要特殊处理$d[i]=s_{0}[p[i]]$的情况，可以令$p[i]=n$，还有当两个字符串相同时编号小的优先
View Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 2000005 4 #define mod 1000000007 5 int t,n,p[N],d[N],st[N],ls[N],rs[N],rk[N]; 6 void dfs(int k,int l,int r,int s){ 7 if ((p[k]==n)||(l>=r)){ 8 for(int i=l;i<=r;i++)rk[i]=s+(i-l); 9 return; 10 } 11 dfs(ls[k],l,k,s+(p[k]%10>d[k])*(r-k)); 12 dfs(rs[k],k+1,r,s+(p[k]%10<d[k])*(k-l+1)); 13 } 14 int main(){ 15 scanf("%d",&t); 16 while (t--){ 17 scanf("%d",&n); 18 int p1,p2,p3,p4; 19 scanf("%d%d%d%d",&p1,&p2,&p3,&p4); 20 for(int i=0;i<n;i++)p[i]=i; 21 for(int i=1;i<n;i++){ 22 swap(p[p1%(i+1)],p[i]); 23 p1=(1LL*p1*p2+p3)%p4; 24 } 25 int d1,d2,d3,d4; 26 scanf("%d%d%d%d",&d1,&d2,&d3,&d4); 27 for(int i=0;i<n;i++){ 28 d[i]=d1%10; 29 d1=(1LL*d1*d2+d3)%d4; 30 if (p[i]%10==d[i])p[i]=n; 31 } 32 st[0]=0; 33 for(int i=0;i<n;i++){ 34 int k=st[0]; 35 while ((k>0)&&(p[st[k]]>p[i]))k--; 36 if (k)rs[st[k]]=i; 37 if (k<st[0])ls[i]=st[k+1]; 38 st[++k]=i; 39 st[0]=k; 40 } 41 dfs(st[1],0,n,0); 42 int s=1,ans=0; 43 for(int i=0;i<=n;i++){ 44 ans=(ans+1LL*s*rk[i])%mod; 45 s=s*10000019LL%mod; 46 } 47 printf("%d ",ans); 48 } 49 }