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);
}

带插入区间k大值

区间k大 主席树即可乱虐
带插入的话 可以想到用平衡树套权值线段树解决
但是如果用splay 每次要改变很多节点
就会要重建很多节点上的权值线段树
这样就会TLE
这么避免这个情况呢?
————替罪羊树(可以参见VFleaKing的论文《对无旋转操作的平衡树的一些探究》)
替罪羊树的思想就是 没有旋转操作
如果某棵子树过于不平衡 则直接重建这颗子树
看似非常暴力 但是通过势能分析 可以证明每次复杂度是均摊logn的
替罪羊树判断不平衡的方法有两种
一 高度平衡
二 子节点个数平衡
我用的是第二个 好像这个也比较好写
定义一个常数A 0.5 <= A <= 1 定义某节点为根的子树大小为sum 左子树大小为left_sum 右子树大小为right_sum 如果max(left_sum, right_sum) > sum * A
则称以这个节点为根的子树不平衡 需要暴力重建

现在细化一下如何暴力重建
这个看似很随意的乱搞就可以
其实也不是很随意的。。

第一步:
把这棵子树表示为一条链
定义函数link(n, k)
表示把以n为根的子树拆成一条链
并在右边连上y 并返回最左边的节点编号
实现如下:

1
2
3
4
5
6
7
int link(int now, int z)
{
  if (!now) return z;
  int y = link(t[now].r, z);
  t[now].rt = y;
  return link(t[now].l, now);
}

第二步:
把这条链建成一棵绝对平衡的树
定义函数build(n, k)
表示把以n这个节点为开头的 链上的k个节点建成一棵树
并满足这颗树的根没有右儿子 返回树的根
实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int build(int now, int n)
{
  if (n == 1)
  {
    t[now].l = t[now].r = 0;
    return now;
  }
  int mid = n / 2;
  int l = build(now, mid);
  int r = build(t[l].rt, n - mid);
  t[l].r = t[r].l;
  t[r].l = l;
  return r;
}

第三步:
对新树上的所有节点做处理
这个用一个dfs就可以实现 就不多说
只说一下关于对于每个节点的权值线段树的建立
可以用一个函数把两个子树合并 再把这个节点的权值插入进去即可

怎么比较好的调用这些函数?

1
2
3
4
5
6
7
8
9
int rebuild(int now)
{
  int n = t[now].sum, p = MAXN - 1;
  t[MAXN - 1] = node(0, 0, 0, 0, 0);
  int k = link(now, p);
  build(k, n + 1);
  bld(t[p].l);
  return t[p].l;
}

就是新建一个节点p 把以now为根的子树形成的链接在p的左边
然后建树后会得到一个以p为根的 只有左子树的树
p的左子树就是要的树

以上就是替罪羊树的实现过程

对于一个询问 可以把它拆成几个节点代表的权值线段树和几个散点 可以证明这些是log级的
然后把这些记下来 像普通的主席树的做法就可以求出第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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const double A = 0.618;
const int MAXN = 80000;
 
struct node2
{
  int l, r, sum;
  node2(int a = 0, int b = 0, int c = 0) : l(a), r(b), sum(c) {}
}t2[20000005];
 
struct node
{
  int l, r, v, sum, root, rt;
  node(int a = 0, int b = 0, int _v = 0, int c = 0, int d = 0, int _rt = 0) : l(a), r(b), v(_v), sum(c), root(d), rt(_rt) {}
}t[MAXN];
 
int n, m, root, tot, tot2, la, temp[MAXN], tot3, tot4, s[20000005];
 
int mknode(int l, int r, int v, int sum, int root)
{
  return t[++tot] = node(l, r, v, sum, root), tot;
}
 
int mknode2(int l, int r, int sum)
{
  int now = s[--tot4];
  return t2[now] = node2(l, r, sum), now;
}
 
int mdf(int l, int r, int now, int v, int c)
{
  if (!now) now = mknode2(0, 0, 0);
  if (l == r)
  {
    t2[now].sum += c;
    return now;
  }
  int mid = (l + r) / 2;
 
  if (v <= mid) t2[now].l = mdf(l, mid, t2[now].l, v, c);
  else t2[now].r = mdf(mid + 1, r, t2[now].r, v, c);
 
  t2[now].sum = t2[t2[now].l].sum + t2[t2[now].r].sum;
 
  if (t2[now].l && !t2[t2[now].l].sum)
  {
    s[tot4++] = t2[now].l;
    t2[now].l = 0;
  }
  if (t2[now].r && !t2[t2[now].r].sum)
  {
    s[tot4++] = t2[now].r;
    t2[now].r = 0;
  }
  return now;
}
 
int insert(int root, int v)
{
  mdf(0, MAXN, root, v, 1);
  return root;
}
 
int del(int root, int v)
{
  mdf(0, MAXN, root, v, -1);
  return v;
}
 
int link(int now, int z)
{
  if (!now) return z;
  int y = link(t[now].r, z);
  t[now].rt = y;
  return link(t[now].l, now);
}
 
int build(int now, int n)
{
  if (n == 1)
  {
    t[now].l = t[now].r = 0;
    return now;
  }
  int mid = n / 2;
  int l = build(now, mid);
  int r = build(t[l].rt, n - mid);
  t[l].r = t[r].l;
  t[r].l = l;
  return r;
}
 
void clear(int now)
{
  if (!now) return;
  clear(t2[now].l), clear(t2[now].r);
  s[tot4++] = now;
}
 
int together(int now1, int now2, int b)
{
  if (!now1 && !now2) return b ? mknode2(0, 0, 0) : 0;
  return mknode2(together(t2[now1].l, t2[now2].l, 0), together(t2[now1].r, t2[now2].r, 0), t2[now1].sum + t2[now2].sum);
}
 
void bld(int now)
{
  if (!now) return;
  bld(t[now].l), bld(t[now].r);
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum + 1;
  clear(t[now].root);
  t[now].root = together(t[t[now].l].root, t[t[now].r].root, 1);
  insert(t[now].root, t[now].v);
}
 
int rebuild(int now)
{
  int n = t[now].sum, p = MAXN - 1;
  t[MAXN - 1] = node(0, 0, 0, 0, 0);
  int k = link(now, p);
  build(k, n + 1);
  bld(t[p].l);
  return t[p].l;
}
 
int ins(int now, int p, int v)
{
  if (!root)
  {
    root = mknode(0, 0, v, 1, insert(mknode2(0, 0, 0), v));
    return root;
  }
  insert(t[now].root, v);
  ++t[now].sum;
 
  if (t[t[now].l].sum >= p - 1)
    if (t[now].l) t[now].l = ins(t[now].l, p, v);
    else t[now].l = mknode(0, 0, v, 1, insert(mknode2(0, 0, 0), v));
  else
    if (t[now].r) t[now].r = ins(t[now].r, p - 1 - t[t[now].l].sum, v);
    else t[now].r = mknode(0, 0, v, 1, insert(mknode2(0, 0, 0), v));
 
  if (max(t[t[now].l].sum, t[t[now].r].sum) >= (int)(t[now].sum * A))
    return rebuild(now);
  return now;
}
 
int modify(int now, int p, int v)
{
  insert(t[now].root, v);
  if (t[t[now].l].sum == p - 1)
  {
    int k = t[now].v;
    t[now].v = v;
    return del(t[now].root, k);
  }
 
  if (t[t[now].l].sum >= p - 1)
    return del(t[now].root, modify(t[now].l, p, v));
  else
    return del(t[now].root, modify(t[now].r, p - 1 - t[t[now].l].sum, v));
}
 
void deal(int l, int r, int now, int lf, int rt)
{
  if (l > r) return;
  if (l >= lf && r <= rt)
  {
    temp[tot3++] = t[now].root;
    return;
  }
  if (l > rt || r < lf) return;
  int k = l + t[t[now].l].sum;
  if (k >= lf && k <= rt) temp[tot3++] = -t[now].v;
  deal(l, k - 1, t[now].l, lf, rt);
  deal(k + 1, r, t[now].r, lf, rt);
}
 
int qu(int l, int r, int k)
{
  if (l == r) return l;
  int sum = 0, mid = (l + r) / 2, sum2 = 0;
  for (int i = 0; i < tot3; ++i)
    if (temp[i] > 1) sum += t2[t2[temp[i]].l].sum;
    else if (temp[i] <= 0) sum2 += ((-temp[i]) <= mid);
  if (sum + sum2 >= k)
  {
    for (int i = 0; i < tot3; ++i) if (temp[i] > 1) temp[i] = t2[temp[i]].l ? t2[temp[i]].l : 1;
    return qu(l, mid, k);
  }
  else
  {
    for (int i = 0; i < tot3; ++i) if (temp[i] > 1) temp[i] = t2[temp[i]].r ? t2[temp[i]].r : 1;
    return qu(mid + 1, r, k - sum);
  }
}
 
int query(int l, int r, int v)
{
  tot3 = 0;
  deal(1, n, root, l, r);
  return qu(0, MAXN, v);
}
 
int main()
{
  scanf("%d", &n);
  for (int i = 1; i < 20000005; ++i)
    s[tot4++] = i;
  for (int i = 1; i <= n; ++i)
  {
    int v;
    scanf("%d", &v);
    t[++tot].r = i + 1;
    t[tot].v = v;
    t[tot].root = mknode2(0, 0, 0);
  }
  t[n].r = 0; t[1].sum = n;
  root = rebuild(1);
  scanf("%d", &m);
  while (m--)
  {
    char c;
    int x, y;
    scanf("\n%c%d%d", &c, &x, &y);
    x ^= la, y ^= la;
    if (c == 'I') (root = ins(root, x, y)), ++n;
    if (c == 'M') modify(root, x, y);
    if (c == 'Q')
    {
      int k;
      scanf("%d", &k);
      k ^= la;
      printf("%d\n", la = query(x, y, k));
    }
  }
}

BZOJ 1926: [SDOI2010]粟粟的书架

这题有两部分
1:r、c<=200
这个开一个 f[x][y][k]的数组 表示(1, 1)~(x, y)矩阵里>=k的数的权值和
对一个询问做一次二分即可
2:r=1、c<=500000
无修改区间k大。。裸主席树=、=

——————code——————-

#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;
struct node
{
  int lf, rt, sum, num;
}t[10000000];
int f[201][201][1002], sum[201][201][1002], r, c, n, m, v[201][201], p, ss[500005], s[500005], root[500005];
int get(int x1, int y1, int x2, int y2, int k)
{
  return f[x2][y2][k] – f[x1 – 1][y2][k] – f[x2][y1 – 1][k] + f[x1 – 1][y1 – 1][k];
}
int get_s(int x1, int y1, int x2, int y2, int k)
{
  return sum[x2][y2][k] – sum[x1 – 1][y2][k] – sum[x2][y1 – 1][k] + sum[x1 – 1][y1 – 1][k];
}
int maketree(int l, int r)
{
  p++;
  if (l == r) return p;
  int mid = (l + r) / 2;
  t[p].lf = maketree(l, mid);
  t[p].rt = maketree(mid + 1, r);
  return p;
}
int ins(int now, int lr, int l, int r)
{
  p++;
  int no = p;
  t[no] = t[now];
  if (l == r)
  {
    ++t[no].num;
    t[no].sum += l;
    return no;
  }
  int mid = (l + r) / 2;
  if (lr <= mid) t[no].lf = ins(t[now].lf, lr, l, mid), t[no].rt = t[now].rt;
  else t[no].rt = ins(t[now].rt, lr, mid + 1, r), t[no].lf = t[now].lf;
  t[no].sum = t[t[no].lf].sum + t[t[no].rt].sum;
  t[no].num = t[t[no].lf].num + t[t[no].rt].num;
  return no;
}
int query(int now1, int now2, int l, int r, int h)
{
  if (l == r) return h ? (h – 1) / l + 1 : 0;
  int mid = (l + r) / 2;
  int tt = t[t[now2].rt].sum – t[t[now1].rt].sum;
  if (h >= tt) return t[t[now2].rt].num – t[t[now1].rt].num + query(t[now1].lf, t[now2].lf, l, mid, h – tt);
  else return query(t[now1].rt, t[now2].rt, mid + 1, r, h);
}
int main()
{
  cin >> r >> c >> m;
  if (r <= 200 && c <= 200)
  {
    for (int i = 1; i <= r; i++)
      for (int j = 1; j <= c; j++) scanf(“%d”, &v[i][j]);
    for (int x = 1; x <= r; ++x)
      for (int y = 1; y <= c; ++y)
      {
        for (int k = 1; k <= 1000; ++k)
          sum[x][y][k] = sum[x – 1][y][k] + sum[x][y – 1][k] – sum[x – 1][y – 1][k];
        ++sum[x][y][v[x][y]];
      }
    for (int x = 1; x <= r; ++x)
      for (int y = 1; y <= c; ++y)
        for (int k = 1000; k >= 1; –k)
          f[x][y][k] = f[x][y][k + 1] + k * sum[x][y][k],
          sum[x][y][k] = sum[x][y][k + 1] + sum[x][y][k];
    for (int i = 0; i < m; i++)
    {
      int x1, y1, x2, y2, h;
      scanf(“%d%d%d%d%d”, &x1, &y1, &x2, &y2, &h);
      if (get(x1, y1, x2, y2, 1) < h)
      {
        printf(“Poor QLW\n”);
        continue;
      }
      int l = 0;
      int r = 1001;
      while (l + 1 < r)
      {
        int mid = (l + r) / 2;
        if (get(x1, y1, x2, y2, mid) < h) r = mid;
        else l = mid;
      }
      int ans = get_s(x1, y1, x2, y2, r);
      if (r > 1 && h – get(x1, y1, x2, y2, r))
        ans += (h – get(x1, y1, x2, y2, r) – 1) / (r – 1) + 1;
      printf(“%d\n”, ans);
    }
  }
  else
  {
    n = c;
    for (int i = 1; i <= n; i++) scanf(“%d”, &s[i]), ss[i] = ss[i – 1] + s[i];
    root[0] = maketree(1, 1000);
    for (int i = 1; i <= n; i++)
      root[i] = ins(root[i – 1], s[i], 1, 1000);
    for (int i = 0; i < m; i++)
    {
      int x1, lf, x2, rt, h;
      scanf(“%d%d%d%d%d”, &x1, &lf, &x2, &rt, &h);
      if (ss[rt] – ss[lf – 1] < h)
      {
        printf(“Poor QLW\n”);
        continue;
      }
      printf(“%d\n”, query(root[lf – 1], root[rt], 1, 1000, h));
    }
  }

}