求三个串的最长公共前缀

class Solution {
public:int findMinimumOperations(string s1, string s2, string s3) {int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();int i = 0;for (; i < min({n1, n2, n3}); i++)if (!(s1[i] == s2[i] && s2[i] == s3[i]))break;if (i == 0)return -1;return n1 + n2 + n3 - i * 3;}
};

双指针：一个指针 $i$ 遍历字符串，一个指针 $j$ 指向下一个 $0$ 应该移动到位置，$i$ 指向 $0$ 时更新答案同时 $j+1$

class Solution {
public:long long minimumSteps(string s) {long long res = 0;for (int j = 0, i = 0; i < s.size(); i++)if (s[i] == '0') {res += i - j;j++;}return res;}
};

贪心：从高到低枚举二进制每一位 $i\in [0,n)$，有两种情况：
1）$a$ 和 $b$ 这一位相同，则存在 $x$ 使得 $a\wedge x$ 和 $b\wedge x$ 这一位都为 $1$ ;
2) $a$ 和 $b$ 这一位不同，则$a\wedge x$ 和 $b\wedge x$ 中只有一个数这一位为 $1$ ，若当前 $a\wedge x$ 不考虑这一位的数大于$b\wedge x$ 不考虑这一位的数时，这一位 $1$ 应该给 $b\wedge x$ ，否则给 $a\wedge x$

class Solution {
public:using ll = long long;int maximumXorProduct(long long a, long long b, int n) {ll mod = 1e9 + 7;ll na = a, nb = b;for (ll i = n - 1; i >= 0; i--)if ((na >> i & 1LL) == (nb >> i & 1LL)) {na |= 1LL << i;nb |= 1LL << i;} else {if ((na & (~(1LL << i))) > (nb & (~(1LL << i)))) {nb |= 1LL << i;na &= ~(1LL << i);} else {na |= 1LL << i;nb &= ~(1LL << i);}}return (na % mod * (nb % mod) % mod + mod) % mod;}
};

二分+线段树：对于一个查询 $[a,b]$ $(a\le b)$ ， 有三种情况：
1）$a==b$，答案为 $a$
2）$a\ne b$ ,且 $heights[a]<heights[b]$ ，答案为 $b$
3）$a\ne b$ ,且 $heights[a]\ge heights[b]$，答案为满足 m a x { h e i g h t s [ k ] ∣ k ∈ [ b + 1 , i ] } > h e i g h t s [ a ] max\{heights[k]\;|\; k \in [b+1,i] \}\; >heights[a] max{heights[k]∣k∈[b+1,i]}>heights[a] 的最小的 $i$ ，通过线段树来维护区间最大值，然后通过二分求 $i$

class SegmentTree {
public:typedef long long ll;inline void push_down(ll index) {st[index << 1].lazy = 1;st[index << 1 | 1].lazy = 1;st[index << 1].mark = max(st[index << 1].mark, st[index].mark);st[index << 1 | 1].mark = max(st[index << 1 | 1].mark, st[index].mark);st[index << 1].s = max(st[index << 1].s, st[index].mark);st[index << 1 | 1].s = max(st[index << 1 | 1].s, st[index].mark);st[index].lazy = 0;}inline void push_up(ll index) {st[index].s = max(st[index << 1].s, st[index << 1 | 1].s);}SegmentTree(vector<int> &init_list) {st = vector<SegmentTreeNode>(init_list.size() * 4 + 10);build(init_list, 1, init_list.size());}void build(vector<int> &init_list, ll l, ll r, ll index = 1) {st[index].tl = l;st[index].tr = r;st[index].lazy = 0;st[index].mark = 0;if (l == r) {st[index].s = init_list[l - 1];} else {ll mid = (l + r) >> 1;build(init_list, l, mid, index << 1);build(init_list, mid + 1, r, index << 1 | 1);push_up(index);}}ll query(ll l, ll r, ll index = 1) {if (l <= st[index].tl and st[index].tr <= r) {return st[index].s;} else {if (st[index].lazy)push_down(index);if (r <= st[index << 1].tr)return query(l, r, index << 1);else if (l > st[index << 1].tr)return query(l, r, index << 1 | 1);return max(query(l, r, index << 1), query(l, r, index << 1 | 1));}}private:struct SegmentTreeNode {ll tl;ll tr;ll s;ll mark;int lazy;};vector<SegmentTreeNode> st;
};class Solution {
public:vector<int> leftmostBuildingQueries(vector<int> &heights, vector<vector<int>> &queries) {int n = heights.size();SegmentTree stree(heights);vector<int> res;res.reserve(queries.size());for (auto &qi: queries) {int a = min(qi[0], qi[1]), b = max(qi[0], qi[1]);if (a == b)res.push_back(a);else if (heights[a] < heights[b])res.push_back(b);else {//ha>hbint l = b + 1, r = n;while (l < r) {int mid = (l + r) / 2;if (stree.query(b + 1 + 1, mid + 1) > heights[a])r = mid;elsel = mid + 1;}if (l < n)res.push_back(l);elseres.push_back(-1);}}return res;}
};