2019 牛客多校五 D generator 3

2019-08-10 by fffasttime·0评论

这也是一道不难想但不好写的题。。。
求平面上点围城的凸包的面积，点的横、纵坐标分别由一个模线性随机数生成器生成。凸包点数<=1e18, 取模的范围<=2e5。

显然横、纵坐标不超过2e5次生成就会出现循环，所以只用先分别求出第一个循环节。然后如果几个点在一条竖直线上，则只会取y坐标最大或最小的两个点。所以在只需要对每一个x的位置查询往后跳不超过n步，每一次跳跃x循环节长度后y上的最大值和最小值。只需使用st表维护即可。

中间被卡了很长时间，因为要处理循环节产生之前的部分，这个过程注意不能把范围超过n。

```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
typedef long long ll;
```
```
 
```
```
const int N=200010;
```
```
int visx[N],visy[N];
```
```
ll sx[N],sy[N],sxc,syc;
```
```
 
```

int stma[N][64],stmi[N][64],xmi[N],xma[N];

```
 
```
```
vector<int> qux[N];
```
```
 
```

ll area(ll stx,ll sty,ll x2, ll y2, ll x3, ll y3){

	return (x2-stx)*(y3-sty)-(x3-stx)*(y2-sty);

```
}
```
```
 
```
```
ll stx[N],sty[N],stm;
```
```
 
```
```
int main(){
```
```
	ll x0,y0,x00,y00,ax,ay,bx,by,px,py,n;
```

	cin>>x00>>y00>>ax>>ay>>bx>>by>>px>>py>>n;

```
	memset(xmi,0x3f,sizeof xmi);
```
```
	memset(xma,-1,sizeof xma);
```
```
	x0=x00; y0=y00;
```
```
	memset(visx,-1,sizeof visx);
```
```
	memset(visy,-1,sizeof visy);
```
```
	while (visx[x0]==-1){
```
```
		visx[x0]=sxc;
```
```
		sx[sxc++]=x0;
```
```
		x0=(x0*ax+bx)%px;
```
```
	}
```
```
	while (visy[y0]==-1){
```
```
		visy[y0]=syc;
```
```
		sy[syc++]=y0;
```
```
		y0=(y0*ay+by)%py;
```
```
	}
```
```
	if (visy[y0]>visx[x0]){
```
```
		x0=y00; y0=x00;
```

		swap(ax,ay); swap(bx,by); swap(px,py);

```
		memset(visx,-1,sizeof visx);
```
```
		memset(visy,-1,sizeof visy);
```
```
		sxc=syc=0;
```
```
		while (visx[x0]==-1){
```
```
			visx[x0]=sxc;
```
```
			sx[sxc++]=x0;
```
```
			x0=(x0*ax+bx)%px;
```
```
		}
```
```
		while (visy[y0]==-1){
```
```
			visy[y0]=syc;
```
```
			sy[syc++]=y0;
```
```
			y0=(y0*ay+by)%py;
```
```
		}
```
```
	}
```
```
	int tdy=syc,sy0=visy[y0];
```

	while (tdy<sxc) sy[tdy++]=y0, y0=(y0*ay+by)%py;

```
	int stt=visx[x0]-sy0;
```
```
	for (int i=0;i<n && i<visx[x0];i++){
```

		xmi[sx[i]]=min(xmi[sx[i]],(int)sy[i]);

		xma[sx[i]]=max(xma[sx[i]],(int)sy[i]);

```
	}
```
```
	n-=visx[x0];
```
```
	rotate(sx,sx+visx[x0],sx+sxc);
```
```
	rotate(sy,sy+sy0,sy+syc);
```
```
	syc-=sy0; sxc-=visx[x0];
```
```
	rotate(sy,sy+stt%syc,sy+syc);
```

	for (int i=0;i<sxc && i<n;i++) qux[sx[i]].push_back(i);

```
	for (int i=0;i<syc;i++)
```
```
		stma[i][0]=stmi[i][0]=sy[i];
```
```
	int dk=log(n/sxc)/log(2)+1;
```
```
	for (int k=1;k<=dk;k++)
```
```
		for (ll i=0;i<syc;i++)
```

			stma[i][k]=max(stma[i][k-1],stma[(i+(1ll<<(k-1))%syc*sxc)%syc][k-1]),

			stmi[i][k]=min(stmi[i][k-1],stmi[(i+(1ll<<(k-1))%syc*sxc)%syc][k-1]);

```
	for (int i=0;i<px;i++)
```
```
		for (auto xp:qux[i]){
```
```
			if (n<1) continue;
```
```
			ll l=xp%syc,sc=n/sxc+(xp<n%sxc);
```
```
			if (sc==0) continue;
```
```
			int p=log(sc)/log(2.0); 
```
```
			ll r=(xp+(sc-(1ll<<p))%syc*sxc)%syc;
```

			xmi[i]=min(xmi[i],min(stmi[l][p],stmi[r][p]));

			xma[i]=max(xma[i],max(stma[l][p],stma[r][p]));

```
		}
```
```
 
```

	for (int i=0;i<px;i++) if (xmi[i]<1e6){

		while (stm>1 && area(stx[stm-2],sty[stm-2],stx[stm-1],sty[stm-1],i,xmi[i])<=0) stm--;

```
		stx[stm]=i; sty[stm++]=xmi[i];
```
```
	}
```
```
	int tstm=stm;
```

	for (int i=px-1;i>=0;i--) if (xma[i]>-1){

		while (stm>tstm && area(stx[stm-2],sty[stm-2],stx[stm-1],sty[stm-1],i,xma[i])<=0) stm--;

```
		stx[stm]=i; sty[stm++]=xma[i];
```
```
	}
```
```
	ll ans=0;
```
```
	for (int i=2;i<stm;i++)
```

		ans+=area(stx[0],sty[0],stx[i-1],sty[i-1],stx[i],sty[i]);

```
	cout<<ans<<'\n';
```
```
	return 0;
```
```
}
```

发表评论取消回复