Skip to content

fASTER

Reverse Pair

  • naive: \(O(n^2)\)

  • BIT: \(O(nlogn)\)

    思路：创建包含输入范围（过大时离散化）的树状数组，每次添加元素时，加上该元素之后的所有元素出现过的次数（区间求和）。

    #include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int maxn = 50005;
int N;
int arr[maxn], arr2[maxn], bit[maxn];
map<int, int> m;

int lowbit(int x) { return x & (-x); }
void add(int n, int x) {
  for (n; n <= N; n += lowbit(n)) bit[n] += x;
}
int getsum(int n) {
  int res = 0;
  for (n; n > 0; n -= lowbit(n)) res += bit[n];
  return res;
}

int main() {
  while (cin >> N && N) {
      m.clear();
      memset(bit, 0, sizeof(bit));
      for (int i = 0; i < N; i++) cin >> arr[i];
      // discretization
      memcpy(arr2, arr, sizeof(arr));
      sort(arr2, arr2 + N); // [0, N) -> [minv, maxv]
      for (int i = 0; i < N; i++) m[arr2[i]] = i; // [0, N) <- [minv, maxv]
      long long ans = 0;
      for (int i = 0; i < N; i++) {
          add(m[arr[i]] + 1, 1);
          ans += i + 1 - getsum(m[arr[i]] + 1);
      }
      cout << ans << endl;
  }
}

  • Merge sort: \(O(nlogn)\)

    思路：归并过程中遇到左边大于右边，则此处为逆序对。

    #include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int maxn = 50005;
int N;
int arr[maxn], tmp[maxn];
long long ans = 0;

void merge(int l, int r, int *a, int *b) {
  if (r == l) return;
  int m = (l + r) / 2;
  merge(l, m, a, b);
  merge(m + 1, r, a, b);
  int i = l, j = m + 1, k = l;
  while (i <= m && j <= r) {
      if (a[i] <= a[j]) b[k++] = a[i++];
      else {
          ans += m + 1 - i; // update
          b[k++] = a[j++];
      }
  }
  while (i <= m) b[k++] = a[i++];
  while (j <= r) b[k++] = a[j++];
  for (int i = l; i <= r; i++) a[i] = b[i];
}

int main() {
  while (cin >> N && N) {
      for (int i = 0; i < N; i++) cin >> arr[i];
      ans = 0;
      merge(0, N - 1, arr, tmp);
      cout << ans << endl;
  }
}
Variants

  • (Leetcode 493) Count (i, j) where i<j and arr[i] > 2*arr[j].

    • mergesort

      在排序之外独立的操作计数。此外，尽管题目说了数据是int内，由于比较时需要*2，仍有溢出风险，所以用ll。

      class Solution {
public:
    long long ans = 0;
    // T(n) = 2T(n/2) + O(2n)
    void mergesort(long long* a, long long* b, int l, int r){
        if(l==r) return;
        int m = (l+r)/2;
        mergesort(a, b, l, m);
        mergesort(a, b, m+1, r);
        // count only, O(n)
        int i=l, j=m+1, k=l;
        while(i<=m && j<=r){  
            if(a[i] > 2*a[j]){
                ans += m - i + 1;
                j++;
            }
            else i++;
        }
        // sort, O(n)
        i=l, j=m+1, k=l;
        while(i<=m && j<=r){
            if(a[i] > a[j]) b[k++] = a[j++];
            else b[k++] = a[i++]; 
        }
        while(i<=m) b[k++] = a[i++];
        while(j<=r) b[k++] = a[j++];
        for(int i=l; i<=r; i++) a[i] = b[i];
    }
    int reversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        int N = nums.size();
        ans = 0;
        long long* b = new long long[N];
        long long* a = new long long[N];
        for(int i=0; i<N; i++) a[i]=nums[i];
        mergesort(a, b, 0, N-1);
        return ans;
    }
};

    • BIT

      离散化仍然是必要的，而正确性需要在原来的数组中搜索两倍关系，而不是在离散后的数组中搜索。

      Lower Bound各种边界条件太难处理好了。

      class Solution{
public:
    const static int maxn = 50005;
    long long bit[maxn];
    int N;
    int lowbit(int x){return x&(-x);}
    void add(int i, int x){
        for(i;i>0;i-=lowbit(i)) bit[i]+=x;
    }
    int getsum(int i){
        int sum = 0;
        for(i;i<=N;i+=lowbit(i)) sum += bit[i];
        return sum;
    }
    void init(int n){
        for(int i=0; i<=n; i++) bit[i] = 0;
    }

    int reversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        N = nums.size();
        init(N);
        vector<int> pos(nums);
        sort(pos.begin(), pos.end());

        int ans = 0;

        for(int i=0; i<N; i++){
            int p = lower_bound(pos.begin(), pos.end(), nums[i]) - pos.begin();
            int p2 = lower_bound(pos.begin(), pos.end(), 2LL*nums[i]+1) - pos.begin();
            ans += getsum(p2+1);
            add(p+1, 1);
        }

        return ans;
    }
};

Interval Scheduling Maximization Problem

given a set of intervals, find the maximum numbers of intervals that are non-overlapping.

  • Greedy: \(O(nlgn)\) (and is enough)

    // here [0,1] and [1,1] are considered as overlapped.
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int maxn = 10005;
int N;

struct node {
  int s, e;
  bool operator< (const node& b) const { return e < b.e; }
} act[maxn];


int main() {
  cin >> N;
    // input
  for (int i = 0; i < N; i++) 
      cin >> act[i].s >> act[i].e;
    // sort, smaller ending time first, and starting time is useless.
  sort(act, act + N);
  int ans = 0, end = -1;
    // remove the interval with smallest ending time 
    // and all overlapped interval with it, ans++
  for (int i = 0; i < N; i++) {
      if (act[i].s > end) {
          ans++;
          end = act[i].e;
      }
      else continue;
  }
  cout << ans << endl;
}

Variants

  • GISDP: Grouped Interval Scheduling decision problem

    Every two intervals shouldn't be in the same group, just decide whether such a compatible set exists.

    • if all groups contain at most 2 intervals. Polynomial.
    • more than 2 intervals: NP-hard.

Monotonic Queue

单调队列，push元素时先把队尾小于x的元素pop掉，保证队首始终为最大元素。适合于滑动区间取最值问题。

\(O(1)\) for pop() and getmax() ! ( but in worst cases \(O( n)\) for push(). )

  • Sliding Window Maximum (leetcode 239)

    Very clever Linear solution & implementation !

    class Solution {
public:
    struct monoque{
        deque<int> que;
        // keep que monotonically decreasing
        void push(int n){
            while(!que.empty() && que.back()<n) que.pop_back();   
            que.push_back(n);
        }
        int getmax(){ return que.front(); }
        // n is the element ought to be deleted, this makes difference!
        void pop(int n){ 
            if(que.front() == n) que.pop_front(); 
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int N = nums.size();
        vector<int> ans;
        monoque que;
        for(int i=0; i<N; i++){
            que.push(nums[i]);
            if(i>=k-1){
                ans.push_back(que.getmax());
                que.pop(nums[i-k+1]);
            }
        }
        return ans;
    }
};

Maximum & Minimum Integer Sequence

Greedy. But the comparator is hard to come about.

import functools

n = int(input())
nums = input().split()

# python sorted cmp
def cmp(a, b):
    a, b = int(a+b), int(b+a)
    if a==b:
        return 0 # eq
    elif a<b:
        return -1 # a < b
    else:
        return 1 # a > b

# functools.cmp_to_key
nums = sorted(nums, key=functools.cmp_to_key(cmp))
print(''.join(reversed(nums)),''.join(nums))

// leetcode 179 
class Solution {
public:
    static bool cmp(const string& a, const string& b){
        return stoll(a+b) > stoll(b+a);
    }
    string largestNumber(vector<int>& nums) {
        vector<string> snums;
        for(int i=0; i<nums.size(); i++)
            snums.push_back(to_string(nums[i]));
        sort(snums.begin(), snums.end(), cmp);
        string ans;
        for(int i=0; i<nums.size(); i++) ans+=snums[i];
        while(ans[0] == '0' && ans.size()>1) ans = ans.substr(1);
        return ans;
    }
};

Palindrome

Manacher is the golden key.

class Solution {
public:
    int manacher(string s){
        // init
        string S = "@#";
        for(int i=0; i<s.size(); i++) S += s[i] + "#";
        S += "$";
        // calc
        int center = 0, right = 0;
        int* z = new int[S.size()];
        for(int i=1; i<S.size(); i++){
            if(i<right) z[i] = min(right-i, z[2*center-i]);
            while(S[i+z[i]+1] == S[i-z[i]-1]) z[i]++;
            if(i+z[i]>right){
                center = i;
                right = i + z[i];
            }
        }
        // find longest 
        int mx = 0;
        for(int i=1; i<S.size(); i++)
            mx = max(mx, (z[i]+1)/2);
        return mx;
    }
};

Cumulative Sum

子序列(Subarray, continuous)求和问题，枚举子序列O(n^2)，每个子序列的计算O(n)，Naive算法O(n^3）。

Cumsum预处理O(n)，枚举子序列O(n^2)，每个子序列的计算O(1)，总共O(n^2)。

  • leetcode 560 Subarray Sum Equals K

    由于要求特殊，还可以散列计数优化到O(n)。

    class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        map<int, int> m;
        m[0] = 1;
        int sum = 0, ans = 0;
        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
            if(m.count(sum-k)) ans+= m[sum-k];
            if(m.count(sum)) m[sum]++;
            else m[sum] = 1;
        }
        return ans;
    }
};

O(1) Space Cults

  • find the unique number

    [1,2,1,3,3] -> 2

    XOR solution.

  • find the duplicate number

    [1,3,4,2,2] -> 2 Amazingly a Floyd Cycle Detection Solution:

    class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow=0, fast=0;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);

        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

Range Maximum

  • Segment tree

    区间更新O(lgn)，预处理O(nlgn)，区间查询O(lgn)

  • BIT

    单点更新O(lg^2n)，预处理O(nlg^2n)，区间查询O(lg^2n)

  • RMQ

    不支持更新，预处理O(nlgn)，区间查询O(1)

Longest Valid Parenthesis substring 32

DP is complicated, use stack and think reversely.

每两个无法匹配的字符之间的子串一定是正确匹配的，所以用栈记录失配字符，减一减即可！

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        for(int i=0; i<s.size(); i++){
            if(s[i] == '(') stk.push(i);
            else{
                if(!stk.empty() && s[stk.top()]=='(') stk.pop();
                else stk.push(i);
            }
        }
        if(stk.empty()) return s.size();
        else{
            int end = s.size(), start = 0, ans = 0;
            while(!stk.empty()){
                start = stk.top(); stk.pop();
                ans = max(ans, end-start-1);
                end = start;
            }
            ans = max(ans, end);
            return ans;
        }
    }
};
排序的代价

求通过交换任意两个数字（代价为两个数字之和）使得数组有序所要花费的最小代价。

思路：索引排序，每个交换环的最小代价为：环中元素之和+环中最小元素*（环中元素数目-2），或者把环中最小元素暂时与整体最小元素互换再求代价。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1000005;
const int inf = 0x3f3f3f3f;
int N;

int vis[maxn];

struct node {
    int val, idx;
    bool operator < (const node& b) const {
        return val < b.val;
    }
} nodes[maxn];

int ans, mn;

int solveLoop(int x) {
    int lmn = inf, cnt = 0, res = 0;
    while (!vis[x]) {
        vis[x] = 1;
        lmn = min(lmn, nodes[x].val);
        cnt++;
        res += nodes[x].val;
        x = nodes[x].idx;
    }
    int val1 = res + lmn * (cnt - 2);
    int val2 = res + mn * cnt + lmn + mn; // important
    return min(val1, val2);
}

int main() {
    while (cin >> N && N) {
        mn = inf;
        for (int i = 0; i < N; i++) {
            cin >> nodes[i].val;
            nodes[i].idx = i;
            mn = min(mn, nodes[i].val);
        }
        sort(nodes, nodes + N);
        memset(vis, 0, sizeof(vis));
        ans = 0;
        for (int i = 0; i < N; i++) if (!vis[i]) ans += solveLoop(i);
        cout << ans << endl;
    }
}