题目描述
思路:(离散化 + 差分)
考虑到题目输入数据多个区间[l,r] 且 发现需要运用差分,那么就对整体进行离散化
由于n范围<=5e5 那么离散化后的数组长度为<=5e5 * 2
可以利用差分相加求出当前哪个时刻满足k名同学,差分异或求出当前整个区间对当前时刻的异或值
除此之外,在差分中对[l,r]区间+1, 仅差分操纵就是在b[l] += 1, b[r + 1] -= 1。
但会发现离散化后在b[r + 1] 的点上进行操纵。 和之前完全不一样。
所以要把右端点+1放入离散化数组,找到离散化后准确的(r + 1)的位置
差分不仅能维护相加减,还能维护异或。。
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 5e5 + 10;
typedef pair <int, int> PII;
ll a[maxn], b[maxn], c[maxn];
ll d[maxn * 2], t[maxn * 2];
int main()
{
int n, k;
scanf("%d %d", &n, &k);
vector <ll> alls;
for(int i = 1 ; i <= n ; i ++)
{
scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
alls.push_back(a[i]), alls.push_back(b[i] + 1ll);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());//进行了离散化
for(int i = 1 ; i <= n ; i ++)
{
int l = lower_bound(alls.begin(), alls.end(), a[i]) - alls.begin() + 1; //在对应的区间 进行操纵
int r = lower_bound(alls.begin(), alls.end(), b[i] + 1ll) - alls.begin() + 1;
d[l] += 1ll, d[r] -= 1ll;
t[l] ^= c[i], t[r] ^= c[i];
}
ll res = -1;
for(int i = 1 ; i <= alls.size() ; i ++)
{
d[i] += d[i - 1];
t[i] ^= t[i - 1];
if(d[i] >= k)
res = max(res, t[i]);
}
printf("%lld\n", res);
return 0;
}