k-string

给一个长度为n的字符串S,定义k-string为在字符串S中出现次数大于等于k次的子串,也就是存在至少k对(i,j)使得0 <= i <= j < n且Si,Si+1…Sj构成的子串与该k-string相同。现给一个初始字符串,然后执行m个操作,每个操作有两种:1.往当前字符串S末尾添加一个字符; 2.询问当前不同的k-string有多少种。

这题可以用sa的h数组做 也可以用构后缀树做
先说下sa的(我没写 只是随便写个思路=-=
【sa】
先把字符串倒过来 这样每次插入就等于插入一个后缀
给每个后缀一个编号 代表插入时询问到第几个询问了
h数组可以画成像这样的柱状图(左)
1
然后可以把它从上到下划分成好几个矩形(右)
划分可以排序+链表做

然后对于一个矩形 记录3个信息 l r h
对于这个矩形的贡献就是:l~r这些后缀中 第k个出现的时间
在这个时间后的询问 这个矩形都能对其贡献h的答案
可以维护一个数组记录改变量 最后扫一遍就可以了

询问k大 题解上写的是用划分树 主席树应该也可以

【后缀树】
其实sam构的是前缀树 那刚好连字符串都不用倒过来了
同样一个插入代表是多了一个前缀
用上面同样的方法对前缀进行标号
考虑parent树上一个节点的贡献
一个节点能有贡献 当且仅当它出现了k次 即它有k个出现了的叶子
而他的贡献是t[now].l – t[t[now].f].l
同样维护一个改变量数组即可
这里的k大是在一个类似dfs序上询问的

有一个值得注意的地方 这题的空间限制是64(32)M
直接用sam+主席树会MLE
有两种办法 1是把sam的ch数组改成map
我试了试 TLE了=-=

还有就是 从下往上计算 对每个节点维护一个大根左偏树
对于一个儿子都计算过的节点 把所有儿子合并
然后不停删根 直到树的大小为k 这时根就是第k小的时间点

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
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 100005;

struct node
{
    int ch[27], l, f;
}t[maxn * 2];

struct line
{
    int to, next;
}li[maxn * 4];

struct t_node
{
    int l, r, dis, v;
}tt[maxn];

int ans[maxn], is[maxn], tot, last, n, m, k, p, be[maxn * 2], l, tot_node, b[maxn * 2];
string s;

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

void add(char c, int len)
{
    c -= 'a';
    int now = ++tot, p = last;
    last = now;
    t[now].l = len;
    for (; p && !t[p].ch[c]; p = t[p].f) t[p].ch[c] = now;
    if (!p) t[now].f = 1;
    else
    if (t[p].l + 1 == t[t[p].ch[c]].l) t[now].f = t[p].ch[c];
    else
    {
        int r = ++tot, ch = t[p].ch[c];
        t[r] = t[ch];
        t[r].l = t[p].l + 1;
        t[ch].f = t[now].f = r;
        for (; p && t[p].ch[c] == ch; p = t[p].f) t[p].ch[c] = r;
    }
}

int merge(int a, int b)
{
    if (!a) return b;
    if (!b) return a;
    if (tt[a].v < tt[b].v) swap(a, b);
    tt[a].r = merge(tt[a].r, b);
    if (tt[tt[a].l].dis < tt[tt[a].r].dis) swap(tt[a].l, tt[a].r);
    tt[a].dis = tt[tt[a].r].dis + 1;
    return a;
}

pair<int, int> dfs(int now)
{
    int root = 0, sum = 0;
    if (!b[now] && t[now].l != 1)
    {
        ++tot_node;
        tt[tot_node].l = tt[tot_node].r = 0;
        tt[tot_node].dis = 1;
        tt[tot_node].v = is[t[now].l - 1];
        root = tot_node;
        sum = 1;
    }
    for (int i = be[now]; i; i = li[i].next)
    {
        pair<int, int> t = dfs(li[i].to);
        root = merge(root, t.first);
        sum += t.second;
    }
    if (now == 1 || sum < k) return make_pair(root, sum);
    while (sum > k) root = merge(tt[root].l, tt[root].r), --sum;
    ans[tt[root].v] += t[now].l - t[t[now].f].l - (!b[now] ? 1 : 0);
    return make_pair(root, sum);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    cin >> s;
    s = '{' + s;
    tot = last = 1;
    for (int i = 0; i < s.length(); ++i)
        add(s[i], i + 1), is[i] = 0;
    for (int i = 0; i < m; ++i)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            char tc, c;
            scanf("%c%c", &tc, &c);
            is[s.length()] = p;
            s += c;
            add(c, s.length());
        }
        else ++p;
    }
    for (int i = 1; i <= tot; ++i)
        makeline(t[i].f, i), b[t[i].f] = 1;
    tot_node = 1;
    dfs(1);
    int as = 0;
    for (int i = 0; i < p; ++i)
    {
        as += ans[i];
        printf("%d\n", as);
    }
    fclose(stdin);fclose(stdout);
}

BZOJ 2809: [Apio2012]dispatching

考虑枚举对于节点i作为领导 一定是把他的儿子们权值最小的几个作为工作忍者
用左偏树 大根堆维护这个关系 每次把最大的删掉 直到和<=S 按从叶子到根的顺序 每次把儿子的左偏树合并即可

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;

const ll MHmaxn = 100005;

struct MHnode
{
  ll l, r, dis, v;
};

struct MergeableHeap  //big first
{
  MHnode t[MHmaxn];
  ll tot;
 
  ll merge(ll a, ll b)
  {
    if (!a) return b;
    if (!b) return a;
    if (t[a].v < t[b].v) swap(a, b);
    t[a].r = merge(t[a].r, b);
    if (t[t[a].l].dis < t[t[a].r].dis) swap(t[a].l, t[a].r);
    t[a].dis = t[t[a].r].dis + 1;
    return a;
  }
 
  ll make_node(ll v)
  {
    ++tot;
    t[tot].l = t[tot].r = t[tot].dis = 0;
    t[tot].v = v;
    return tot;
  }
 
  ll pop(ll root)
  {
    return merge(t[root].l, t[root].r);
  }
 
  ll top(ll root)
  {
    return t[root].v;
  }
}mh;

struct line
{
  ll next, to;
}li[MHmaxn];

struct poll
{
  ll a, b, c;
  poll(ll x, ll y, ll z) : a(x), b(y), c(z) {}
};

ll be[MHmaxn], l, n, m, e[MHmaxn], c[MHmaxn], ans;

void makeline(ll fr, ll to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}

poll dfs(ll now)
{
  ll no = mh.make_node(c[now]), sum = c[now], tot = 1;
  for (ll i = be[now]; i; i = li[i].next)
  {
    ll to = li[i].to;
    poll t = dfs(to);
    no = mh.merge(no, t.a);
    sum += t.b;
    tot += t.c;
  }
  while (sum > m)
  {
    sum -= mh.top(no);
    no = mh.pop(no);
    --tot;
  }
  ans = max(ans, e[now] * tot);
  return poll(no, sum, tot);
}

int main()
{
  scanf("%lld%lld", &n, &m);
  ll root;
  for (ll i = 1; i <= n; ++i)
  {
    ll b;
    scanf("%lld%lld%lld", &b, &c[i], &e[i]);
    if (!b) root = i;
    else makeline(b, i);
  }
  dfs(root);
  printf("%lld", ans);
}

左偏树

左偏树 会让人联想到平衡树 其实毫无关系= =
只不过一个很平衡 一个很不平衡而已~
左偏树其实是可并堆 主要操作是merge(int, int)
传入两个根 把这以这两个为根的子树合并 返回新根

这个数据结构的node类:

1
2
3
4
struct MHnode
{
  int l, r, dis, v;
}

l,r就是左右儿子的指针
v是这个节点的权值
dis就是左偏树的关键 表示从这个点 一直走右儿子 要走多少步能走到头
左偏树就是用这个保持左偏性质

以下是merge程序 这里是大根堆
[/cc lang = “cpp”]
int merge(int a, int b)
{
if (!a) return b;
if (!b) return a; //如果某个点为空 就返回另外一个点
if (t[a].v < t[b].v) swap(a, b); //以a为根 t[a].r = merge(t[a].r, b); //合并a.r和b if (t[t[a].l].dis < t[t[a].r].dis) swap(t[a].l, t[a].r); //如果左边的dis<右边的dis 那么就交换 这样可以保持左偏性质 t[a].dis = t[t[a].r].dis + 1; //更新dis return a; //返回根 } [/cc] 删除只能删除根 就是把根弄掉 然后合并左右子树 插入就是把一个只有一个点的树和原堆合并 合并就是合并了 一个性价比很高的数据结构 虽然他能做的 启发式合并平衡树都能做 但是代码复杂度不是一个级别。。