Leetcode

void adjust(vector<int>& a, int len, int i){
  int l = i * 2 + 1, r = l + 1, maxId = i;
  if (l < len && a[maxId] < a[l]) maxId = l;
  if (r < len && a[maxId] < a[r]) maxId = r;
  if (maxId != i) {
    swap(a[i], a[maxId]);
    adjust(a, len, maxId);
  }
}
void hsort(vector<int>& a){
  for(int i = a.size() / 2 - 1; i >= 0; --i){
    adjust(a, a.size(), i);
  }
  for(int i = a.size() - 1; i > 0; --i){
    swap(a[0], a[i]);
    adjust(a, i, 0);
  }
}

int ans{0};  // 逆序对
vector<int> tmp;
vector<int> sortArray(vector<int>& nums) {
  tmp.assign(nums.size(), 0);
  mergesort(nums, 0, nums.size() - 1);
  return nums;
}
void mergesort(vector<int>& nums, int l, int r){
  if (l < r) {
    int m = l + r >> 1;
    mergesort(nums, l, m);
    mergesort(nums, m + 1, r);
    merge(nums, l, m, r);
  }
}
void merge(vector<int>& nums, int l, int m, int r){
  int i = l, j = m + 1, k = l;
  while (i <= m && j <= r) {
    if (nums[i] <= nums[j]) {
      // ans += j - m - 1;
      tmp[k++] = nums[i++];
    } else {
      tmp[k++] = nums[j++];
    }
  }
  while (i <= m) {
    // ans += j - m - 1;
    tmp[k++] = nums[i++];
  }
  while (j <= r) tmp[k++] = nums[j++];
  for (int i = l; i <= r; ++i) nums[i] = tmp[i];
}

ListNode *midLeft(ListNode* p){
  ListNode *f = p, *s = p;
  while(f->next && f->next->next){
    s = s->next;
    f = f->next->next;
  }
  return s;
}
ListNode *reverse(ListNode* p){
  ListNode *dummy=new ListNode(),*q;
  while(p){
    q=p->next;
    p->next=dummy->next;
    dummy->next=p;
    p=q;
  }
  return dummy->next;
}

string addStr(string num1, string num2) {
  string ans;
  int add = 0,i = num1.size() - 1, j = num2.size() - 1;
  while(add || i >= 0 || j >= 0){
    int x= i >= 0 ? num1[i] - '0': 0;
    int y= j >= 0 ? num2[j] - '0': 0;
    int result = x + y + add;
    ans += char('0' + result % 10);
    add = result / 10;
    i--; j--;
  }
  reverse(ans.begin(), ans.end());
  return ans;
}

string ans;
string multiply(string num1, string num2) {
  if (num1 == "0" || num2 == "0") return "0";
  int m = num1.size(), n = num2.size();
  for(int i = n - 1; i >= 0; i--){
    string tmp(n - 1 - i, '0');
    int add = 0, y = num2[i] - '0';
    for(int j = m - 1; j >= 0 || add; --j){
      int x = j < 0 ? 0 : num1[j] - '0';
      int multi = x * y + add;
      tmp += char('0' + multi % 10);
      add = multi / 10;
    }
    reverse(tmp.begin(), tmp.end());
    ans = addStr(tmp, ans);
  }
  return ans;
}

vector<string> ret;
void split(string s, char del){
  stringstream ss(s);
  string tmp;
  while(getline(ss, tmp, del)){
    if(tmp.size()) ret.push_back(tmp);
  }
}

TreeNode *buildTree(vector<int>& vec) {
  vector<TreeNode*> tree(vec.size(), nullptr);
  for (int i = 0; i < vec.size(); ++i) {
    if (vec[i] != -1) tree[i] = new TreeNode(vec[i]);
  }
  for (int i = 0; i < vec.size() / 2; ++i) {
    if (vec[i] != -1) {
      tree[i]->left = tree[i * 2 + 1];
      tree[i]->right = tree[i * 2 + 2];
    }
  }
  return tree[0];
}
int main(){
	vector<int> v = {4,1,6,0,2,5,7,-1,-1,-1,3,-1,-1};
	TreeNode* root = Build(v);
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  if (!root || root == p || root == q) return root;
  auto l = lowestCommonAncestor(root->left, p, q);
  auto r = lowestCommonAncestor(root->right, p, q);
  if (!l) return r;
  if (!r) return l;
  return root;
}

int m, n, ans;
vector<int> d{-1, 0, 1, 0, -1};
vector<vector<int>> dp;
int longestIncreasingPath(vector<vector<int>>& matrix) {
  m = matrix.size(), n = matrix[0].size();
  dp.assign(m, vector<int>(n, -1));  // cache, 仅增加了注释的三行代码
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      ans = max(ans, fun(matrix, i, j, INT_MAX + 1l));
    }
  }
  return ans;
}
int fun(vector<vector<int>>& matrix, int i, int j, long value) {
  if (i < 0 || j < 0 || i == m || j == n || (long)matrix[i][j] >= value) {
    return 0;
  }
  if (dp[i][j] != -1) return dp[i][j];  // load
  int len = 0;
  for (int k = 0; k < 4; ++k) {
    len = max(len, fun(matrix, i + d[k], j + d[k + 1], matrix[i][j]));
  }
  dp[i][j] = len + 1;  // save
  return len + 1;
}

// 返回字典序最小的序列
vector<int> lengthOfLIS(vector<int>& nums) {
  int n = nums.size();
  vector<int> d;       // d[i] 维护当前长度为 len 的 LIS
  vector<int> pos(n);  // pos[i]: nums[i] 在 d 中的下标
  d.push_back(nums[0]);
  for (int i = 1; i < n; ++i) {
    if (nums[i] > d.back()) {
      d.push_back(nums[i]);
      pos[i] = d.size();
    } else {
      auto it = lower_bound(d.begin(), d.end(), nums[i]);
      *it = nums[i];
      pos[i] = it - d.begin() + 1;
    }
  }
	int len = d.size();  // 长度
  vector<int> lis;
  for (int i = n - 1; i >= 0 && len; --i) {
    if (pos[i] == len) {
      lis.push_back(nums[i]);
      len--;
    }
  }
  reverse(lis.begin(), lis.end());
  return lis;
}

int longestCommonSubsequence1(string text1, string text2) {
  int m = text1.size(), n = text2.size();
  vector<int> dp(n + 1);
  for (int i = 1; i <= m; ++i) {
    int leftup = dp[0];
    for (int j = 1; j <= n; ++j) {
      int tmp = dp[j];
      if (text1[i - 1] == text2[j - 1]) dp[j] = leftup + 1;
      else dp[j] = max(dp[j], dp[j - 1]);
      leftup = tmp;
    }
  }
  return dp[n];
}

bool wordBreak(string s, vector<string>& wordDict) {
  int n = s.size(), max_len = 0;
  vector<int> dp(n);
  unordered_set<string> st;
  for (auto& w : wordDict) {
    max_len = max(max_len, (int)w.size());
    st.insert(w);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = max(0, i - max_len + 1); j <= i; ++j) {
      string cur = s.substr(j, i - j + 1);
      if (!st.count(cur)) continue;
      if (j == 0 || dp[j - 1] > 0) {
        dp[i] = 1;
        break;
      }
    }
  }
  return dp.back();
}

int knapsack(vector<int> weights, vector<int> values, int space) {
  vector<int> dp(space + 1, 0);
  for (int i = 1; i <= N; ++i) {
    int w = weights[i - 1], v = values[i - 1];
    for (int j = space; j >= w; --j)
      dp[j] = max(dp[j], dp[j - w] + v);
  }
  return dp[space];
}

pair<int, int> dfs(TreeNode* t) {
  if (!t) return {0, 0};
  pair<int, int> l = dfs(t->left), r = dfs(t->right);
  int stole = t->val + l.first + r.first;
  int unstole = max(l.first, l.second) + max(r.first, r.second);
  return {unstole, stole};
}
int rob(TreeNode* root) {
  auto pair = dfs(root);
  return max(pair.first, pair.second);
}

// 返回首个≥target的元素下标
int Bsearch(vector<int>& nums,int target){
    int l = 0,r = nums.size() - 1;
    while(l < r){
        int m = l + r >> 1;
        if(nums[m] < target) l = m + 1;
        else r = m;
    }
    return nums[l] == target ? l : -1;
}

// 升序 从左向右找
while(l < r) {
    int mid = l + r >> 1;
    if(flag) l = mid + 1;
    else r = m;
}
// 升序 从右向左找
while(l < r) {
    int mid = l + r + 1 >> 1; 
    if(flag) r = mid - 1;
    else l = mid;
}

while(l <= r){
    int mid = l + r >> 1;
    if(flag) ans = mid, l = mid + 1;  // 需记录答案
    else r = mid - 1;
}

int search(vector<int>& arr, int target) {
  int n = arr.size(), l = 0, r = n - 1;
  while (l <= r) {
    int m = l + r >> 1;
    if (arr[m] == target) {  // 重复选首个下标
      while (m && arr[m - 1] == arr[m]) m--;
      return m;
    }
    if (arr[l] < arr[m]) {  // 左侧有序
      if (arr[l] <= target && arr[m] > target) 
        r = m - 1;
      else l = m + 1;
    } else if (arr[l] > arr[m]) {  // 右侧有序
      if (arr[m] < target && arr[r] >= target)
        l = m + 1;
      else r = m - 1;
    } else {
      l++;
    }
  }
  return -1;
}

int findMin(vector<int>& nums) {
  int l = 0, r = nums.size() - 1;
  while (l < r) {
    if (nums[l] < nums[r]) break;  // 特判 case: [1,2,3 ...]
    int m = l + r >> 1;
    if (nums[m] < nums[l]) r = m;
    else if (nums[m] > nums[l]) l = m + 1;
    else l++;
  }
  return nums[l];
}

int FindK(vector<int>& a, int k){
  int l = 0, r = a.size() - 1;
  while(l <= r){
    int pivot = Part(a, l, r);
    if (pivot == k) return a[k];
    else if (pivot > k) r = pivot - 1;
    else l = pivot + 1;
  }
  return -1;
}
int Part(vector<int>& a, int l, int r){
  int pivot = a[l];
  while(l < r ) {
    while(l < r && a[r] >= pivot) r--;
    a[l] = a[r];
    while(l < r && a[l] <= pivot) l++;
    a[r] = a[l];
  }
  a[l] = pivot;
  return l;
}

double quickMul(double x, int N){
  double ans = 1.0;
  while(N) {
    if(N & 1) ans *= x;
    x *= x;
    N >>= 1;
  }
  return ans;
}

int lastRemaining(int n, int m) {
  int ans=0;
  for(int i = 2;i <= n; ++i)
      ans = (ans + m) % i;
  return ans;
}

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 10);
cout << dis(gen) << endl;

int n = 1005; // n根据题目中节点数量而定
vector<int> father = vector<int>(n);

void init() {
  for (int i = 0; i < n; ++i) {
    father[i] = i;
  }
}
// 并查集里寻根的过程
int find(int u) {
  return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
  u = find(u);
  v = find(v);
  return u == v;
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
  u = find(u);
  v = find(v);
  if (u == v) return;
  father[v] = u;
}

int nthSuperUglyNumber(int n, vector<int>& primes) {
  vector<int> next(primes.size(), 0), dp{1};
  while (dp.size() < n) {
    int pid = -1, ugly = INT_MAX;
    for (int i = 0; i < primes.size(); ++i) {
      long tmp = (long)primes[i] * dp[next[i]];
      if (tmp < ugly) {
        ugly = tmp;
        pid = i;
      }
    }
    next[pid]++;
    if (dp.back() < ugly) {  // 去重
      dp.push_back(ugly);
    }
  }
  return dp.back();
}

// 时间复杂度高，可能乘法溢出
int nthSuperUglyNumber(int n, vector<int>& primes) {
  priority_queue <double, vector<double>, greater<double>> q;
  unordered_set<int> s;
  s.insert(1);  // 去重
  int answer = 1;
  for (int i = 1; i < n; ++i){
    for (int j: primes) {
      int multi = answer * j;
      if(!s.count(multi)){
        q.push(multi);
        s.insert(multi);
      }
    }
    answer = q.top();
    q.pop();
  }
  return answer;
}