const volatile int i = 10;

// 没有问题
// volatile: 存在寄存器里面的值，表示会被意想不到的改变
// const: 表明程序不要去试图修改它。表示运行时候所在作用域内不能进行修改

// 190. Reverse Bits
uint32_t reverseBits(uint32_t n) {
  uint32_t res = 0;
  int power = 31;
  while (n > 0) {
    res |= (n & 1) << power;
    --power;
    n = n >> 1;
  }
  return res;
}

uint32_t reverseBits(uint32_t n) {
  n = (n >> 16) | (n << 16);
  n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
  n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
  n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
  n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
  return n;
}

// Minimum Spanning Tree: 最小生成树
// 村庄供水
// 1584. Min Cost to Connect All Points
class Solution {
 public:
  int FindSet(const int num, vector<int>& record) {
    if (num != record[num]) {
      record[num] = FindSet(record[num], record);
    }
    return record[num];
  }
  
  void Union(const int a1, const int a2, vector<int>& rank,
             vector<int>& record) {
    if (rank[a1] > rank[a2]) {
      record[a2] = a1;
    } else {
      record[a1] = a2;
      if (rank[a1] == rank[a2]) {
        ++rank[a2];
      }
    }
  }
  
  int minCostConnectPoints(vector<vector<int>>& points) {
    vector<vector<int>> edges;
    vector<int> record(points.size()+1, 0);
    for (int i = 0; i < points.size(); ++i) record[i] = i;
    
    vector<int> rank(points.size()+1, 0);
    for (int i = 0; i < points.size(); ++i) {
      for (int j = i + 1; j < points.size(); ++j) {
        const int dis = abs(points[i][0] - points[j][0]) +
                        abs(points[i][1] - points[j][1]);
        edges.push_back({i, j, dis});
      }
    }
    sort(begin(edges), end(edges), [](const vector<int>& v1,
      const vector<int>& v2) {
      return v1[2] < v2[2];
    });
    int num_components = points.size();
    int dis_sum = 0;
    for (const auto& edge : edges) {
      const auto a1 = FindSet(edge[0], record);
      const auto a2 = FindSet(edge[1], record);
      if (a1 != a2) {
        Union(a1, a2, rank, record);
        --num_components;
        dis_sum += edge[2];
      }
      if (num_components == 1) break;
    }
    return dis_sum;
  }
};

// 1135. Connecting Cities With Minimum Cost
class Solution {
 public:
  int FindSet(const int num, vector<int>& record) {
    if (num != record[num]) {
      record[num] = FindSet(record[num], record);
    }
    return record[num];
  } 
  
  void Union(const int a1, const int a2, vector<int>& rank, 
             vector<int>& record) {
    if (rank[a1] > rank[a2]) {
      record[a2] = a1;
    } else {
      record[a1] = a2;
      if (rank[a1] == rank[a2]) {
        ++rank[a2];
      }
    }
  }
  
  int minimumCost(int N, vector<vector<int>>& connections) {
    sort(begin(connections), end(connections), 
        [](const vector<int>& v1, const vector<int>& v2){
      return v1[2] < v2[2];
    });  
    int num_connected = N;
    int sum_dis = 0;
    vector<int> record(N + 1, 0);
    vector<int> rank(N + 1, 0);
    for (int i = 0; i < N; ++i) record[i] = i;
    for (const auto& connection : connections) {
      const auto a1 = FindSet(connection[0], record);
      const auto a2 = FindSet(connection[1], record);
      if (a1 != a2) {
        Union(a1, a2, rank, record);
        sum_dis += connection[2];
        --num_connected;
      }
      if (num_connected == 1) break;
    }
    return num_connected == 1?sum_dis:-1;
  }
};

// 1168. Optimize Water Distribution in a Village
class Solution {
 private:
  class UnionFind {
   public:
    UnionFind(const int n) {
      rank_ = vector<int>(n, 0);
      num_component_ = n;
      for (int i = 0; i < n; ++i) {
        record_.push_back(i);
      }
    }
    
    int Find(const int num) {
      if (record_[num] != num) {
        record_[num] = Find(record_[num]);
      }
      return record_[num];
    }
    
    void Union(const int a, const int b, const int cost) {
      const auto p_a = Find(a);
      const auto p_b = Find(b);
      if (p_a == p_b) return;
      if (rank_[p_a] > rank_[p_b]) {
        record_[p_b] = p_a;
      } else {
        record_[p_a] = p_b;
        if (rank_[p_a] == rank_[p_b]) {
          ++rank_[p_b];
        }
      }
      cost_ += cost;
      --num_component_;
    }
    
    vector<int> rank_;
    vector<int> record_;
    int cost_ = 0;
    int num_component_ = 0;
  };
 public:
  int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
    for (int i = 0; i < wells.size(); ++i) {
      pipes.push_back({0, i+1, wells[i]});
    }      
    sort(pipes.begin(), pipes.end(), [](const vector<int>& p1, const vector<int>& p2) {
      return p1[2] < p2[2];
    });
    UnionFind uf(n+1);
    for (const auto& pipe : pipes) {
      uf.Union(pipe[0], pipe[1], pipe[2]);
      if (uf.num_component_ == 1) break;
    }
    return uf.cost_;
  }
};

// Knapsack: 背包问题
// 播放广告: 利润最大化；还可以加入混合背包
// 518. Coin Change 2

// map：map快速操作
// 355. Design Twitter
class Twitter {
 public:
  class Compare {
   public:
    bool operator()(const pair<int, int>&p1, const pair<int, int>& p2) {
      return p1.second > p2.second;
    }
  };
  
  unordered_map<int, unordered_set<int>> follower_ids_;
  unordered_map<int, vector<pair<int, int>>> posts_;
  int count_ = 0;
  
  /** Initialize your data structure here. */
  Twitter() {}
    
  /** Compose a new tweet. */
  void postTweet(int userId, int tweetId) {
    posts_[userId].push_back({tweetId, count_++});
  }
    
  /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
  vector<int> getNewsFeed(int userId) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    int cnt = 0;
    for (auto it = posts_[userId].crbegin(); it != posts_[userId].crend(); ++it) {
      if (pq.size() < 10) {
        pq.push(*it);
      } else {
        if (it->second < pq.top().second) break;
        pq.push(*it);
      }
    }
    
    for (auto id = follower_ids_[userId].begin(); id != follower_ids_[userId].end(); ++id) {
      for (auto it = posts_[*id].crbegin(); it != posts_[*id].crend(); ++it) {
        if (pq.size() < 10) {
          pq.push(*it);
        } else {
          if (it->second < pq.top().second) break;
          pq.pop();
          pq.push(*it);
        }
      }
    }
    vector<int> ans;
    while (!pq.empty()) {
      ans.push_back(pq.top().first);
      pq.pop();
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
    
  /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
  void follow(int followerId, int followeeId) {
    if (followerId != followeeId) {
      follower_ids_[followerId].insert(followeeId);
    }
  }
    
  /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
  void unfollow(int followerId, int followeeId) {
    follower_ids_[followerId].erase(followeeId);    
  }
};

// Topological sort: 拓扑排序
// For multiple start points with flooding with priority queue.
vector<int> FloodingWithPriority() const {
  store the existing node into pq.
  while (!pq.empty()) {
    fetch & pop
    go the 4 or 8 connected  
  }  
  return result.
}

// Travel different ways
int TravelWays(const int N) {
  if (N < 2) return 0;
  int num = 0;
  vector<int> stations(N+1, 0);
  stations[1] = 1;
  for (int i = 2; i <= N; ++i) {
    for (int j = 1; j < i; ++j) {
      stations[i] += stations[j];
    }
  }
  
  return stations[N];
}
// easier way, only 2^(N-2), as we could select this station or not.

// Link parse with DFS & memorial search.