用C语言写一段代码实现给定一个字符串s和两个字符c1,c2,均保证只含有小写字母，求出有多少个s的子串，符合以c1开头，以C2结束。n的范围为1到10的5次方使用并查集

很高兴能为您解答问题！以下是用C语言写一段代码实现给定一个字符串s和两个字符c1,c2,均保证只含有小写字母，求出有多少个s的子串，符合以c1开头，以C2结束，同时使用并查集的代码：

#include <stdio.h>
#include <string.h>

const int MAXN = 1e5 + 5;

int fa[MAXN], cnt[MAXN], used[MAXN];

int find(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        fa[x] = y;
        cnt[y] += cnt[x];
    }
}

int main() {
    char s[MAXN], c1, c2;
    scanf("%s %c %c", s, &c1, &c2);

    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        cnt[i] = 1;
        used[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        if (s[i] == c1)
            used[i] = 1;
        else if (i > 0 && used[i - 1])
            merge(i - 1, i);
    }
    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == c2 && used[i])
            ans += cnt[find(i)];
        else if (i < n - 1 && used[i + 1])
            merge(i, i + 1);
    }

    printf("%d\n", ans);
    return 0;
}

具体思路：

我们可以先遍历一遍字符串s，并用并查集来维护以字符c1开头的子串，然后再从后往前遍历字符串，用并查集来维护以字符c2结尾的子串，并在遍历过程中计算符合要求的子串个数。

具体来说，我们可以遍历一遍字符串s，用一个数组used来记录字符串中以字符c1开头的位置，然后再遍历一遍字符串s，每次遇到以字符c2结尾的位置i，如果used[i]为1，说明以字符c1开头、以字符c2结尾的子串就是以i结尾、以c1开头的所有子串的总数，我们可以通过并查集来维护这一点。

具体来说，我们可以用一个数组cnt来记录每个集合（即并查集中的一棵树）中元素的个数，然后每次合并两个集合时，我们将cnt[x]的值加到cnt[y]上即可。这样，对于以i结尾、以c1开头的所有子串的总数，我们可以通过查找集合中以i结尾的元素个数得到。

具体实现时，我们可以用并查集来维护以字符c1开头、以字符c2结尾的子串，具体如下：

- 初始化并查集：将每个位置i初始化为一个集合，并将其父亲设为i，初始的计数器cnt[i]都为1。
- 对于以字符c1开头的位置i，我们将used[i]设为1，表示这个位置可以作为一个以c1开头的子串，然后如果前一个位置j有used[j]=1，说明当前位置可以和前一个位置构成一个符合要求的子串，我们就把它们合并。
- 从后往前遍历，对于每个位置i，如果s[i]等于c2且used[i]等于1，说明以i结尾、以c1开头的子串是符合要求的子串，我们就累加以i结尾、以c1开头的所有子串的数量cnt[find(i)]。
- 如果s[i]不等于c2，或者used[i]等于0，我们就可以通过查看当前节点和其下一个节点所在的集合，并在需要时将两个集合合并。

最后统计cnt[find(i)]即可。

希望我的回答能解决您的问题。如有疑问，欢迎继续追问！