https://ac.nowcoder.com/acm/contest/331/E
C++版本一
题解:
std
题意转化为:读入一些区间,输出直到有区间交叉的第一个位置。
正经解法:
考虑线段树维护最小值。将左端点值赋值在右端点下标,查询左闭右开内最小值是否小于左端点。
随意解法:
树状数组哈希即可,具体的做法是对于每次连线,随机一个足够随机的值s,然后在首尾分别加上s和减去s,每次查询连线的区间是否和为0即可。
如果和不为0,说明有线交叉了。
时间复杂度O(mlogn)
#include <bits/stdc++.h>
using namespace std;
//因为本题标程过长,故只放出不正经解法。
const int mn = 1e5 + 5;
typedef long long ll;
int n, m;
int a[mn], b[mn];
int rrand() { //一种简易的随机方法
return (rand() << 15) + rand();
}
ll t[mn];
void add(int i, int x) {
while (i <= n) t[i] += x, i += i & -i;
}
ll sum(int i) {
ll s = 0;
while (i) {
s += t[i];
i -= i & -i;
}
return s;
}
ll sum(int l, int r) { return sum(r) - sum(l - 1); }
int main() {
int T;
cin >> T;
while (T--) {
memset(t, 0, sizeof t);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &a[i], &b[i]);
}
int ans = -1;
for (int i = 1; i <= m; i++) {
if (a[i] > b[i]) swap(a[i], b[i]);
if (sum(a[i], b[i]) != 0) {
ans = i;
break;
}
int u = rrand();
add(a[i], u);
add(b[i], -u);
}
printf("%d\n", ans);
}
return 0;
}