下面给出详细的讲解，帮助你理解“扫描线算法”和“随机异或哈希”在这道题中的应用，以及它们在算法竞赛中的常见用法和模板代码。

题目回顾 在数轴上有 n 个闭区间 ([l_i, r_i]) 。我们说两个数 x 和 y 性质不同，若存在某个区间 S 使得 x 属于 S 而 y 不属于 S（或者反之）。要求选取数轴上的若干整数，使得它们两两性质不同，求最多能选取多少个。

思路概要 可以证明：数轴上区间性质只会在某些“临界点”（区间开始的 l 和区间结束后紧接的 r+1 处）产生变化。也就是说，在两个连续“事件点”之间的所有整数，其“区间所属状态”（哪些区间内包含该整数）都是相同的。

因此，我们只需要模拟这些事件点，并记录每个区间的状态（“active”或者“不active”）。用一个状态来表示“当前处于哪些区间内”，题目要求的答案就是所有不同状态的个数（外加状态不在任何区间内，即状态 0）。

不过，由于 n 可能比较大，直接用 n 维二进制数组表示状态难以处理。所以我们采用 随机哈希 的技巧，每个区间生成一个随机数，用 XOR 操作“合并”所有处于活跃状态的区间的随机数，形成一个 64 位数，作为该状态的“哈希”。这样一来，不同的状态必然对应不同的哈希值（碰撞概率非常低），从而统计不同状态即可。

---

一、扫描线算法讲解

扫描线（Sweep Line）是一种遍历事件（一般是横轴上的点或其他特征）的方法。核心思想是：

1. 枚举所有会导致状态变化的“事件”： 对于每个区间 ([l, r]) 来说，状态改变发生在下列两个位置：

   • 当 x = l 时，区间开始（激活事件）。
   • 当 x = r + 1 时，区间结束（移除或失效事件），因为在 x = r 时仍然处于该区间。

2. 按“事件点”从小到大排序 当多个事件在同一个位置时，我们一般需要规定处理顺序。在本题中，要求在同一点先“移除”再“激活”。这种处理顺序保证了：

   • 在 x = r+1 的位置，刚好被失效区间不再认为是活跃的；
   • 在 x = l 的位置，新加入的区间被算作活跃状态。

3. 模拟状态的变化 设一个变量 curState 表示当前状态。初始状态为空集合（这里用 0 表示）。 然后依次处理每个事件，对 curState 进行更新。事件处理完后，curState 表示在当前区间（从当前事件点到下个事件点之前）的状态。

这种方法通常用于求“覆盖区间”、“线段树离散化”、“区间合并”等问题。在竞赛中，扫描线算法是处理连续变化状态及区间交集问题的重要工具之一。

---

二、随机异或哈希讲解

在本题中，“状态”其实是每个整数在 n 个区间中的“所属关系”，原本可以用一个长度 n 的二进制串表示（第 i 位代表 x 是否在区间 i 内），但这样的表示内存和处理开销太大。因此我们采用随机哈希技巧来“压缩”这一状态。

为什么选择异或 (XOR)？

1. 可逆性： 异或运算有一个性质：对于任意数 a，有 [ a \oplus b \oplus b = a ] 也就是说，当我们希望“添加”一个区间的哈希（表示该区间变为活跃）时，可以做 [ curState , \oplus= , hash_i; ] 当该区间结束时，只需再做一次相同的 XOR 操作就可以“取消”之前的影响（因为 (hash_i \oplus hash_i=0)）。这种可逆性非常适合用于区间“加入”和“移除”的场景。

2. 随机性降低碰撞概率： 为每个区间生成一个随机的 64 位数（例如：uint64_t hash[i]），只要随机数足够分散，不同的组合经过 XOR 得到相同结果的概率极低，因此可以近似认为不同的活跃区间集合对应唯一的哈希值。

3. 操作简单高效： XOR 运算比加法更能“对消”，而且在硬件上操作速度非常快，适合竞赛中的时间要求。

如何利用异或哈希表示状态？

• 初始状态： 设 curHash = 0。表示没有任何区间被激活。

• 区间激活（事件 x = l）： 当遇到一个区间激活事件时，将对应区间的随机数与 curHash 进行异或操作： [ curHash \mathrel{\oplus}= hash[i] ] 对应的逻辑是：将该区间加入当前活跃集合。

• 区间失效（事件 x = r+1）： 当遇到一个区间失效事件时，同样异或该区间的随机数： [ curHash \mathrel{\oplus}= hash[i] ] 由于同一个随机数进行两次 XOR 会还原原值，因此这一步相当于把该区间从活跃集合中移除。

这样整个过程模拟的就是一个“加进集合”与“从集合中移除”的过程，而不必实际保存集合中的所有区间，只需要“累积”一个 64 位的哈希值表示当前活跃区间的组合。

---

三、完整模板代码（异或哈希版本）

下面给出使用异或哈希实现的完整 C++ 代码，同时包含详细注释，符合 OI/ACM 风格。代码首先生成事件，然后利用扫描线模拟状态变化时用 XOR 进行哈希更新，并将所有不同状态存入集合，最后答案为不同状态的数量。

#include <bits/stdc++.h>
using namespace std;
 
// 定义事件结构体，表示数轴上发生状态改变的点
struct Event {
    long long pos;   // 事件发生的位置
    int type;        // 事件类型：+1 表示区间激活（开始），-1 表示区间失效（结束后，即 r+1）
    int idx;         // 该事件对应的区间下标
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int t; 
    cin >> t;
  
    // 使用 Mersenne Twister 的 64 位版本生成随机数，用于生成每个区间的随机哈希值
    mt19937_64 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
 
    while(t--){
        int n;
        cin >> n;
      
        // 对于每个区间，我们将生成一个随机的64位无符号整数
        vector<unsigned long long> hashVals(n);
        for(int i = 0; i < n; i++){
            hashVals[i] = rng();
        }
 
        // 生成所有事件，每个区间生成两个事件
        vector<Event> events;
        events.reserve(2 * n);
 
        long long l, r;
        for (int i = 0; i < n; i++){
            cin >> l >> r;
            // 激活事件：在位置 l，将区间 i 加入（即异或其随机数）
            events.push_back({l, +1, i});
            // 失效事件：在位置 r+1，将区间 i 移除（即再次异或其随机数）
            events.push_back({r + 1, -1, i});
        }
 
        // 排序所有事件：先按位置升序，如果位置相同，则先处理失效事件 (-1)，再处理激活事件 (+1)
        sort(events.begin(), events.end(), [](const Event &a, const Event &b) {
            if(a.pos == b.pos)
                return a.type < b.type; // -1 在前
            return a.pos < b.pos;
        });
 
        // 使用 curHash 来记录当前活跃区间的哈希，初始值表示空集合
        unsigned long long curHash = 0ULL;
        // 使用 unordered_set 来保存所有遇到的状态哈希值，从而统计不同状态数
        unordered_set<unsigned long long> distinct;
 
        // 初始状态（即在负无穷到第一个事件点之前）均为 0
        distinct.insert(curHash);
 
        int m = events.size();
        int i = 0;
        // 扫描所有事件：每个不同的位置更新一次状态
        while(i < m){
            long long currPos = events[i].pos;
 
            // 在同一位置上可能存在多个事件，一次处理完所有该位置的事件
            while(i < m && events[i].pos == currPos){
                // 对于失效和激活事件都采用 XOR 操作
                // 利用 XOR 的性质：两次 XOR 同一个值可以互相抵消
                curHash ^= hashVals[events[i].idx];
                i++;
            }
 
            // 记录当前状态（在从 currPos 开始直至下一个事件前，状态不变）
            distinct.insert(curHash);
        }
 
        // 不同状态的数量即为可以选出的性质不同的整数个数
        cout << distinct.size() << "\n";
    }
 
    return 0;
}

---

四、模板代码与应用说明

在竞赛中，你可以将“事件结构体”、“扫描线处理过程”以及“随机异或哈希”作为常用模板。一般步骤包含：

1. 离散化或提取关键点： 就像本题只在区间的起点和 r+1 点状态变化一样，其他涉及区间或者前后扫描的问题，都可以提取这些“关键点”来简化问题。

2. 事件排序： 模板代码中通常会将事件按坐标排序，若坐标相同则设定一个合适的次序（例如先删除后添加）。

3. 状态更新与记录： 用一个全局状态变量（如 curHash）来记录当前状态，每当状态变化后记录或更新答案。

4. 随机异或哈希： 为每个元素（或者在本题中每个区间）生成一个随机数，然后通过 XOR 来模拟集合的加入或删除。

   • 如果你要“添加”一个元素，则做：state ^= randomNumber
   • 如果你要“删除”一个元素，再次做同样的 XOR 操作即可，因为 (a ^ b ^ b = a) 从而取消 b 的影响。 常见应用包括：
   • 判断两个集合是否相等（对集合中的所有元素的随机数做 XOR，看两个集合是否得到相同的结果）。
   • 快速比较子数组、子序列等，在字符串哈希（比如 Rabin-Karp 的思想中也有类似原理，只不过常用乘法加法融合）中也有其他哈希技术。

---

总结

• 扫描线算法在区间问题中十分常见，能够高效地依次处理区间的“起点”与“终点变化”。
• 随机异或哈希利用 XOR 的可逆性，可以用来压缩高维状态或集合信息，从而支持高效比较与查重。本题即利用这一技术，将“区间激活集合”映射为一个 64 位整数，极大地降低了实现难度，同时保证了正确性。
• 这种组合在实际竞赛中十分高效，常用于解决“区间性质不同”、“子集比较”、“数组去重”等问题。

希望以上详细讲解与代码示例能帮助你更好地掌握扫描线和随机异或哈希的核心思路，并在今后的竞赛中加以应用。