省选模拟测试5

T1 点点的圈圈

因为只有包含关系和不相交关系，就可以根据包含关系\(O(n^2)\)建树，\(O(n)\)跑树形dp

考虑优化建树，把一个圆看成一个正方形然后做扫描线，线段树每个节点维护set，存纵坐标在这个区间的正方形的编号

需要判四个角，暴力跳就行了

大多数情况下复杂度\(O(n\log^2n)\)

T2 点点的计算

发现\(T(n,k)=nC(n-1,k-1)\)

然后继续观察，我们要求的是\(lcm(n-k+1,n-k+2 ...n)\)

构造一个数组\(G_i\),使得上式等于\(\prod_{i=n-k+1}^{n}G_i\)

考虑已经构造出 n-1 时的G数组，先在\(G_n\)处插入 n

这样显然不一定合法，因为n的质因子在前面出现过，这样会重复

将n质因数分解，计算\(p^k\)，q设为k

如果之前出现了\(p^r\)，若r>=q，使r减q，否则r->0，q也减r

可以给每种质数开个栈，可持久化线段树维护即可

复杂度\(O(m\log^2m + t\log m)\)

T3

没改出来

代码

T1

#include
using namespace std;
#define il inline
#define int long long
const int N=1e5+11;
const int inf=1e9;
struct pot_{int xl,xr,yd,yp,x,y,r,w;}pot[N];
struct tree{int l,r;set st;}tre[8*N];
bool vis[N];
int n;
int f[N];
int lsh[2*N],num;
vector vi[2*N],vo[2*N],vct[N];
il int pd(int x){return x*x;}
il int min_(int x,int y){return x>y?y:x;}
il int max_(int x,int y){return x>y?x:y;}
il bool cmp(pot_ a,pot_ b){return a.r'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void build(int i,int l,int r)
{
	tre[i].l=l,tre[i].r=r;
	tre[i].st.clear();
	if(l==r) return;
	int mid=(l+r)>>1;
	build(i<<1,l,mid),build(i<<1|1,mid+1,r);
	return;
}
void insert(int i,int l,int r,int id,bool jd)
{
	if(tre[i].l>=l&&tre[i].r<=r){if(jd) tre[i].st.insert(id);else tre[i].st.erase(id);return;}
	int mid=(tre[i].l+tre[i].r)>>1;
	if(l<=mid) insert(i<<1,l,r,id,jd);
	if(r>mid) insert(i<<1|1,l,r,id,jd);
	return;
}
int qry(int i,int x,int id)
{
	int ans=inf;
	if(tre[i].st.size())
	{
		set::iterator it=tre[i].st.lower_bound(id);
		for(;it!=tre[i].st.end();++it)if(jud(pot[id],pot[*it])){ans=*it;break;}
	}
	if(tre[i].l==tre[i].r) return ans;
	int mid=(tre[i].l+tre[i].r)>>1;
	if(x<=mid) ans=min_(qry(i<<1,x,id),ans);
	else ans=min_(qry(i<<1|1,x,id),ans);
	return ans;
}
void get_ans(int x)
{
	vis[x]=1;
	for(int v : vct[x]) get_ans(v),f[x]+=f[v];
	f[x]=max_(f[x],pot[x].w);
	return;
}
signed main()
{
	n=read();
	for(int x,y,r,w,i=1;i<=n;++i)x=read(),y=read(),r=read(),w=read(),pot[i]=(pot_){x-r,x+r,y-r,y+r,x,y,r,w};
	for(int i=1;i<=n;++i) lsh[++num]=pot[i].xl,lsh[++num]=pot[i].xr;
	sort(lsh+1,lsh+num+1);
	int k=unique(lsh+1,lsh+num+1)-lsh;
	for(int i=1;i<=n;++i)
	{
		pot[i].xl=lower_bound(lsh+1,lsh+k,pot[i].xl)-lsh;
		pot[i].xr=lower_bound(lsh+1,lsh+k,pot[i].xr)-lsh;
	}
	num=0;for(int i=1;i<=n;++i) lsh[++num]=pot[i].yd,lsh[++num]=pot[i].yp;
	sort(lsh+1,lsh+num+1);
	k=unique(lsh+1,lsh+num+1)-lsh;
	for(int i=1;i<=n;++i)
	{
		pot[i].yd=lower_bound(lsh+1,lsh+k,pot[i].yd)-lsh;
		pot[i].yp=lower_bound(lsh+1,lsh+k,pot[i].yp)-lsh;
	}
	sort(pot+1,pot+n+1,cmp);
	for(int i=1;i<=n;++i) vi[pot[i].xl].push_back(i),vo[pot[i].xr].push_back(i);
	build(1,1,2*n);
	for(int fa,i=1;i<=2*n;++i)
	{
		for(int x : vo[i]) insert(1,pot[x].yd,pot[x].yp,x,0);
		for(int x : vi[i])
		{
			fa=qry(1,pot[x].yd,x);
			if(fa!=inf) vct[fa].push_back(x);
			insert(1,pot[x].yd,pot[x].yp,x,1);
		}
	}
	int ans=0;
	for(int i=n;i;--i)if(!vis[i])get_ans(i),ans+=f[i];
	cout<

#include
using namespace std;
#define int long long
#define il inline
const int N=2e5+11;
const int mod=1e9+7;
struct vct_{signed x,mi;}sta[N][20];
struct tree{signed lc,rc;int val;}tre[8409110];
bool fp[N];
signed q,n,k,a,b,p;
signed root[N],tot;
signed pr[N],num,top[N];
int c[N],d[N];
vector vct[N];
int fm(int x,int y){int ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
il int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void pre()
{
	fp[0]=fp[1]=1;
	for(int i=2;i>1;
	if(x<=mid) ins(tre[i].lc,tre[j].lc,l,mid,x,val);
	else ins(tre[i].rc,tre[j].rc,mid+1,r,x,val);
	return;
}
int qry(signed i,int l,int r,int L,int R)
{
	if(!i) return 1;
	if(l>=L&&r<=R) return tre[i].val;
	int mid=(l+r)>>1;
	int val=1;
	if(L<=mid) val=qry(tre[i].lc,l,mid,L,R);
	if(R>mid) val=val*qry(tre[i].rc,mid+1,r,L,R)%mod;
	return val;
}
signed main()
{

	pre();
	q=read();
	n=read(),k=read();
	a=read(),b=read(),p=read();
	for(int i=2;i<=q;++i) c[i]=read();
	for(int i=2;i<=q;++i) d[i]=read();
	ins(root[1],root[0],1,1e5,1,1);
	for(int mi,pri,mis,loc,now,i=2;i<=1e5;++i)
	{
		root[i]=root[i-1];
		ins(root[i],root[i],1,1e5,i,i);
		for(vct_ x : vct[i])
		{
			now=top[pri=x.x],mi=x.mi;
			while(now>0&&(mis=sta[pri][now].mi)<=mi)
			{
				loc=sta[pri][now].x;
				ins(root[i],root[i],1,1e5,loc,fm(fm(x.x,mis),mod-2));
				mi-=mis,--now;
			}
			if(now){if(mi) ins(root[i],root[i],1,1e5,sta[pri][now].x,fm(fm(x.x,mi),mod-2)),sta[pri][now].mi-=mi;}
			sta[pri][++now]={i,x.mi};
			top[pri]=now;
		}
	}
	int ans=qry(root[n],1,1e5,n-k+1,n);
	printf("%lld\n",ans);
	for(int i=2;i<=q;++i)
	{
		n=(a*ans+c[i])%p+1;
		k=(b*ans+d[i])%n+1;
		printf("%lld\n",ans=qry(root[n],1,1e5,n-k+1,n));
	}
	return 0;
}