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; }

?

總結

以上是生活随笔為你收集整理的炫酷划线的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。