差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:笛卡尔树 [2020/07/05 19:54]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:笛卡尔树 [2020/07/27 22:56] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:笛卡尔树被移动至2020-2021:teams:legal_string:jxm2001:笛卡尔树
@@ 行 27: / 行 27: @@
 [[https://www.luogu.com.cn/problem/P5854|洛谷p5854]]
-<hidden 查看代码>
 <code cpp>
-const int MAXN=1e7+5;
+const int MAXN=1e7+5,Inf=2e9;
 int Stack[MAXN],v[MAXN],ch[MAXN][2],root;
-void build(int n){//小根堆的笛卡尔树
+void build(int n){//小根堆笛卡尔树
-	int top=0,last=0;
+	int top=0;
+	v[0]=-Inf;Stack[++top]=0;
 	_rep(i,1,n){
-		while(top&&v[i]<v[Stack[top]])top--;
+		while(v[i]<v[Stack[top]])top--;
-		if(top)ch[Stack[top]][1]=i;
+		ch[i][0]=ch[Stack[top]][1];
-		if(top<last)ch[i][0]=Stack[top+1];
+		ch[Stack[top]][1]=i;
 		Stack[++top]=i;
-		last=top;
 	}
-	root=Stack[1];
+	root=Stack[2];
 }
 </code>
-</hidden>
 ===== 算法练习 =====
@@ 行 83: / 行 81: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=505,MAXH=1e6+5,mod=1e9+7;
 LL frac[MAXH],inv[MAXH];
@@ 行 208: / 行 159: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=505,MAXH=1e6+5,mod=1e9+7;
 LL frac[MAXH],inv[MAXH];
@@ 行 322: / 行 226: @@
 </hidden>
+==== 习题二 ====
+[[https://ac.nowcoder.com/acm/contest/5668/H|牛客暑期多校(第三场) H 题]]
+=== 题意 ===
+有一个长度为 $n$ 的字符串 $s_0$, 第 $i$ 个字符是数字 $i\bmod 10$。
+给定一个 $0\sim n-1$ 的排列 $p$ 和一个数值范围在 $0\sim 9$ 的数列 $d$。
+字符串 $s_i$ 是把字符串 $s_{i-1}$ 的第 $p_i$ 个字符改成 $d_i$ 的结果。
+将这 $n+1$ 个字符串按字典序排序，字典序相同时按字符串编号排序，输出每个字符串在排序后的位置(范围为 $0\sim n$)。
+=== 题解 ===
+首先假设所有 $d_i\neq p_i\bmod 10$，先考虑 $p_i=1$ 的位置。
+如果有 $d_i\lt p_i\bmod 10$，则显然有 $s_0\sim s_{i-1}$ 字典序大于 $s_i\sim s_n$，考虑将 $s_0\sim s_{i-1}$ 排名加上 $n-i+1$。
+如果有 $d_i\gt p_i\bmod 10$，则显然有 $s_0\sim s_{i-1}$ 字典序小于 $s_i\sim s_n$，考虑将 $s_i\sim s_n$ 排名加上 $i$。
+接下来 $p_i=1$ 将 $s$ 分为 $s_0\sim s_{i-1},s_i\sim s_n$ 两个区间，且两区间互不影响，可以分别递归求解。
+由于每次需要找到该区间 $p_i$ 最小的位置并划分区间，发现笛卡尔树恰好满足要求。
+排名修改可以考虑差分处理。
+最后是 $d_i=p_i\bmod 10$ 的情况，可以考虑将 $p_i$ 修改为 $\inf$，这样 $p_i$ 的影响一定会最后考虑。
+由于此时字典序相同，所以是 $s_\text{left}\sim s_{i-1}$ 字典序小于 $s_i\sim s_\text{right}$。
+该情况影响与 $d_i\gt p_i\bmod 10$ 的情况相同，考虑合并这两种情况，改为 $d_i\ge p_i\bmod 10$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e6+5,Inf=1e9,Base=1e7+19,Mod=1e9+7;
+int n,p[MAXN],d[MAXN];
+void init(){
+	int seed=read_int(),a=read_int(),b=read_int(),mod=read_int();
+	_for(i,0,n)p[i]=i;
+	_for(i,1,n){
+		swap(p[i],p[seed%(i+1)]);
+		seed=(1LL*seed*a+b)%mod;
+	}
+	seed=read_int(),a=read_int(),b=read_int(),mod=read_int();
+	_for(i,0,n){
+		d[i]=seed%10;
+		seed=(1LL*seed*a+b)%mod;
+	}
+	for(int i=n;i;i--)p[i]=p[i-1],d[i]=d[i-1];
+}
+int Stack[MAXN],ch[MAXN][2],root;
+void build(int n){
+	int top=0;
+	p[0]=-Inf;Stack[++top]=0;
+	_rep(i,1,n){
+		while(p[i]<p[Stack[top]])top--;
+		ch[i][0]=ch[Stack[top]][1];
+		ch[Stack[top]][1]=i;
+		Stack[++top]=i;
+	}
+	root=Stack[2];
+}
+int s[MAXN];
+void dfs(int pos,int lef,int rig){
+	if(lef>=rig)return;
+	if(d[pos]>=0){
+		s[pos]+=pos-lef;
+		s[rig+1]-=pos-lef;
+	}
+	else{
+		s[lef]+=rig-pos+1;
+		s[pos]-=rig-pos+1;
+	}
+	dfs(ch[pos][0],lef,pos-1);
+	dfs(ch[pos][1],pos,rig);
+}
+int main()
+{
+	int t=read_int();
+	while(t--){
+		n=read_int();
+		init();
+		s[0]=0;
+		_rep(i,1,n){
+			s[i]=0;
+			d[i]-=p[i]%10;
+			if(!d[i])p[i]=Inf;
+		}
+		build(n);
+		dfs(root,0,n);
+		_rep(i,1,n)
+		s[i]+=s[i-1];
+		int ans=0,base=1;
+		_rep(i,0,n){
+			ans=(ans+1LL*s[i]*base)%Mod;
+			base=1LL*base*Base%Mod;
+		}
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具