electionposter

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

#define OJ                            \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);
#define FIO                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

vector<int> lazy;
int n;

void shift(int id)
{
    if (lazy[id])
    {
        lazy[2 * id] = lazy[2 * id + 1] = lazy[id];
    }

    lazy[id] = 0;
}

void update(int x, int y, int color, int id = 1, int l = 0, int r = n)
{
    if (x >= r || y <= l)
    {
        return;
    }

    if (x <= l && r <= y)
    {
        lazy[id] = color;
        return;
    }

    int mid = (l + r) / 2;
    shift(id);
    update(x, y, color, 2 * id, l, mid);
    update(x, y, color, 2 * id + 1, mid, r);
}

set<int> ans;
void cnt(int id = 1, int l = 0, int r = n)
{
    if (lazy[id])
    {
        ans.insert(lazy[id]);
        return;
    }

    if (r == l+1)
    {
        return;
    }

    int mid = (l + r) / 2;
    cnt(2 * id, l, mid);
    cnt(2 * id + 1, mid, r);
}

int main()
{
    OJ;
    FIO;
    int t;
    cin >> t;
    while (t--)
    {
        ans.clear();
        int x;
        cin >> x;
        set<int> pts;
        vector<pair<int, int>> ranges(x);
        for (int i = 0; i < x; i++)
        {
            int l, r;
            cin >> l >> r;
            pts.insert(l);
            pts.insert(r);
            ranges[i] = make_pair(l, r);
        }

        // range compression
        int k = 0;
        map<int, int> m;
        for (auto p : pts)
        {
            m[p] = k++;
        }

        n = k;
        for (int i = 0; i < x; i++)
        {
            ranges[i].first = m[ranges[i].first];
            ranges[i].second = m[ranges[i].second];
        }

        lazy.assign(4 * (k + 1), 0);

        for (int i = 0; i < x; i++)
        {
            update(ranges[i].first, ranges[i].second + 1, i + 1);
        }

        cnt();
        cout << ans.size() << "\n";
    }
    return 0;
}