杨图
对于n的一个划分$\lambda=(\lambda_1 \geq \lambda_2 \ldots) \vdash n$，杨图第$i$行有$\lambda_i$个方块
标准杨表
将1-n这n个数填入一个杨图$\lambda$的每一个方块中，使得从上到下，从左到右数字都递增
近似杨表
将n个不同的数字填入杨图中存在一种插入算法RSK，从第一行开始，每次替换当前行第一个大于自己的数（如果有相同数字就替换第一个大于等于自己的数），并将替换的数去插入下一行，若找不到这样一个数，则将该数插入到该行末尾并结束
钩子定理
$h_{i,j}$定义为(i,j)这个格子下面的格子数+右边的格子数+1对于$\lambda \vdash n$，有$f^\lambda = \dfrac{n!}{\prod h_{i,j}}$表示$\lambda$对应的杨图的填法
Robinson–Schensted correspondence
一个1到n个数的排列和一对相同形状的标准杨表一一对应$\sum \limits_{\lambda \vdash n} (f^\lambda)^2$
n个元素的杨氏矩阵的个数
$f_n = f_{n-1} + (n-1)f_{n-2}$
杨表与LIS
将一个排列按序用RSK算法插入到杨表中，则杨表第一行的长度等于其LIS长度（构建的杨表从上到下，从左到右递增）将杨表的比较方式取反($\lt$变$\geq$,$gt$变$\leq$)，所得杨表的形状为原杨表的转置(仅形状而言)杨表第一列的长度等于最长不上升子序列长度(考虑转置)杨表前k列的长度和等于LIS$\leq k$的k-LIS的长度(利用Dilworth定理，等价于划分出k个不相交的最长不上升子序列)
P3774 [CTSC2017]最长上升子序列
给定一个长为n的序列a，q次询问a的某个前缀的最长k-LIS的长度$n\leq 50000, q \leq 200000$对于每个询问的答案就是将a的这个前缀依次插入杨表后，前k列长度的和考虑离线询问后动态维护前k列长度和每次插入的复杂度是$O(n\log n)$的我们可以只维护杨表的前$\sqrt n$行，然后反转比较方式，再维护这个杨表的转置的前$\sqrt n$行(等价于维护了原杨表的前$\sqrt n$列，当这一列的长度超过$\sqrt n$时，表明这个元素在原杨表中没有维护到，所以在这里维护即可)，显然每个元素的行或列的下标至少有一个$\leq \sqrt n$，所以这样是正确的复杂度为$O(n\sqrt n \log n)$
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, M = 255;
int n, qq, blo, a[N], c[N], ans[4*N];
vector<int> YT[M], YT2[M];
struct qry
{
int m, k, idx;
bool operator < (const qry& oth) { return m < oth.m; }
}q[4*N];
void upd(int x, int v)
{
for(int i=x; i<=n; i+=(i&-i)) c[i] += v;
}
int ask(int x)
{
int ans = 0;
for(int i=x; i>0; i-=(i&-i)) ans += c[i];
return ans;
}
void add(int v)
{
for(int i=1, x=v; i<blo; i++)
{
if(YT[i].empty() || YT[i].back()<x)
{
YT[i].push_back(x);
upd(YT[i].size(), 1);
break;
}
swap(YT[i][lower_bound(YT[i].begin(), YT[i].end(), x)-YT[i].begin()], x);
}
}
void add2(int v)
{
for(int i=1, x=v; i<blo; i++)
{
if(YT2[i].empty() || YT2[i].back()>=x)
{
YT2[i].push_back(x);
if((int)YT2[i].size()>=blo) upd(i, 1);
break;
}
swap(YT2[i][upper_bound(YT2[i].begin(), YT2[i].end(), x, greater<int>())-YT2[i].begin()], x);
}
}
int main()
{
scanf("%d%d", &n, &qq);
blo = sqrt(n) + 1;
for(int i=1; i<=n; i++) scanf("%d", a+i);
for(int i=1; i<=qq; i++) scanf("%d%d", &q[i].m, &q[i].k), q[i].idx = i;
sort(q+1, q+qq+1);
int pre = 1;
for(int i=1; i<=qq; )
{
int j = i;
while(pre<=q[i].m) add(a[pre]), add2(a[pre]), pre++;
while(j<=qq && q[j].m==q[i].m)
{
ans[q[j].idx] = ask(q[j].k);
j++;
}
i = j;
}
for(int i=1; i<=qq; i++) printf("%d\n", ans[i]);
return 0;
}
|
P4484 [BJWC2018]最长上升子序列
求长度为n的随机排列的LIS的长度的期望$n \leq 28$暴力跑前几个然后oeis我们只需要枚举n的所有整数划分$\lambda$，然后利用钩子公式计算出相应的$f^\lambda$，那么所有排列的LIS长度的和是$\sum\limits_{\lambda \vdash n} (f^\lambda)^2 \lambda_1$，再除以排列数$n!$即可n的整数划分个数$p(n) \approx \frac{1}{4n\sqrt 3}exp(\pi\sqrt{\frac{2n}{3}})$复杂度$O(p(n))$，大概能跑$\leq 63$
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
| #include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int mod = 998244353, N = 30;
int n;
ll inv[N], ans;
int a[N];
int powmod(int a, int b)
{
int ans = 1;
while(b)
{
if(b&1) ans = 1ll*ans*a%mod;
a = 1ll*a*a%mod;
b >>= 1;
}
return ans;
}
void dfs(int x, int y)
{
if(!x)
{
ll cur = 1;
for(int i=2; i<=n; i++) cur = cur*i%mod;
for(int i=1; i<y; i++)
for(int j=1; j<=a[i]; j++)
{
int R = a[i] - j, D = 0;
for(int k=i; k<y; k++)
if(a[k]>=j) D++;
cur = cur*inv[R+D]%mod;
}
ans = (ans + cur*cur%mod*a[1]%mod)%mod;
return;
}
for(int i=1; i<=x; i++)
{
if(y!=1 && i>a[y-1]) continue;
a[y] = i;
dfs(x-i, y+1);
}
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++) inv[i] = powmod(i, mod-2);
dfs(n, 1);
for(int i=1; i<=n; i++) ans = ans*inv[i]%mod;
printf("%lld\n", ans);
return 0;
}
|
求不相交的LIS
考虑$dp_{i,j}$表示第一个LIS的最后一个元素的值为i，第二个LIS的最后一个元素的值为j，朴素转移的复杂度是$O(n^3)$，利用树状数组可以优化到$O(n^2\log n)$此外也可以用费用流如果询问的是不相交LIS的长度，只要维护出杨表的前两行即可，然后答案就是前两行的长度和$O(2n\log n)$，对于k不相交LIS，可以做到$O(kn\log n)$hdu5406
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n;
pair<int, int> p[N];
struct YT
{
vector<int> t[3];
YT() { for(int i=1; i<=2; i++) t[i].clear(); }
void add(int v)
{
for(int i=1, x=v; i<=2; i++)
{
if(t[i].empty() || t[i].back()<=x)
{
t[i].push_back(x);
break;
}
swap(t[i][upper_bound(t[i].begin(), t[i].end(), x)-t[i].begin()], x);
}
}
};
void solve()
{
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d%d", &p[i].first, &p[i].second);
sort(p+1, p+n+1, [](pair<int, int> x, pair<int, int> y) {
if(x.first==y.first) return x.second < y.second;
return x.first > y.first;
});
YT T;
for(int i=1; i<=n; i++) T.add(p[i].second);
printf("%d\n", int(T.t[1].size() + T.t[2].size()));
}
int main()
{
int _; scanf("%d", &_);
while(_--) solve();
return 0;
}
|