【牛客 - 331E】炫酷划线（权值线段树，树状数组哈希，随机数）

题干：

链接：https://ac.nowcoder.com/acm/contest/331/E
来源：牛客网
 

平面上有一个圆，圆环上按顺时针顺序分布着从1到n，一共n个点。

现在无聊的小希开始按某种顺序对其在圆内两两连线，小希尽量避免让两条线碰撞，可是有的时候，这显然避免不了。

现在你知道小希划线的顺序是什么，请你判断小希在最优情况下，什么时候会被迫使得线相交，输出最早的时刻（是第几条线）。

输入描述:

数据第一行一个整数T，表示数据组数。每组数据第一行输入两个整数N,M，代表点的个数和游戏进行的轮数。随后M行，每行两个整数aiai,bibi，表示两个点之间连线。数据保证每个点最多被连线一次。T≤10T≤101≤N,M≤1000001≤N,M≤1000001≤ai,bi≤1000001≤ai,bi≤100000

输出描述:

对于每组数据，一行。如果中途某一条线开始无法避免相交，则输出当轮轮数。否则，输出-1。

示例1

输入

复制

2 10 4 5 3 1 9 2 6 7 10 4 2 1 2 3 4

输出

复制

4 -1

一句话题意：

   读入一些区间，输出直到有区间交叉的第一个位置。（区间包含的情况不算是交叉）

解题报告：

正经解法：

考虑线段树维护最小值。将左端点值赋值在右端点下标，查询左闭右开内最小值是否小于左端点。

随意解法：

树状数组哈希即可，具体的做法是对于每次连线，随机一个足够随机的值rd（比较大的数），然后在首尾分别加上rd和减去rd（也就是使得这条线段只在这个区间内起作用，出了这个区间就消除了影响），每次查询连线的区间是否和为0即可。如果和不为0，说明有线交叉了。

时间复杂度O(mlogn)

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int n,m; ll c[MAX]; int a[MAX],b[MAX]; int lowbit(int x) {return x&-x;} ll query(int x) {ll res = 0;while(x > 0) {res += c[x];x -= lowbit(x);}return res; } void update(int x,ll val) {while(x < MAX) {c[x] += val;x += lowbit(x);} } int main() {int t;cin>>t;srand(time(NULL));while(t--) {cin>>n>>m; memset(c,0,sizeof c);for(int i = 1; i<=m; i++) {scanf("%d%d",a+i,b+i);if(a[i] > b[i]) swap(a[i],b[i]);}int ans = -1;for(int i = 1; i<=m; i++) {if( (query(b[i]) - query(a[i] - 1)) != 0) {ans = i;break;}ll rd = (rand()<<15) + rand()*rand();update(a[i],rd);update(b[i],-rd);}printf("%d\n",ans); }return 0 ;}

 

总结

以上是生活随笔为你收集整理的【牛客 - 331E】炫酷划线（权值线段树，树状数组哈希，随机数）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。