Hướng dẫn giải của Điểm chung

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: mrtee

Subtask 1

  • Ta có thể ~for~ từng đoạn ~[a,b]~ để thực hiện tăng giá trị.
  • Độ phức tạp ~O(n*m)~.

Subtask 2

  • Với ~K = N~ tức ta cần tìm các điểm nằm trong mọi đoạn ~[a,b]~.
  • Để làm được điều này, ta sẽ lấy ~l = max(a)~ và ~r = min(b)~ của tất cả các đoạn.
  • Nếu ~l > r~ thì in ra ~0~, ngược lại in ra ~r-l+1~.

Subtask 3

  • Để giải được trọn vẹn bài này, ta sẽ dùng tới kĩ thuật tăng đoạn ~[l,r]~ offline. Khá giống (nhưng đơn giản hơn) so với bài ~3~ của đề thi học sinh giỏi thành phố Hà Nội năm học ~2020 - 2021~.
  • Gọi ~val[i]~ là số những đoạn chứa điểm ~i~. Như vậy với mỗi đoạn ~[a,b]~, ta cần tăng các ~val[a], val[a+1], ..., val[b]~ lên ~1~ đơn vị.
  • Cuối cùng, cần kiểm tra xem có bao nhiêu ~i~ thỏa mãn ~val[i] = k~.
  • Điều này khiến ta liên tưởng tới segment tree, nhưng thực tế lại không cần phức tạp tới vậy.
  • Đầu tiên ta lưu ~val~ bằng một map<int,int>.
  • Với mỗi đoạn ~[a,b]~ ta làm như sau:
    • val[a]++
    • val[b+1]--
  • Thao tác trên có nghĩa là, đầu tiên, ta sẽ đánh dấu tăng đoạn ~[a,\infty]~ lên ~1~ đơn vị, tuy nhiên do chỉ cần tăng từ ~a~ tới ~b~, ta cần giảm đoạn ~[b+1,\infty]~ xuống ~1~ đơn vị.

  • Vậy "đánh dấu tăng đoạn" là gì? Sau khi đọc và tăng xong ~m~ truy vấn, ta sẽ tiến hành thao tác sau:

    • Gọi ~value = 0~ là giá trị của điểm đang xét tới, ~res = 0~ là số điểm thỏa mãn nằm trong đúng ~k~ đoạn.
    • Gọi ~it~ là ~iterator~ đang trỏ tới trong ~map~, ~past~ là ~iterator~ trước đó. Ta sẽ thực hiện phép cộng dồn như sau:
      • value += it->second
      • Nếu ~value = k~, res += it->first - past->first
      • Như vậy, ta đã có thể thực hiện ~m~ phép tăng một cách gián tiếp. Nếu ~value~ đang xét tới của ta ~ = k~, tức là điểm ~it->firsts~ có ~k~ đoạn đi qua nó. Đây là một điểm thỏa mãn, tuy nhiên các điểm trong đoạn [past->first+1,it->first] sẽ có giá trị bằng nhau, nên ta cần cộng thêm số phần tử của đoạn này vào kết quả.

  • Độ phức tạp ~O(n+m*log)~

Code C++

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
struct _data {
    int l,r;
}a[N];

int n,k;
namespace sub1 {
    int f[N];
    int res;
    void solve () {
        for (int i=1; i<=n; i++) {
            int l = a[i].l, r = a[i].r;
            f[l]++; f[r+1]--;
        }
        int mx = 1e3;
        int res = 0;
        for (int i=1; i<=mx; i++) {
            f[i] += f[i-1];
            if (f[i] == k) res++;
        }
        cout << res;
    }
}
#define ii pair<int,int>
namespace sub3 {
    map<int,int> m;
    void solve () {
        for (int i=1; i<=n; i++) {
            int l = a[i].l, r = a[i].r;
            m[l]++; m[r+1]--;
        }
        vector<ii> v;
        for (map<int,int> ::iterator it = m.begin(); it != m.end(); it++) {
            ii dak = *it;
            v.push_back(dak);
        }
        int inf = 1e18;
        for (int i=1; i<v.size(); i++) {
            v[i].second += v[i-1].second;
        }
        int t = v.size();
        int res = 0;
        for (int i=0; i<t-1; i++) {
            if (v[i].second == k) {
                res += v[i+1].first - v[i].first;
            } 
        }
        cout << res;
    }
}
signed main() {
    freopen("DC.INP", "r", stdin);
    freopen("DC.OUT", "w", stdout);
    cin >> n >> k;
    int check = 1;
    for (int i=1; i<=n; i++) {
        int l,r; cin >> l >> r;
        a[i] = {l,r};
        if (r > 1e3) check = 0;
    }
    if (check) sub1::solve();
    else sub3::solve();
}

Code Python

import sys
sys.stdin = open("DC.INP", "r")
sys.stdout = open("DC.OUT", "w")

mp = {}

n, k = 0, 0

def main():
    n, k = map(int, input().split())

    for i in range(n):
        l, r = map(int, input().split())

        if l in mp: mp[l] += 1
        else: mp[l] = 1

        if r + 1 in mp: mp[r + 1] -= 1
        else: mp[r + 1] = -1

    cur, ans = 0, 0
    p = sorted(mp.keys())

    for i in range(len(p) - 1):
        cur += mp[p[i]]
        if cur == k:
            ans += p[i + 1] - p[i]

    print(ans)





if __name__ == '__main__':
    main()