基数排序 + 树状数组：2026暑杭电多校 1008 数字子序列

1008 数字子序列

考虑每个数字串的长度 ll, 显然有 lmx≤2nl_{mx}\le \sqrt{2n}

然后我们从 1 开始计算 ll，fif_i 记为以 [i,i+l−1][i,i+l-1] 为末尾字符串，最长上升整数序列长度。

有两种转移：

  1. 前面长 l−1l-1，现在长 ll，这个跑一遍就行

  2. 上一个（以 jj 开头）长 ll，这个长 ll

我们考虑 jj 要满足的条件：

  1. j<ij<i
  2. s[j:j+l−1]<s[i:i+l−1]s[j:j+l-1]<s[i:i+l-1]

由于我们 ll 是从小到大枚举的，所以上面可以直接使用基数排序即可（类似SA的思想）

（注意，我们不能一开始就排好序，因为当两个串如果前 ll 个字符相同，即使第 l+1l+1 个字符不同，我们也必须先按限制 1 来排序）

维护最大值拿个树状数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244353
#define N 200010
int n, m, i, j, k, T;
int rk[N], nrk[N], pw[N]; 
int g[N], f[N], p[N], Pw[N]; 
int ans, cnt[N];
vector<int>tong[10];  
char s[N]; 

struct Binary_tree {
	int cnt[N], i; 
	void clear(int n) {
		for(i = 0; i <= n; ++i) cnt[i] = 0; 
	}
	void add(int x, int k) {
		while(x <= n) {
			cnt[x] = max(cnt[x], k); 
			x += x & -x; 
		}  
	} 
	int qry(int x) {
		int ans = 0; 
		while(x) {
			ans = max(ans, cnt[x]); 
			x -= x & -x; 
		}
		return ans; 
	}
}Bin;

int Mod(int x) {
	return (x % mo + mo) % mo; 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	for(i = Pw[0] = 1; i < N; ++i) Pw[i] = Pw[i - 1] * i % mo; 
	T = read();
	while(T--) {
		scanf("%s", s + 1); 
		n = strlen(s + 1); m = sqrt(2 * n) + 5; 
		for(i = 1; i <= n; ++i) {
			s[i] -= '0'; 
//			a[i] = (a[i - 1] * 11 + s[i]) % mo; 
			p[i] = 1; 
		}
		for(i = 1; i <= n; ++i) f[i] = g[i] = 0; 
		for(i = 1; i <= n; ++i) p[i] = n - i + 1, rk[i] = 1; 
//		for(i = 1; i <= n; ++i) rk[i] = a[i]; 
		for(int l = 1; l <= m; ++l) {
			for(i = 1, ans = 0; i <= n; ++i) {
				if(i >= l ) ans = max(ans, f[i - l + 1]); 
				if(s[i] != 0 && i + l - 1 <= n) g[i] = max(f[i], ans + 1); 
				else g[i] = f[i]; 
			}
			
			for(i = 0; i <= n; ++i) cnt[i] = 0; 
			for(i = 0; i <= 9; ++i) tong[i].clear(); 
			for(i = 1; i <= n; ++i) {
				cnt[rk[p[i]]]++; 
				tong[s[p[i] + l - 1]].pb(p[i]); 
 			}
			for(i = 1; i <= n; ++i) cnt[i] += cnt[i - 1]; 
//			for(i = 1; i <= n; ++i) debug("%lld ", cnt[i]); debug("\n"); 
			for(i = 0; i <= 9; ++i) {
				for(auto v: tong[i]) {
//					debug("(%lld) %lld |  %lld %d\n", i, v, cnt[rk[v] - 1], (int)s[v + l - 1]); 
					p[++cnt[rk[v] - 1]] = v; 
				}
			}
//			for(i = 1; i <= n; ++i) {
//				debug("[%2d] ", p[i]); 
//				for(j = 1; j <= l; ++j) debug("%d", s[p[i] + j - 1]); 
////				debug("\n"); 
//				debug("(%lld %lld)\n", rk[p[i]], s[p[i] + l - 1]); 
//			}
			for(i = 1, j = 0; i <= n; ++i) {
				if(rk[p[i]] != rk[p[i - 1]] || s[p[i] + l - 1] != s[p[i - 1] + l - 1])
					++j; 
				nrk[p[i]] = j; 
			}
			for(i = 1; i <= n; ++i) rk[i] = nrk[i]; 		
			Bin.clear(n); 
			for(i = 1; i <= n; ++i) {
				j = p[i]; 
				if(j >= l && j + l - 1 <= n) {
					g[j] = max(g[j], Bin.qry(j - l) + 1); 
				}
				Bin.add(j, g[j]); 
				 
			}
			for(i = 1; i <= n; ++i) f[i] = g[i]; 
			ans = 0; 
			for(i = 1; i <= n; ++i) ans = max(ans, f[i]); 
//			for(i = 1; i <= n; ++i) debug("%lld ", f[i]); 
//			debug("%lld\n", ans); 
//			debug("------------\n"); 
		}
		ans = 0; 
		for(i = 1; i <= n; ++i) ans = max(ans, f[i]); 
		printf("%lld\n", ans); 
	}

	return 0;
}