相似度查询

普通解法

每次交换直接交换。每次查询都暴力匹配，存下现在可能的最长公共前缀长度len然后对于每个新串只要匹配前len个字符即可。
时间复杂度。显然这个时间复杂度不足以通过此题。

vector<int> solve(int n, vector<string>& s, int m, vector<int> &op, vector<int>& l, vector<int>& r) {
        vector<int> ans;
        for(int i = 0; i < m; ++i){
            if(op[i] == 1){
                if(l[i] == r[i]) continue;
                else swap(s[l[i]-1], s[r[i]-1]);
                continue;
            }
            if(l[i] == r[i]) ans.push_back(s[l[i]-1].size());
            else{
                int len = s[l[i]-1].size();
                for(int j = l[i]; j < r[i] ; ++j){
                    len = min(len,(int) s[j].size());
                    for(int k = 0; k < len ; ++k){
                        if(s[j][k] != s[j-1][k]){
                            len = k; break;
                        }
                    }
                }
                ans.push_back(len);
            }
        }
        return ans;
    }

最优解法

先对所有字符串建立一个字典树
考虑查询两个字符串的最长公共前缀的时候，相当于是查询它们对应的字典树结点在字典树上的公共祖先的深度。这就转化成了求树上最近公共祖先问题，可以通过树上倍增在的时间复杂度求出。
现在要求多个字符串的最长公共前缀，相当于求多个点在树上的最近公共祖先。按照dfs序把这些点排列之后，可以发现其实它们最近树上公共祖先是由dfs序最小的点和dfs序最大的点决定的。所以我们只要找出区间内DFS序最小的点和DFS序最大的点就可以了。
当需要交换字符串的时候，在线段树上修改对应位置的DFS序即可，而不用去操作串。

所以这题的解题步骤为：

1. 建立字典树，求出每个字符串在字典树上对应的结点编号
2. 从根结点开始DFS，求出倍增数组和整棵树的DFS序，求出每个结点对应的DFS序编号。
3. 建立线段树维护区间最小值和区间最大值。[l,r]区间内维护的是[l,r]区间内的字符串对应的结点的最小/大DFS序。
4. 查询的时候先在线段树上查询DFS序最小/最大的结点，然后求出它们的最近公共祖先，它的深度就是答案。
5. 修改的时候，在线段树上修改对应位置的DFS序值，再交换两个字符串对应的结点编号。

需要倍增数组和字典树，所以空间复杂度为
求倍增数组复杂度为，单次线段树查询复杂度为，单次LCA查询复杂度为,总时间复杂度为

int ch[1000005][26], tot = 0;
int f[1000005][20];
int dfn[1000005], idx = 0, id[1000005], dep[1000005];
int to[1000005];
void dfs(int u){
    if(!u) return;
    for(int i = 1; i < 20; ++i) f[u][i] = f[f[u][i-1]][i-1];
    dfn[++idx] = u; id[u] = idx;
    for(int i = 0; i < 26; ++i) dfs(ch[u][i]);
}
int mi[1000005*4], mx[1000005*4];
void build(int rt, int l, int r){
    if(l == r){
        mx[rt] = mi[rt] = id[to[l]]; return;
    }
    int mid = (r+l)>>1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    mx[rt] = max(mx[rt<<1], mx[rt<<1|1]);
    mi[rt] = min(mi[rt<<1], mi[rt<<1|1]);
    return;
}
int qry(int rt, int l, int r, int L, int R, int op){//0 mi  1 mx
    if(L <= l && r <= R)
        return (op==1) ? mx[rt] : mi[rt];
    int res; if(op == 0) res = 0x3f3f3f3f; else res = 0;
    int mid = (r+l)>>1;
    if(L <= mid) {
        if(op == 0) res = min(res, qry(rt<<1, l, mid, L, R, op));
        else res = max(res, qry(rt<<1, l, mid, L, R, op));
    }
    if(R > mid){
        if(op == 0) res = min(res, qry(rt<<1|1, mid+1, r, L, R, op));
        else res = max(res, qry(rt<<1|1, mid+1, r, L, R, op));
    } return res;
}
void update(int rt, int l, int r, int pos, int x){
    if(l == r){
        mx[rt] = mi[rt] = x; return;
    }
    int mid = (r+l)>>1;
    if(pos <= mid) update(rt<<1, l, mid, pos, x);
    else update(rt<<1|1, mid+1, r, pos, x);
    mx[rt] = max(mx[rt<<1], mx[rt<<1|1]);
    mi[rt] = min(mi[rt<<1], mi[rt<<1|1]);
}
int lca(int u, int v){
    if(dep[v] < dep[u]) swap(u, v);
    int d = dep[v]-dep[u];
    for(int i = 19; i >= 0; --i) if(d>>i&1) v = f[v][i];
    if(u == v) return u;
    for(int i = 19; i >= 0; --i){
        if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    }return f[u][0];
}
int newnode(){
    tot++;
    memset(ch[tot], 0, sizeof ch[tot]); return tot;
}
vector<int> solve(int n, vector<string> &s, int m,vector<int> &op, vector<int> &l, vector<int> &r){
    assert(s.size() == n);
    idx = 0;
    tot = 0; int rt = newnode(); dep[rt] = 0; f[rt][0] = 0;
    for(int i = 0; i < s.size(); ++i){
        int p = rt;
        for(int j = 0; j < s[i].size(); ++j){
            int x = s[i][j]-'a';
            if(!ch[p][x]) ch[p][x] = newnode(), f[ch[p][x]][0] = p, dep[ch[p][x]] = dep[p]+1;
            p = ch[p][x];
        }
        to[i+1] = p;
    }
    dfs(rt);
    build(1, 1, n);
    vector<int> ans; ans.clear();
    assert(l.size() == r.size() && r.size() == m);
    for(int i = 0; i < m; ++i){
        if(op[i] == 1){
            if(l[i] == r[i]) continue;
            update(1, 1, n, l[i], id[to[r[i]]]);
            update(1, 1, n, r[i], id[to[l[i]]]);
            swap(to[l[i]], to[r[i]]);
            continue;
        }
        assert(op[i] == 2);
        assert(l[i] <= r[i] && l[i] > 0 && r[i] <= n);
        int u = qry(1, 1, n, l[i], r[i], 0);u = dfn[u];
        int v = qry(1, 1, n, l[i], r[i], 1);v = dfn[v];
        int p = lca(u, v);
        ans.push_back(dep[p]);
    }return ans;
}