题意：给定母串s和若干个询问。每个询问是一个串t和两个数l,r，表示求t中有多少个本质不同的子串没有在s[l,r]中出现过。
解：我写的并不是正解......是个毒瘤做法。只在loj上面卡时过了就写loj的题号好了...
首先有个68分部分分是l = 1， r = |s|，这个怎么做呢？
回忆起之前写的广义SAM的套路，我们建出广义SAM之后把s的所有子串标记。
然后对于每个t跑一遍SAM，跳fail的时候如果该节点被标记了就停止。这样走到的节点所代表的子串总数就是该串的答案。
68分还是比较友善的...
然后顺着这个思路思考正解。
多了个母串范围限制，又听说这个题是线段树合并，这就很自然了。
对于每个节点用值域线段树维护right集合，然后对于每一个询问，查看该节点是否有个right存在于[l,r]之间。存在就GG了，同时也不能往上传递。否则可以加上这个节点的贡献。有一种居中的情况就是一个节点所表示的串中，有些可选，有些不行。这种情况下不用向上传递(然而我当时没想到，传了...无伤大雅)
细节上就是找到那一段暧昧区域的最右边一个right，用线段树上找第k个实现。
那么我们要一个一个询问的处理吗？我很天真的以为线段树合并之后下面的线段树就不存在了....于是只能把询问一次性处理。于是我又SB的对询问开了个线段树，继续线段树合并......
具体来说，对于每个询问串，都在对应节点加上该串的询问。然后DFSfail树，在每一个节点遍历询问线段树，处理询问，然后向上合并。如果不会有贡献就删去这个节点，减少复杂度。
还有个小问题，right线段树合并的时候sum是两棵树的sum和，但是询问的那棵线段树合并要去重，所以不能把sum累加...然后发现询问线段树不需要查sum......这样就可以了。
因为加了很多常数优化所以代码不是很能看......复杂度分析也不会...反正估计也是不对的。uoj洛谷都T了。bzoj空间限制512M根本开不下。只有loj过了(loj牛逼！！！)
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <string> 5 #include <queue> 6 7 template <class T> inline void read(T &x) { 8 x = 0; 9 char c = getchar(); 10 while(c < ‘0‘ || c > ‘9‘) { 11 c = getchar(); 12 } 13 while(c >= ‘0‘ && c <= ‘9‘) { 14 x = (x << 3) + (x << 1) + c - 48; 15 c = getchar(); 16 } 17 return; 18 } 19 20 typedef long long LL; 21 const int N = 1000010, M = 4000010; 22 using std::string; 23 24 struct SGT { // 两个线段树合并 25 int tot, sum[M * 6], ls[M * 6], rs[M * 6], rt[M * 6], p, k; 26 std::queue<int> Q; 27 inline int np() { 28 if(Q.empty()) { 29 return ++tot; 30 } 31 int t = Q.front(); 32 Q.pop(); 33 sum[t] = ls[t] = rs[t] = 0; 34 return t; 35 } 36 void add(int l, int r, int &o) { 37 if(!o) { 38 o = np(); 39 } 40 if(l == r) { 41 sum[o]++; 42 return; 43 } 44 int mid = (l + r) >> 1; 45 if(p <= mid) { 46 add(l, mid, ls[o]); 47 } 48 else { 49 add(mid + 1, r, rs[o]); 50 } 51 sum[o] = sum[ls[o]] + sum[rs[o]]; 52 return; 53 } 54 int merge(int x, int y) { 55 if(!x || !y) { 56 return x | y; 57 } 58 int z = np(); 59 sum[z] = sum[x] + sum[y]; 60 ls[z] = merge(ls[x], ls[y]); 61 rs[z] = merge(rs[x], rs[y]); 62 Q.push(x); 63 Q.push(y); 64 return z; 65 } 66 int ask(int L, int R, int l, int r, int o) { 67 if(!o) { 68 return 0; 69 } 70 if(L <= l && r <= R) { 71 return sum[o]; 72 } 73 int mid = (l + r) >> 1, ans = 0; 74 if(L <= mid) { 75 ans += ask(L, R, l, mid, ls[o]); 76 } 77 if(mid < R) { 78 ans += ask(L, R, mid + 1, r, rs[o]); 79 } 80 return ans; 81 } 82 inline void exmerge(int x, int y) { 83 rt[x] = merge(rt[x], rt[y]); 84 return; 85 } 86 int getK(int l, int r, int o) { 87 if(l == r) { 88 return r; 89 } 90 int mid = (l + r) >> 1; 91 if(k <= sum[ls[o]]) { 92 return getK(l, mid, ls[o]); 93 } 94 else { 95 k -= sum[ls[o]]; 96 return getK(mid + 1, r, rs[o]); 97 } 98 } 99 }rt, st; 100 101 string str[N]; 102 char ss[N], s[N]; 103 int tot = 1, fail[M], len[M], e[M], tr[M][26], top, n, m, nodel[N], noder[N], edgenex[M], edgev[M]; 104 LL nodea[N]; 105 106 inline void add(int x, int y) { 107 top++; 108 edgev[top] = y; 109 edgenex[top] = e[x]; 110 e[x] = top; 111 return; 112 } 113 114 inline int split(int p, int f) { 115 int Q = tr[p][f]; 116 int nQ = ++tot; 117 len[nQ] = len[p] + 1; 118 fail[nQ] = fail[Q]; 119 fail[Q] = nQ; 120 memcpy(tr[nQ], tr[Q], sizeof(tr[Q])); 121 while(tr[p][f] == Q) { 122 tr[p][f] = nQ; 123 p = fail[p]; 124 } 125 return nQ; 126 } 127 128 inline int insert(int p, char c) { 129 int f = c - ‘a‘; 130 if(tr[p][f]) { 131 int Q = tr[p][f]; 132 if(len[Q] == len[p] + 1) { 133 return Q; 134 } 135 return split(p, f); 136 } 137 int np = ++tot; 138 len[np] = len[p] + 1; 139 while(p && !tr[p][f]) { 140 tr[p][f] = np; 141 p = fail[p]; 142 } 143 if(!p) { 144 fail[np] = 1; 145 } 146 else { 147 int Q = tr[p][f]; 148 if(len[Q] == len[p] + 1) { 149 fail[np] = Q; 150 } 151 else { 152 fail[np] = split(p, f); 153 } 154 } 155 return np; 156 } 157 158 void work(int l, int r, int &o, int x) { 159 if(!o || !st.sum[o]) { 160 if(o) { 161 st.Q.push(o); 162 } 163 o = 0; 164 return; 165 } 166 if(l == r) { 167 // node[r] 168 int sum = 0; 169 if(nodel[r] + len[fail[x]] <= noder[r]) { 170 sum = rt.ask(nodel[r] + len[fail[x]], noder[r], 1, n, rt.rt[x]); 171 } 172 if(!sum) { 173 nodea[r] += len[x] - len[fail[x]]; 174 } 175 else { 176 int temp = 0; 177 if(nodel[r] + len[x] - 1 <= noder[r]) { 178 temp = rt.ask(nodel[r] + len[x] - 1, noder[r], 1, n, rt.rt[x]); 179 } 180 if(temp) { 181 //GG 182 st.sum[o] = 0; 183 st.Q.push(o); 184 o = 0; 185 return; 186 } 187 else { 188 // add some... 189 // find ->| (the right pos) 190 rt.k = rt.ask(1, nodel[r] + len[x] - 2, 1, n, rt.rt[x]); 191 int ed = rt.getK(1, n, rt.rt[x]); 192 nodea[r] += len[x] - (ed - nodel[r] + 1); 193 } 194 } 195 return; 196 } 197 int mid = (l + r) >> 1; 198 if(st.ls[o]) { 199 work(l, mid, st.ls[o], x); 200 } 201 if(st.rs[o]) { 202 work(mid + 1, r, st.rs[o], x); 203 } 204 st.sum[o] = st.sum[st.ls[o]] + st.sum[st.rs[o]]; 205 if(!st.sum[o]) { 206 st.Q.push(o); 207 o = 0; 208 } 209 return; 210 } 211 212 void solve(int x) { 213 for(int i = e[x]; i; i = edgenex[i]) { 214 int y = edgev[i]; 215 solve(y); 216 if(x > 1) { 217 rt.exmerge(x, y); 218 } 219 } 220 if(x > 1) { 221 work(1, m, st.rt[x], x); 222 if(fail[x] > 1) { 223 st.exmerge(fail[x], x); 224 } 225 } 226 return; 227 } 228 229 int main() { 230 231 //freopen("name.in", "r", stdin); 232 //freopen("name.out", "w", stdout); 233 234 scanf("%s", ss); 235 n = strlen(ss); 236 int last = 1; 237 for(int i = 0; i < n; i++) { 238 last = insert(last, ss[i]); 239 } 240 read(m); 241 for(int i = 1; i <= m; i++) { 242 scanf("%s", s); 243 str[i] = (string)(s); 244 int t = strlen(s); 245 last = 1; 246 for(int j = 0; j < t; j++) { 247 last = insert(last, s[j]); 248 } 249 read(nodel[i]); 250 read(noder[i]); 251 } 252 // 253 int p = 1; 254 for(int i = 0; i < n; i++) { 255 p = tr[p][ss[i] - ‘a‘]; 256 rt.p = i + 1; 257 rt.add(1, n, rt.rt[p]); 258 } 259 for(int i = 2; i <= tot; i++) { 260 add(fail[i], i); 261 } 262 263 for(int i = 1; i <= m; i++) { 264 int t = str[i].size(), p = 1; 265 for(int j = 0; j < t; j++) { 266 // str[i][j] 267 p = tr[p][str[i][j] - ‘a‘]; 268 st.p = i; 269 st.add(1, m, st.rt[p]); 270 } 271 } 272 273 solve(1); 274 275 for(int i = 1; i <= m; i++) { 276 printf("%lld\n", nodea[i]); 277 } 278 return 0; 279 }
正解不是广义SAM，是普通SAM，还不用离线......还是我太菜了>_<
时限4s，你们感受一下...尤其是跟下面那个AC代码的对比......
原文：https://www.cnblogs.com/huyufeifei/p/10335861.html
