【JZOJ5801】【2018.8.12省选模拟】circular

题目大意

分析

把环拆开

线段其实就是区间

对于每个区间，向在TA后面并且b_i最小的区间连边，

然后从每个区间(ai,bi)开始，在保证跳到的区间(aj,bj)，bj<=ai+m的情况下向后倍增。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

#include <bitset>

#include <set>

#include <vector>

const int inf=2147483647;

const int mo=1e9+7;

const int N=100005;

using namespace std;

struct arr

{

	int x,y,be;

}a[N*2],b[N*2];

int n,m,g[N*2][25],mn[N*2],ans;

bool cmp(arr x,arr y)

{

	return x.y<y.y || (x.y==y.y && x.x<y.x);

}

bool cmp1(arr x,arr y)

{

	return x.x<y.x || (x.x==y.x && x.y<y.y);

}

int main()

{

	scanf("%d%d",&m,&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d%d",&a[i].x,&a[i].y);

		if(a[i].x>a[i].y) a[i].y+=m;

		a[i+n].x=a[i].x+m,a[i+n].y=a[i].y+m;

	}

	sort(a+1,a+1+n,cmp);

	for(int i=1;i<=n*2;i++) b[i]=a[i],b[i].be=i;

	sort(b+1,b+1+n,cmp1);

	a[0].y=b[n*2+1].y=inf,mn[n*2+1]=n*2+1;

	for(int i=n*2;i>=1;i--) mn[i]=b[i].y<b[mn[i+1]].y?i:mn[i+1];

	for(int i=1,pos=1;i<=n*2;i++)

	{

		while(a[i].y>b[mn[pos]].x && pos<=n*2) pos++;

		g[i][0]=b[mn[pos]].be;

	}

	for(int j=1;j<=20;j++)

		for(int i=1;i<=n*2;i++) g[i][j]=g[g[i][j-1]][j-1];

	ans=1;

	for(int i=1;i<=n;i++)

	{

		int k=i,sum=0;

		for(int j=20;j>=0;j--)

			if(a[g[k][j]].y<=a[i].x+m) k=g[k][j],sum+=1<<j;

		ans=max(ans,sum);

	}

	printf("%d",ans+1);

}

巴特西

【JZOJ5801】【2018.8.12省选模拟】circular

题目大意

分析

最新文章

热门文章