#创作计划# 今晚ABC F题解
2025-09-21 12:27:11
发布于：广东
36阅读
0回复
0点赞
史诗级猎奇做法。
题意解析：你需要在一个圆中进行 次操作。每次操作如下：
- 给定两个正整数 。
- 请你判断并输出圆上端点为 的线是否与其他圆上已有的线相交。
- 如果不相交，请添加这条线。
显然，这可以转换成区间问题，假设这次添加的线是 ，则问题为判断是否有已添加的区间 使得 。
显然可以线段树解决。
但众所周知，我不会线段树。
所以我就想到了一个很猎奇的做法。
我们可以查一下左端点和右端点，看看它们所在的所有区间是否相同，如果相同就说明符合题意。
直接 ？显然不可以，随便找个反例比如说把一个区间拆成两半就能 hack 了。
我们可以使用异或哈希。
我们给每个区间赋一个随机权值，然后判断两端点的值是否相等即可，如果相等往这个区间异或上权值。显然可以树状数组实现。
显然只要权值值域够大，它的错误率就极小。而且最关键的是，无法通过构造来卡掉这种做法！
#include <iostream>
#include <cstdio>
#include <vector>
#include <random>
#include <ctime>
#define int unsigned long long
using namespace std;
mt19937_64 rng(time(0));
int mp[300005];
class FenwickTree{
vector <int> tree;
int n;
public:
FenwickTree(){}
FenwickTree(int n){
this -> n = n;
tree.resize(n);
}
void insert(int idx, int val){
for(int i = idx; i <= n; i += (i & (-i))) tree[i] ^= val;
}
int query(int idx){
int ans = 0;
for(int i = idx; i; i -= (i & (-i))) ans ^= tree[i];
return ans;
}
};
int n, m;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++){
mp[i] = rng();
}
FenwickTree tr(n + 5);
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
if(tr.query(x) != tr.query(y)){
cout << "No\n";
}else{
cout << "Yes\n";
tr.insert(x, mp[i]);
tr.insert(y + 1, mp[i]);
}
}
return 0;
}
时间复杂度：。
有帮助，赞一个