<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

339. Segments
Time limit per test: 2.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Consider a real axis and segments on it. You are to write a program that processes queries of two kinds.

Query '+ L R' adds a segment from point L to point R. You program should print the number of segments that are (non-strictly) inside the new one.

Query '- L R' removes one segment from point L to point R. If there is no such segment, ignore this query.

You may assume that no more than 1000 segments will present on the axis simultaneously.

Input
Each line of the input file contains one query. Query can be in the form '- L R' or '+ L R', where L and R are integers (-109 ≤ L < R ≤ 109). There will be no more than 250 · 103 queries.

Output
Print to the output one line for each '+ L R' query, containing the number of segments inside the added segment.

Example(s)
sample input
sample output
+ 1 2
+ 1 2
+ 0 3
- 1 2
+ 1 2
0
1
2
1

<|response|>
## 1) Abridged problem statement (concise)

Maintain a multiset of segments \([L,R]\) on the real line under queries until EOF:

- `+ L R`: add segment \([L,R]\), and **print** how many currently active segments \([l,r]\) satisfy \(L \le l\) and \(r \le R\) (i.e., are inside the new segment, endpoints allowed).
- `- L R`: remove **one** occurrence of \([L,R]\) if it exists; otherwise ignore.

Constraints: up to 250,000 queries, coordinates \([-10^9,10^9]\), and **at most 1000 segments are active at any time**.

---

## 2) Key observations

1. **Active set is small (≤ 1000).**
   Even with 250k queries, the expensive work per query can be linear in the number of active segments and still pass.

2. For a `+ L R` query, a segment \([l,r]\) is inside iff:
   \[
   l \ge L \;\;\text{and}\;\; r \le R
   \]
   So we can just scan all active segments and count.

3. Deletions are "remove one copy". Duplicates may exist, so we need multiset behavior.

4. Efficient deletion from a vector: **swap-with-last + pop**
   - Find one matching segment index `i`
   - Replace it with the last element
   - `pop_back()`
   This avoids shifting and keeps removal O(1) after the O(A) search.

5. Coordinate compression is optional for correctness, but the reference code applies it: it keeps endpoints in 32-bit lanes (useful for SIMD) and order is preserved, so containment comparisons stay correct.

---

## 3) Full solution approach

### Data structure
Keep currently active segments in two parallel vectors:
- `Ls[k]` = left endpoint of segment k
- `Rs[k]` = right endpoint of segment k

Active size \(A \le 1000\).

### Reading and compressing
Read all queries until EOF. While reading, a `multiset` of segments tracks what currently exists, so invalid `- L R` deletions (segment not present) are dropped immediately. Then all endpoints are gathered, sorted, uniqued, and each query's `(L, R)` is replaced by 1-indexed ranks.

### Processing queries
Process the recorded queries sequentially:

- **On `+ L R`:**
  1. Count `cnt = number of k such that Ls[k] >= L and Rs[k] <= R`
  2. Print `cnt`
  3. Insert the new segment by `Ls.push_back(L); Rs.push_back(R)`

- **On `- L R`:**
  1. Find any index `i` with `Ls[i] == L && Rs[i] == R`
  2. If found: overwrite with the last element and `pop_back` both arrays
  3. If not found (already filtered out during reading): ignore

### SIMD acceleration
Both the count and the deletion search scan 8 segments at a time with AVX2. For the count, since AVX2 only offers a signed `>` comparison, we use `l >= L  <=>  l > L-1` and `r <= R  <=>  R+1 > r`, AND the two lane masks, and add `popcount(mask) >> 2` (each matching int32 lane sets 4 mask bytes).

### Complexity
- Each `+`: \(O(A)\) comparisons, \(A \le 1000\) (vectorized)
- Each `-`: \(O(A)\) search, O(1) removal
- Worst-case: \(250000 \times 1000 = 2.5 \times 10^8\) simple checks, acceptable in optimized C++.

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>
#include <immintrin.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

vector<tuple<bool, int, int>> queries;

void read() {
    char type;
    int l, r;
    multiset<pair<int, int>> segments;
    vector<int> all_coords;
    while(cin >> type >> l >> r) {
        if(type == '+') {
            segments.insert({l, r});
            queries.push_back({true, l, r});
        } else {
            auto it = segments.find({l, r});
            if(it == segments.end()) {
                continue;
            }
            segments.erase(it);
            queries.push_back({false, l, r});
        }

        all_coords.push_back(l);
        all_coords.push_back(r);
    }

    sort(all_coords.begin(), all_coords.end());
    all_coords.erase(
        unique(all_coords.begin(), all_coords.end()), all_coords.end()
    );

    for(auto& [add, l, r]: queries) {
        l = (int)(lower_bound(all_coords.begin(), all_coords.end(), l) -
                  all_coords.begin() + 1);
        r = (int)(lower_bound(all_coords.begin(), all_coords.end(), r) -
                  all_coords.begin() + 1);
    }
}

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

class ActiveSegments {
  private:
    vector<int> Ls;
    vector<int> Rs;

  public:
    ActiveSegments() {
        Ls.reserve(1024);
        Rs.reserve(1024);
    }

    void add(int l, int r) {
        Ls.push_back(l);
        Rs.push_back(r);
    }

    bool remove(int ql, int qr) {
        size_t n = Ls.size();
        size_t i = 0;

        __m256i qlv = _mm256_set1_epi32(ql);
        __m256i qrv = _mm256_set1_epi32(qr);

        for(; i + 7 < n; i += 8) {
            __m256i lv = _mm256_loadu_si256((const __m256i*)(Ls.data() + i));
            __m256i rv = _mm256_loadu_si256((const __m256i*)(Rs.data() + i));

            __m256i matchL = _mm256_cmpeq_epi32(lv, qlv);
            __m256i matchR = _mm256_cmpeq_epi32(rv, qrv);
            __m256i both = _mm256_and_si256(matchL, matchR);

            int mask = _mm256_movemask_epi8(both);
            if(mask != 0) {
                int bit = __builtin_ctz(mask);
                size_t lane = bit >> 2;
                size_t pos = i + lane;

                Ls[pos] = Ls.back();
                Ls.pop_back();
                Rs[pos] = Rs.back();
                Rs.pop_back();
                return true;
            }
        }

        for(; i < n; ++i) {
            if(Ls[i] == ql && Rs[i] == qr) {
                Ls[i] = Ls.back();
                Ls.pop_back();
                Rs[i] = Rs.back();
                Rs.pop_back();
                return true;
            }
        }
        return false;
    }

    int count_contained(int ql, int qr) const {
        int cnt = 0;
        size_t n = Ls.size();
        size_t i = 0;

        __m256i qlv = _mm256_set1_epi32(ql - 1);
        __m256i qrv = _mm256_set1_epi32(qr + 1);

        for(; i + 7 < n; i += 8) {
            __m256i lv = _mm256_loadu_si256((const __m256i*)&Ls[i]);
            __m256i rv = _mm256_loadu_si256((const __m256i*)&Rs[i]);

            __m256i ge = _mm256_cmpgt_epi32(lv, qlv);
            __m256i le = _mm256_cmpgt_epi32(qrv, rv);

            __m256i both = _mm256_and_si256(ge, le);

            int mask = _mm256_movemask_epi8(both);
            cnt += __builtin_popcount(mask) >> 2;
        }

        for(; i < n; ++i) {
            if(Ls[i] >= ql && Rs[i] <= qr) {
                ++cnt;
            }
        }

        return cnt;
    }
};

void solve() {
    // One approach for solving this in O(Q log^2 Q) is to build a segment tree
    // on the L coordinates, and then keep all R coordinates in a sorted manner.
    // Then the update (addition / removal), ends up being a walk down to the
    // corresponding leaf of the segment tree for L, and inserting / erasing R
    // from all nodes we visit. The query ends up being just decomposing the [L;
    // R] range with the O(log Q) segment tree nodes, and figuring out how many
    // R coordinates fall within [L; R]. For the inner structure we can use some
    // BST or offline build all unique values that could appear in the segment
    // tree node, and do a segment tree / BIT over them. One easy approach is
    // to use the Policy-Based Data Structures (PBDS) from GNU C++ which is
    // widely accepted on online judges. Another simple approach that ends up
    // being fast in practice is to implement everything with a 2D fenwick tree,
    // by keeping the nodes as an unordered_map. However, after trying to
    // implement this it's a bit hard to fit in the memory limit.
    //
    // Instead, here we will use the fact that there are at most ~1000-2000
    // active segments at any moment and do a brute-force with a vector. This is
    // fast enough to pass, but we can further speed it up with AVX2 SIMD.

    ActiveSegments active;

    for(auto [is_add, l, r]: queries) {
        if(is_add) {
            int cnt = active.count_contained(l, r);
            cout << cnt << '\n';
            active.add(l, r);
        } else {
            active.remove(l, r);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    """
    Maintain active segments in two lists (Ls, Rs).
    For '+' queries: linear scan to count segments contained in [L, R], print it, then add.
    For '-' queries: find one matching segment and remove via swap-with-last.
    """

    data = sys.stdin.buffer.read().split()
    # Each query is: type L R => 3 tokens
    # type is b'+' or b'-'
    n = len(data)

    Ls = []
    Rs = []

    out_lines = []
    i = 0
    while i < n:
        t = data[i]      # b'+' or b'-'
        L = int(data[i+1])
        R = int(data[i+2])
        i += 3

        if t == b'+':
            cnt = 0
            # Active size <= 1000 => scan is fine
            for l, r in zip(Ls, Rs):
                if l >= L and r <= R:
                    cnt += 1
            out_lines.append(str(cnt))

            Ls.append(L)
            Rs.append(R)

        else:  # t == b'-'
            # Remove one occurrence if present (ignore if absent)
            for idx in range(len(Ls)):
                if Ls[idx] == L and Rs[idx] == R:
                    # swap with last, then pop
                    Ls[idx] = Ls[-1]
                    Rs[idx] = Rs[-1]
                    Ls.pop()
                    Rs.pop()
                    break

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()
```

Notes:
- Uses fast tokenized input (`buffer.read().split()`).
- Works directly with original coordinates; no compression needed.
- Deletion removes only one copy, matching the problem statement.
