题目大意：给出一个字符串，给出一些询问，每次问几个后缀两两之间的LCP之和。

思路：保证Σask数量级在O(n)上，可以考虑一下虚树了。建立虚树之后，这题就和差异那个题一样了。但是必须要打时间戳啊，要不死的很惨的啊。。

CODE：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define MAX 1000010 using namespace std; struct Complex{ Complex *tranc[26],*father; int len,id; }none,*nil = &none,mempool[MAX],*C = mempool,*root,*last; int cnt = -1; Complex *NewComplex(int _) { C->id = ++cnt; C->len = _; fill(C->tranc,C->tranc + 26,nil); C->father = nil; return C++; } void Initialize() { root = last = NewComplex(0); fill(nil->tranc,nil->tranc + 26,nil); nil->father = nil; } int length,asks; char s[MAX]; inline void Add(int c) { Complex *np = NewComplex(last->len + 1),*p = last; for(; p != nil && p->tranc[c] == nil; p = p->father) p->tranc[c] = np; if(p == nil) np->father = root; else { Complex *q = p->tranc[c]; if(q->len == p->len + 1) np->father = q; else { Complex *nq = NewComplex(p->len + 1); memcpy(nq->tranc,q->tranc,sizeof(q->tranc)); nq->father = q->father; np->father = q->father = nq; for(; p != nil && p->tranc[c] == q; p = p->father) p->tranc[c] = nq; } } last = np; } int head[MAX],total; int next[MAX],aim[MAX]; int deep[MAX],father[MAX][20]; void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } int pos[MAX]; void DFS(int x,int last) { static int c = 0; deep[x] = deep[last] + 1; father[x][0] = last; pos[x] = ++c; for(int i = head[x]; i; i = next[i]) DFS(aim[i],x); } void SparseTable() { for(int j = 1; j <= 19; ++j) for(int i = 1; i <= cnt; ++i) father[i][j] = father[father[i][j - 1]][j - 1]; } inline int GetLCA(int x,int y) { if(deep[x] < deep[y]) swap(x,y); for(int i = 19; ~i; --i) if(deep[father[x][i]] >= deep[y]) x = father[x][i]; if(x == y) return x; for(int i = 19; ~i; --i) if(father[x][i] != father[y][i]) x = father[x][i],y = father[y][i]; return father[x][0]; } bool cmp(int x,int y) { return pos[x] < pos[y]; } int src[MAX]; namespace Graph{ int head[MAX],v_head[MAX],total; int next[MAX],aim[MAX]; int father[MAX],v_father[MAX]; int T; int ans; int size[MAX]; int v_set[MAX]; bool set[MAX]; void Reset() { ++T; total = 0; ans = 0; } void Add(int x,int y) { if(v_head[x] != T) { v_head[x] = T; head[x] = 0; } next[++total] = head[x]; aim[total] = y; head[x] = total; } void TreeDP(int x,int last) { if(v_set[x] != T) v_set[x] = T,set[x] = false; size[x] = set[x]; if(v_head[x] != T) { v_head[x] = T; head[x] = 0; } for(int i = head[x]; i; i = next[i]) { TreeDP(aim[i],x); size[x] += size[aim[i]]; } ans += size[x] * (size[x] - 1) * (mempool[x].len - mempool[last].len) >> 1; } } int p[MAX]; int main() { cin >> length >> asks; scanf("%s",s); Initialize(); for(int i = strlen(s) - 1; ~i; --i) p[i + 1] = cnt + 1,Add(s[i] - 'a'); for(int i = 1; i <= cnt; ++i) Add(mempool[i].father->id,mempool[i].id); DFS(0,0); SparseTable(); while(asks--) { int num; scanf("%d",&num); static int v[MAX],T = 0; ++T; int temp = 0; for(int x,i = 1; i <= num; ++i) { scanf("%d",&x); if(v[x] != T) src[++temp] = p[x],v[x] = T; } num = temp; sort(src + 1,src + num + 1,cmp); Graph::Reset(); int top = 0,end = num; static int stack[MAX]; for(int i = 1; i <= num; ++i) { if(!top) { stack[++top] = src[i]; Graph::v_set[src[i]] = Graph::T; Graph::set[src[i]] = true; continue; } int lca = GetLCA(stack[top],src[i]); Graph::v_father[src[i]] = Graph::T; Graph::father[src[i]] = lca; while(deep[stack[top]] > deep[lca]) { if(deep[stack[top - 1]] <= deep[lca]) { Graph::v_father[stack[top]] = Graph::T; Graph::father[stack[top]] = lca; } --top; } if(stack[top] != lca) { Graph::v_father[lca] = Graph::T; Graph::father[lca] = stack[top],stack[++top] = src[++end] = lca; } stack[++top] = src[i]; Graph::v_set[src[i]] = Graph::T; Graph::set[src[i]] = true; } for(int i = 1; i <= end; ++i) if(Graph::v_father[src[i]] == Graph::T) Graph::Add(Graph::father[src[i]],src[i]); if(Graph::v_head[0] != T) { Graph::v_head[0] = T; Graph::head[0] = 0; } Graph::TreeDP(0,0); printf("%d\n",Graph::ans); } return 0; }