BZOJ – hahaschool

题意

给出一系列的字符串，我们把这些串叫母串，然后给你若干字符串，对于每一个字符串，你要求出在多少个母串中可以找到和给出的字符串相同的母串的字串。

思路

子串问题，要借助后缀系列解决，这个题使用了后缀自动机。但是通常意义的后缀自动机都是针对一个母串建立的，现在我们手里有一堆母串，这时候就需要我们进行活用，来创建“广义后缀自动机”，这个自动机将可以接受母串集合里所有的字串。

广义后缀自动机的建立方法其实是在一般的自动机创建基础之上，增加了一些东西。构造后缀自动机的方法是增量法，构造广义后缀自动机的方法也是一样的，但是我们从第个二串开始，一位一位增量的时候，我们有可能会用到构造到一半的自动机的某些节点或者某些转移边。对于当前将要加入的mxn(最长可接受字串长度)值，和当前追加节点时的last，如果last有一条转移边可以用，而且即将加入的新节点的mxn值正好等于last的mxn+1，这说明既存的节点和我们将要加入的节点是等价的，这一轮的追加到这里就可以结束了。如果存在转移边，但是转移边连着的节点mxn值并不是last的mxn+1，这个时候就需要我们使用在平常构造后缀自动机中使用的“拆点”方法。复制既存的节点作为符合我们mxn要求的节点，调整parent关系和所有自动机上父亲节点的转移关系，就像我们在平常构造自动机时为了防止mxn异常缩短采用的“拆点”方法一样。如果last节点不存在可用的转移边，这时候按照普通的增量法处理就可以。(如果觉得费解，不妨直接参考我的MultiSAM_Append()方法)。

创建完广义后缀自动机，这还只是个开始。接下来我们要提取出自动机中的所有的parent关系，创建parent树。我们注意到，在parent树中，一个节点的子树代表的是以这个节点为后缀的全部字串。举个例子就是，对于“banana”的”ana”代表节点(mxn值3)，他的子树就代表了”ana“,”nana“,”bana“,”anana“,”banana“，这一系列字串。这一特性有什么用呢？

注意到题意，我们要找到给出的串在多少个串中匹配，如果我们按照正常的方法在广义后缀自动机上完整地匹配这个串（如果匹配有中断，那就说明这个串不存在于母串集合的字串当中），这个时候转移到的最终状态对应节点的parent树的子树，就是在母串集合中所有的以给出的串为后缀的字串。如果我们给parent树上的每一个节点挂一个列表，标记这个节点都被哪些字符串利用了，这样只要我们逐一统计子树中的每一个节点，就可以知道当前给出的串在几个母串中存在，问题就可以解决了。

但是对于每一棵子树都统计一次，复杂度很大，显然需要再优化。优化的方法就是“DFS序把树压平”然后“离线处理”。首先遍历parent树，纪录每一个节点进入时的DFN和出去时的DFN，从进去到出去这两个DFN之间的所有节点(包括出入两个节点)显然就是parent的子树了。现在我们的问题就转变为了在某个数组上一段给定的区间求有多少个不同的数字，而且还是离线处理，这种问题可以使用一种O(n)的处理方法，详情可以参考BZOJ 1878 HH的项链。

问题到了这里，终于是完美地解决了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

const int MAXN = 200010;

int tot = 0;

#pragma mark - Binary Indexed Tree (BIT) 1D
//index begins from ONE
//init:memset BIT,set BIT_size
int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int
int BIT_size;//should assign when use

inline int lowbit(int a){
    return a & (-a);
}

void BIT_modify(int pos,int delta){//type of delta may need to modify
    for (int x = pos; x <= BIT_size; x += lowbit(x)) {
        BIT[x] += delta;
    }
}

int BIT_sum(int pos){//return type may alter
    int ret = 0;
    for (int x = pos; x > 0; x -= lowbit(x)) {
        ret += BIT[x];
    }
    return ret;
}
#pragma mark -

struct Graph{//Chained Linear Edges
    int head[MAXN];
    int next[MAXN];
    int to[MAXN];
    inline void addEdge(int _from,int _to){
        static int q = 1;//!!
        to[q] = _to;
        next[q] = head[_from];
        head[_from] = q++;
    }
} parentTree,idx;

struct Query{
    int id,ans,from,to;
} query[60010];

bool cmp1(const Query &a,const Query &b){
    return a.to < b.to;
}

bool cmp2(const Query &a,const Query &b){
    return a.id < b.id;
}


struct SAM_State{
    int mxn;
    int id;
    SAM_State *to[26];
    SAM_State *parent;
    SAM_State(int _mxn){
        mxn = _mxn;
        id = ++tot;
        memset(to, 0, sizeof(to));
        parent = NULL;
    }
} *state[MAXN];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = new SAM_State(p -> mxn + 1);
    state[np -> id] = np;
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = new SAM_State(p -> mxn + 1);
            state[nq -> id] = nq;
            nq -> parent = q -> parent;
            q -> parent = nq;
            np -> parent = nq;
            memcpy(nq -> to, q -> to, sizeof(q -> to));
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

SAM_State* MultiSAM_Append(SAM_State *last, SAM_State *root,int ch){
    SAM_State *p = last;
    if (p -> to[ch] != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            last = q;
        }else {
            SAM_State *nq = new SAM_State(p -> mxn + 1);
            state[nq -> id] = nq;
            nq -> parent = q -> parent;
            q -> parent = nq;
            memcpy(nq -> to, q -> to, sizeof(q -> to));
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
            last = nq;
        }
    }else{
        return SAM_Append(last, root, ch);
    }
    return last;
}

void MultiSAM_Build(int num,char* str,SAM_State *root){
    SAM_State *last = root;
    int len = (int)strlen(str);
    for (int i = 0; i < len; i++) {
        last = MultiSAM_Append(last, root, str[i] - 'a');
        idx.addEdge(last -> id, num);
    }
}

SAM_State* SAM_Match(char *str,SAM_State *root){//only for this problem
    SAM_State *sam = root;
    int len = (int)strlen(str);
    for (int i = 0; i < len; i++) {
        if (sam -> to[str[i] - 'a']) {
            sam = sam -> to[str[i] - 'a'];
        }else{
            return NULL;
        }
    }
    return sam;
}

int in[MAXN],out[MAXN],seq[MAXN],dfn = 0;//dfn begins from 1
void dfs_getdfn(int cur){
    in[cur] = ++dfn;
    seq[dfn] = cur;
    for (int i = parentTree.head[cur]; i; i = parentTree.next[i]) {
        dfs_getdfn(parentTree.to[i]);
    }
    out[cur] = dfn;
}

char container[360010];
int prv[MAXN];
int main(){
    int n,m;
    scanf(" %d %d",&n,&m);
    state[1] = new SAM_State(0);
    for (int i = 1; i <= n; i++) {
        scanf(" %s",container);
        MultiSAM_Build(i,container, state[1]);
    }

    for (int i = 1; i <= tot; i++) {
        if (state[i] -> parent) {
            parentTree.addEdge(state[i] -> parent -> id, state[i] -> id);
        }
    }
    dfs_getdfn(1);
    for (int i = 1; i <= m; i++) {
        scanf(" %s",container);
        SAM_State *pos = SAM_Match(container, state[1]);
        if (pos != NULL) {
            query[i].id = i;
            query[i].from = in[pos -> id];
            query[i].to = out[pos -> id];
        }else{
            query[i].id = i;
            query[i].from = -1;
            query[i].to = -1;
        }
    }
    sort(query+1, query+1+m, cmp1);

    BIT_size = tot;
    int k = 1;
    while (query[k].to == -1) {
        k++;
    }
    for (int i = 1; i <= tot; i++) {
        for (int j = idx.head[seq[i]]; j; j = idx.next[j]) {
            if (prv[idx.to[j]]) {
                BIT_modify(prv[idx.to[j]], -1);
            }
            BIT_modify(prv[idx.to[j]] = i, 1);
        }
        for (; i == query[k].to && k <= m; k++) {
            query[k].ans = BIT_sum(query[k].to) - BIT_sum(query[k].from - 1);
        }
    }
    sort(query+1, query+1+m, cmp2);
    for (int i = 1; i <= m; i++) {
        printf("%d\n",query[i].ans);
    }

    return 0;
}

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

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

const int MAXN = 200010;

int tot = 0;

#pragma mark - Binary Indexed Tree (BIT) 1D

//index begins from ONE

//init:memset BIT,set BIT_size

int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int

int BIT_size;//should assign when use

inline int lowbit(int a){

return a & (-a);

}

void BIT_modify(int pos,int delta){//type of delta may need to modify

for (int x = pos; x <= BIT_size; x += lowbit(x)) {

BIT[x] += delta;

}

int BIT_sum(int pos){//return type may alter

int ret = 0;

for (int x = pos; x > 0; x -= lowbit(x)) {

ret += BIT[x];

}

return ret;

}

#pragma mark -

struct Graph{//Chained Linear Edges

int head[MAXN];

int next[MAXN];

int to[MAXN];

inline void addEdge(int _from,int _to){

static int q = 1;//!!

to[q] = _to;

next[q] = head[_from];

head[_from] = q++;

}

} parentTree,idx;

struct Query{

int id,ans,from,to;

} query[60010];

bool cmp1(const Query &a,const Query &b){

return a.to < b.to;

}

bool cmp2(const Query &a,const Query &b){

return a.id < b.id;

}

struct SAM_State{

int mxn;

int id;

SAM_State *to[26];

SAM_State *parent;

SAM_State(int _mxn){

mxn = _mxn;

id = ++tot;

memset(to, 0, sizeof(to));

parent = NULL;

}

} *state[MAXN];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = new SAM_State(p -> mxn + 1);

state[np -> id] = np;

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = new SAM_State(p -> mxn + 1);

state[nq -> id] = nq;

nq -> parent = q -> parent;

q -> parent = nq;

np -> parent = nq;

memcpy(nq -> to, q -> to, sizeof(q -> to));

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

SAM_State* MultiSAM_Append(SAM_State *last, SAM_State *root,int ch){

SAM_State *p = last;

if (p -> to[ch] != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

last = q;

}else {

SAM_State *nq = new SAM_State(p -> mxn + 1);

state[nq -> id] = nq;

nq -> parent = q -> parent;

q -> parent = nq;

memcpy(nq -> to, q -> to, sizeof(q -> to));

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

last = nq;

}

}else{

return SAM_Append(last, root, ch);

}

return last;

}

void MultiSAM_Build(int num,char* str,SAM_State *root){

SAM_State *last = root;

int len = (int)strlen(str);

for (int i = 0; i < len; i++) {

last = MultiSAM_Append(last, root, str[i] - 'a');

idx.addEdge(last -> id, num);

}

SAM_State* SAM_Match(char *str,SAM_State *root){//only for this problem

SAM_State *sam = root;

int len = (int)strlen(str);

for (int i = 0; i < len; i++) {

if (sam -> to[str[i] - 'a']) {

sam = sam -> to[str[i] - 'a'];

}else{

return NULL;

}

return sam;

}

int in[MAXN],out[MAXN],seq[MAXN],dfn = 0;//dfn begins from 1

void dfs_getdfn(int cur){

in[cur] = ++dfn;

seq[dfn] = cur;

for (int i = parentTree.head[cur]; i; i = parentTree.next[i]) {

dfs_getdfn(parentTree.to[i]);

}

out[cur] = dfn;

}

char container[360010];

int prv[MAXN];

int main(){

int n,m;

scanf(" %d %d",&n,&m);

state[1] = new SAM_State(0);

for (int i = 1; i <= n; i++) {

scanf(" %s",container);

MultiSAM_Build(i,container, state[1]);

}

for (int i = 1; i <= tot; i++) {

if (state[i] -> parent) {

parentTree.addEdge(state[i] -> parent -> id, state[i] -> id);

}

dfs_getdfn(1);

for (int i = 1; i <= m; i++) {

scanf(" %s",container);

SAM_State *pos = SAM_Match(container, state[1]);

if (pos != NULL) {

query[i].id = i;

query[i].from = in[pos -> id];

query[i].to = out[pos -> id];

}else{

query[i].id = i;

query[i].from = -1;

query[i].to = -1;

}

sort(query+1, query+1+m, cmp1);

BIT_size = tot;

int k = 1;

while (query[k].to == -1) {

k++;

}

for (int i = 1; i <= tot; i++) {

for (int j = idx.head[seq[i]]; j; j = idx.next[j]) {

if (prv[idx.to[j]]) {

BIT_modify(prv[idx.to[j]], -1);

}

BIT_modify(prv[idx.to[j]] = i, 1);

}

for (; i == query[k].to && k <= m; k++) {

query[k].ans = BIT_sum(query[k].to) - BIT_sum(query[k].from - 1);

}

sort(query+1, query+1+m, cmp2);

for (int i = 1; i <= m; i++) {

printf("%d\n",query[i].ans);

}

return 0;

}

题意

给出一个数列，问你好多次在这个序列上某一段里面有多少不同的数。数列没有发生更新。

思路

因为没有发生更新，所以可以采用这样的一种方法：

首先接收好全部的查询请求，然后把查询请求按照右端点从小到大排列。接下来，我们已Sample为例“1 2 3 4 3 5”，首先看1，这个数没有出现过，我们给一号位置标记一个1，然后看2，没出现过，标记一个1，然后3号位的3没出现过，标上1，然后四号位标1，然后到了五号位，我们发现3出现过了，所以要把之前出现过的三号位的1抹去，给5号位标上1，到了六号位，是5，没出现过，标记上1。

我们发现，在上面这个过程中，只要我们照着这种方法来标记，就可以确保检查到i号位的时候，所有1～i这个区间的询问都是准确的，也就是说我们一次处理一位的标记情况，之后就可以处理掉所有以这一位为右端点的询问，询问的结果就是被询问的那一段区间的标记之和。区间和当然要优化，可以使用BIT。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

#define MAXN 50005

#pragma mark - Binary Indexed Tree (BIT) 1D
//index begins from ONE
//init:memset BIT,set BIT_size
int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int
int BIT_size;//should assign when use

inline int lowbit(int a){
    return a & (-a);
}

void BIT_modify(int pos,int delta){//type of delta may need to modify
    for (int x = pos; x <= BIT_size; x += lowbit(x)) {
        BIT[x] += delta;
    }
}

int BIT_sum(int pos){//return type may alter
    int ret = 0;
    for (int x = pos; x > 0; x -= lowbit(x)) {
        ret += BIT[x];
    }
    return ret;
}
#pragma mark -

int prv[MAXN*20];
int seq[MAXN];
int res[MAXN*4];

struct Query{
    int l,r,id,res;
} query[MAXN*4];

bool cmp1(const Query &a,const Query &b){
    return a.r < b.r;
}

bool cmp2(const Query &a,const Query &b){
    return a.id < b.id;
}

int main(){
    int n;
    while(scanf(" %d",&n) != EOF){
        memset(BIT, 0, sizeof(BIT));
        BIT_size = n;
        memset(prv, 0, sizeof(prv));
        for (int i = 1; i <= n; i++) {
            scanf(" %d",&seq[i]);
        }
        int q;
        scanf(" %d",&q);
        for (int i = 1; i <= q; i++) {
            scanf(" %d %d",&query[i].l,&query[i].r);
            query[i].id = i;
        }
        sort(query+1, query+1+q,cmp1);
        int k = 1;
        for (int i = 1; i <= n; i++) {
            if (prv[seq[i]]) {
                BIT_modify(prv[seq[i]], -1);
            }
            BIT_modify(prv[seq[i]] = i, 1);
            for (; query[k].r == i; k++) {
                query[k].res = BIT_sum(i) - BIT_sum(query[k].l-1);
            }
        }
        sort(query+1, query+1+q, cmp2);
        for (int i = 1; i <= q; i++) {
            printf("%d\n",query[i].res);
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#define MAXN 50005

#pragma mark - Binary Indexed Tree (BIT) 1D

//index begins from ONE

//init:memset BIT,set BIT_size

int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int

int BIT_size;//should assign when use

inline int lowbit(int a){

return a & (-a);

}

void BIT_modify(int pos,int delta){//type of delta may need to modify

for (int x = pos; x <= BIT_size; x += lowbit(x)) {

BIT[x] += delta;

}

int BIT_sum(int pos){//return type may alter

int ret = 0;

for (int x = pos; x > 0; x -= lowbit(x)) {

ret += BIT[x];

}

return ret;

}

#pragma mark -

int prv[MAXN*20];

int seq[MAXN];

int res[MAXN*4];

struct Query{

int l,r,id,res;

} query[MAXN*4];

bool cmp1(const Query &a,const Query &b){

return a.r < b.r;

}

bool cmp2(const Query &a,const Query &b){

return a.id < b.id;

}

int main(){

int n;

while(scanf(" %d",&n) != EOF){

memset(BIT, 0, sizeof(BIT));

BIT_size = n;

memset(prv, 0, sizeof(prv));

for (int i = 1; i <= n; i++) {

scanf(" %d",&seq[i]);

}

int q;

scanf(" %d",&q);

for (int i = 1; i <= q; i++) {

scanf(" %d %d",&query[i].l,&query[i].r);

query[i].id = i;

}

sort(query+1, query+1+q,cmp1);

int k = 1;

for (int i = 1; i <= n; i++) {

if (prv[seq[i]]) {

BIT_modify(prv[seq[i]], -1);

}

BIT_modify(prv[seq[i]] = i, 1);

for (; query[k].r == i; k++) {

query[k].res = BIT_sum(i) - BIT_sum(query[k].l-1);

}

sort(query+1, query+1+q, cmp2);

for (int i = 1; i <= q; i++) {

printf("%d\n",query[i].res);

}

return 0;

}

Tag: BZOJ

BZOJ 2780 / SPOJ JZPGYZ Sevenk Love Oimaster

题意

思路

代码

BZOJ 1878 HH的项链

题意

思路

代码