电商网站建设用php,做pc端网站平台,redis 在网站开发中怎么用,修水县城乡建设局官方网站题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/331/E 来源#xff1a;牛客网
平面上有一个圆#xff0c;圆环上按顺时针顺序分布着从1到n#xff0c;一共n个点。 现在无聊的小希开始按某种顺序对其在圆内两两连线#xff0c;小希尽量避免让两…题干
链接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代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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;cint;srand(time(NULL));while(t--) {cinnm; memset(c,0,sizeof c);for(int i 1; im; i) {scanf(%d%d,ai,bi);if(a[i] b[i]) swap(a[i],b[i]);}int ans -1;for(int i 1; im; 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 ;}
