面试了个36岁的大哥，技术底子那是真硬，架构设计头头是道，甚至还能手写源码，才18k。结果HR那边直接卡住...

刚看到个贴子，说是面了个36岁的大哥，技术稳得一批，架构设计说得明明白白，薪资也就十八K，结果被 HR 以“没潜力、性价比低”给卡了。

网友们也有说“年轻便宜好用”，但我觉得有点片面。说到底，公司招人是为了干活，不是为了做公益。一个能直接上手的人，被嫌弃潜力不够，不懂怎么想的！

换个角度想，30+ 的价值不是潜力，而是稳定、经验、靠谱，这些在项目里才是真金白银。有网友说年轻人便宜，但便宜往往要老员工擦屁股，这算哪门子性价比？

不过话说回来，职场嘛，双方都在算账。希望企业别把“潜力”当挡箭牌，也别忽略成熟人才的价值。【备注:文末可领最新资料】

面试题：变更性别

写这个题之前，咱先把“变更性别”这仨字翻成程序员听得懂的话：一串男女同学排队，老师老喜欢搞事情——“把 2 到 5 号同学性别都反一下”“问问 3 到 7 号里面有几个男生”……你要写个程序，把这些操作都快速处理了。

我们自己把题意定完整一点（方便讲算法）：

• 有 n 个同学，从 1 到 n 排队。

• 用一个长度为 n 的字符串表示初始性别：

• 'M' 表示男（male）
• 'F' 表示女（female）

• 之后有 q 次操作，两种类型：

1. C l r：把区间 [l, r] 里的性别全部翻转

• 男变女、女变男

要求：n 和 q 都可能是 10^5 级别的，如果你每次都一个一个去改、一个一个去数，肯定超时。

暴力做法为啥不行？

最朴素的想法：

• 用一个列表存性别，比如 ['M', 'F', 'M', ...]

• 遇到 C l r：

• for i in [l, r] 把 'M' 换成 'F'，反之亦然，复杂度 O(r-l+1)

• 遇到 Q l r：

• for i in [l, r] 数一数 'M' 的个数，也是 O(r-l+1)

最坏情况：每个操作都改 / 查整个数组，就是 q * n10^5 * 10^5 = 10^10，这在 Python 里铁定超时。

所以核心问题就一句话：怎么在支持区间翻转的同时，又能快速统计区间里有多少男生？

把性别数字化一下

先做一件小事：把性别转成 0/1，更好算：

• 定义 1 表示男生
• 0 表示女生

那一个区间 [l, r] 里男生数量，就是这个区间的“和”。

翻转性别就变成：

• 0 变 1
• 1 变 0

如果区间长度是 len，原来这段区间里有 sum 个男生，翻转之后：

• 女生变男生：len - sum
• 男生变女生：sum 变女生数量 所以 **翻转后的男生数 = len - sum**。

也就是说： 对一个区间做“翻转”操作，其实就是把这个区间的“男生数量”改成 len - 原来的值。这点很重要，等会儿用在线段树的懒标记里。

为啥要上线段树 + 懒标记？

我们要支持两种区间操作：

• 区间翻转：C l r
• 区间求和：Q l r（统计男生数）

非常标准的“区间修改 + 区间查询”场景，用 线段树（Segment Tree）+ 懒惰标记（Lazy Propagation） 就比较合理：

在线段树每个节点里存三样信息：

• l, r：这个节点代表的区间左右端点
• sum：这个区间里有多少男生
• lazy_flip：一个布尔值（0/1），表示“这一段是否需要翻转但还没往下传”

关键逻辑：

1. 当对一个节点 [l, r] 做“整段翻转”时：

• 它的 sum 变成 len - sum
• lazy_flip ^= 1（翻转标记异或一下，相当于“再来一刀又翻回来”）

• 把这个懒标记推给左右孩子
• 同样更新左右孩子的 sum 和 lazy_flip
• 然后把当前节点的 lazy_flip 清零

这样，每次区间修改和区间查询的复杂度都是 O(log n)，10^5 级别完全扛得住。

下面直接上一个可跑的实现，默认输入格式类似：

n q
MFMFMF...
C 2 5
Q 1 3
...

代码：

import sys
sys.setrecursionlimit(1_000_000)


classSegmentTree:
def__init__(self, arr):
        self.n = len(arr)
# 开 4n 比较保险
        self.sum = [0] * (4 * self.n)        # 区间男生数量
        self.lazy = [0] * (4 * self.n)       # 懒标记：是否需要翻转
        self._build(1, 1, self.n, arr)

def_build(self, idx, l, r, arr):
"""建树：把初始性别数组灌进线段树"""
if l == r:
            self.sum[idx] = arr[l - 1]   # arr 是 0-based，下标注意一下
return
        mid = (l + r) // 2
        self._build(idx * 2, l, mid, arr)
        self._build(idx * 2 + 1, mid + 1, r, arr)
        self._push_up(idx)

def_push_up(self, idx):
"""父节点的 sum = 左子 + 右子"""
        self.sum[idx] = self.sum[idx * 2] + self.sum[idx * 2 + 1]

def_apply_flip(self, idx, l, r):
"""对当前节点整段翻转"""
        length = r - l + 1
        self.sum[idx] = length - self.sum[idx]
        self.lazy[idx] ^= 1# 懒标记取反（0->1，1->0）

def_push_down(self, idx, l, r):
"""把当前节点的懒标记往下传"""
if self.lazy[idx] == 0:
return
        mid = (l + r) // 2
# 左孩子
        self._apply_flip(idx * 2, l, mid)
# 右孩子
        self._apply_flip(idx * 2 + 1, mid + 1, r)
# 清除当前懒标记
        self.lazy[idx] = 0

defupdate_range_flip(self, ql, qr, idx=1, l=1, r=None):
"""把区间 [ql, qr] 性别翻转"""
if r isNone:
            r = self.n
# 不相交
if qr < l or ql > r:
return
# 完全覆盖
if ql <= l and r <= qr:
            self._apply_flip(idx, l, r)
return
# 部分覆盖，往下递归
        self._push_down(idx, l, r)
        mid = (l + r) // 2
        self.update_range_flip(ql, qr, idx * 2, l, mid)
        self.update_range_flip(ql, qr, idx * 2 + 1, mid + 1, r)
        self._push_up(idx)

defquery_range_sum(self, ql, qr, idx=1, l=1, r=None):
"""查询 [ql, qr] 里有多少男生"""
if r isNone:
            r = self.n
# 不相交
if qr < l or ql > r:
return0
# 完全覆盖
if ql <= l and r <= qr:
return self.sum[idx]
# 部分覆盖，下推懒标记
        self._push_down(idx, l, r)
        mid = (l + r) // 2
        left_sum = self.query_range_sum(ql, qr, idx * 2, l, mid)
        right_sum = self.query_range_sum(ql, qr, idx * 2 + 1, mid + 1, r)
return left_sum + right_sum


defmain():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    s = input().strip()  # 形如 "MFMFFM..."
# 把性别转成 0/1：男=1，女=0
    arr = [1if ch == 'M'else0for ch in s]
    seg = SegmentTree(arr)

    output = []
for _ in range(q):
        line = input().split()
        op = line[0]
        l = int(line[1])
        r = int(line[2])
if op == 'C':
# 区间翻转
            seg.update_range_flip(l, r)
elif op == 'Q':
# 查询区间男生数量
            res = seg.query_range_sum(l, r)
            output.append(str(res))
    sys.stdout.write("\n".join(output))


if __name__ == "__main__":
    main()

• 把男女变成 0/1，问题就变成“区间翻转 + 区间求和”
• 翻转这件事，本质是：sum -> len - sum
• 用线段树维护“每一段里有多少个男生”，再用懒标记记住“这段以后要不要翻转”
• 这样每次操作都只是 log n 级别，n, q 上到 10^5 也能稳住

你如果想换玩法，比如把查询变成“问第 x 个同学现在是男是女”，也很好改： 用 Q x x 查一下这个位置的值，1 就男、0 就女，开个 if 输出 'M' 或 'F' 就行了。