luoguP4097 [HEOI2013]Segment

题意

李超树板子题。

对每个区间维护该区间中点\(mid\)的最优线段。

插入一个线段：

求出这个线段的斜率和截距，注意特判无斜率的情况，得到\(y=kx+b\)。

之后开始在线段树上插入，假设当前节点\(p\)区间为\([l,r]\)包含在插入区间内，那么比较插入的线段\(id\)与当前维护的线段\(pos\)，分类讨论：

1.\(id\)完全优于\(pos\)：直接替换。

2.\(id\)完全劣于\(pos\)：什么也不做。

3.找到在\(mid\)优的那条线段，将劣的那条下放到左右儿子中，那边有优势（相较于在\(mid\)更优的那条）下放哪边。

查询：

查到叶子节点后回溯，不断当前节点维护的（我们插入时把劣的那条下放，因此叶子结点不一定最优）比较。

code:

#include<bits/stdc++.h>

using namespace std;

#define ls(p) (p<<1)

#define rs(p) (p<<1|1)

const int maxn=40000;

const int maxm=1e5+10;

const double eps=1e-8;

int n,m,lastans,cnt;

int maxpos[maxn<<2];

double k[maxm],b[maxm];

inline int read()

{

	char c=getchar();int res=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();

	return res*f;

}

inline double f(int x,int id){return k[id]*x+b[id];}

inline bool check(int a,int b,int x){return fabs(f(x,a)-f(x,b))>eps?f(x,a)<f(x,b):a>b;}

void insert(int p,int l,int r,int ql,int qr,int id)

{

	int mid=(l+r)>>1;

	if(l>=ql&&r<=qr)

	{

		if(check(id,maxpos[p],l)&&check(id,maxpos[p],r))return;

		if(!check(id,maxpos[p],l)&&!check(id,maxpos[p],r)){maxpos[p]=id;return;}

		if(!check(id,maxpos[p],mid))swap(id,maxpos[p]);

		if(!check(id,maxpos[p],l))insert(ls(p),l,mid,ql,qr,id);

		else insert(rs(p),mid+1,r,ql,qr,id);

		return;

	}

	if(ql<=mid)insert(ls(p),l,mid,ql,qr,id);

	if(qr>mid)insert(rs(p),mid+1,r,ql,qr,id);

}

int query(int p,int l,int r,int pos)

{

	if(l==r)return maxpos[p];

	int mid=(l+r)>>1,res;

	res=pos<=mid?query(ls(p),l,mid,pos):query(rs(p),mid+1,r,pos);

	res=check(res,maxpos[p],pos)?maxpos[p]:res;

	return res;

}

int main()

{

	n=read();

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

	{

		int op=read();

		if(!op)

		{

			int k=(read()+lastans-1)%39989+1;

			printf("%d\n",lastans=query(1,1,40000,k));

		}

		else

		{

			int x0=(read()+lastans-1)%39989+1,y0=(read()+lastans-1)%1000000000+1,x1=(read()+lastans-1)%39989+1,y1=(read()+lastans-1)%1000000000+1;

			cnt++;

			if(x1<x0)swap(x0,x1),swap(y0,y1);

			if(x0==x1)k[cnt]=0,b[cnt]=max(y0,y1);

			else k[cnt]=1.0*(y1-y0)/(x1-x0),b[cnt]=1.0*y0-1.0*k[cnt]*x0;

			insert(1,1,40000,x0,x1,cnt);

		}

	}

	return 0;

}

巴特西

luoguP4097 [HEOI2013]Segment

题意

最新文章

热门文章