自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 21:47:14，当前版本为作者最后更新于2024-05-30 09:16:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很好的一道题，让我模拟赛没看 T2 T3。

题目大意

有一个 $n$ 行的网格图，上面有 $m$ 个僵尸。

你可以选择一行扔出一个坚果，坚果会沿着这行水平滚出。

如果撞到了一个僵尸，则坚果会改变运动方向，如果水平撞上，则如果在前 $\frac{n}{2}$ 行，坚果就会向右下 $45\degree$ 方向滚出，否则向右上 $45\degree$ 方向滚出。如果是以斜着的方向撞上，则会在这两种方向中切换。然后，这个僵尸就被击倒了，并不会再出现在网格图上。

出题人要选一行扔出坚果，满足能击倒最多的僵尸的前提下编号最小。请你模拟 $k$ 轮这样的操作，每轮输出扔出的行编号和击倒的僵尸数目。

题目分析

这种较为复杂的限制，往往用图论建模来描绘。

将每个点拆点，分为左上和左下两个点。然后连向往那个方向出发后会碰到的第一个点。很容易发现，图由若干条链构成。

如果一个僵尸被击倒，则相当于这个地方不会再改变方向。只需要将两条链在此处断开然后接到正确的位置。

考虑用平衡树维护这些链，map 维护每一行出发会碰到的第一个僵尸，称这些僵尸为关键僵尸，显然我们的链只需要维护最靠左端的关键僵尸。然后用线段树维护一下每一行扔出去会击倒多少僵尸就可以了。

复杂度 $O((m+k)\log m)$。

到这都还是蓝题水平，但开始扣代码就知道这题有多 Hard 了。

#include<bits/stdc++.h>
#define ll long long
#define L(x) t[x].l
#define R(x) t[x].r
#define mid (l+r>>1)
#define lc x<<1,l,mid
#define rc x<<1|1,mid+1,r
#define OK Ll<=l&&r<=Rr
#define Root 1,1,n
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
#define Pi pair<int,int>
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(int x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N =2e5+5,M=1e6+5,MM=N*2,inf=(1LL<<30)-1;
mt19937 rd(20080626);
int n,m,k,tot;
bool Tiao=1;
inline int idl(int x){
	return x;
}
inline int idr(int x){
	return x+tot; 
}
struct node{
	int x,y,id,ty;
}a[N<<1];
map<Pi,int>P;
int nxt[N<<1],pre[N<<1],Mx,root[N<<1];
struct seg{
	int mx,id;
}xd[N];
inline void getup(int x){
	xd[x]=xd[x<<1].mx>=xd[x<<1|1].mx?xd[x<<1]:xd[x<<1|1];
}
inline void modify(int x,int l,int r,int p,int k){
	if(l==r)return xd[x]={k,l},void();
	p<=mid?modify(lc,p,k):modify(rc,p,k),getup(x);
}
struct fhq{
	int l,r,key,siz,sm,p,k,mp,f,le,lp;
}t[MM];
int cnt;
inline void create(int id,int ty,int ex){
	a[id].ty>0?t[id+ty*tot]={0,0,(int)rd(),1,1,1,1,1,0,ex,ex}:t[id+ty*tot]={0,0,(int)rd(),1,0,inf,0,inf,0,ex,ex};
}
inline void Getup(int x){
	t[L(x)].f=t[R(x)].f=x;
	t[x].siz=t[L(x)].siz+t[R(x)].siz+1,t[x].sm=t[L(x)].sm+t[R(x)].sm+t[x].k;
	t[x].mp=min({t[L(x)].mp,t[L(x)].siz+t[x].p,t[L(x)].siz+1+t[R(x)].mp});
	t[x].le=min({t[L(x)].le,t[L(x)].siz+t[x].lp,t[L(x)].siz+1+t[R(x)].le});
} 
inline Pi split(int x,int k){
	if(!x)return {0,0};
	t[x].f=0;
	if(k<=t[L(x)].siz){
		Pi now=split(L(x),k);
		L(x)=now.second,Getup(x),t[now.first].f=0;
		return {now.first,x};
	}
	Pi now=split(R(x),k-t[L(x)].siz-1);
	R(x)=now.first,Getup(x),t[now.second].f=0;
	return {x,now.second};
} 
inline int merge(int x,int y){
	t[x].f=t[y].f=0;
	if(!x||!y)return x|y;
	if(t[x].key<t[y].key)return L(y)=merge(x,L(y)),Getup(y),y;
	return R(x)=merge(R(x),y),Getup(x),x;
}
inline int getrt(int x){
	int nw=x;
	while(t[nw].f)nw=t[nw].f;
	return nw;
}
inline int getps(int x){
	int ans=1+t[L(x)].siz;
	while(t[x].f){
		if(x==R(t[x].f))ans+=t[L(t[x].f)].siz+1;
		x=t[x].f;
	}
	return ans;
}
int st[MM],tp;
map<int,int>Q[20005];
bool v[MM];
inline int getid(int x){
	return !Q[x].size()?0:(*Q[x].begin()).second;
}
inline void build(int s){
	tp=0;
	while(s)st[++tp]=s,s=nxt[s];
	int rt=st[1],k=0,id=0;
	rep(i,2,tp)rt=merge(rt,st[i]);
	rep(i,1,tp)if(v[st[i]])return modify(Root,a[st[i]].y,tp-i+1),void();
}
inline int getr(int x){
	while(R(x))x=R(x);
	return x;
}
inline int getl(int x){
	while(L(x))x=L(x);
	return x;
}
inline int got(int rt){
	if(!rt)return rt;
	int fir=t[rt].mp;
	if(fir>t[rt].siz)return rt;
	Pi now=split(rt,fir); 
	st[++tp]=getr(now.first);
	if(st[tp]>tot)st[tp]-=tot;
	return merge(now.first,got(now.second));
}
inline void del(int rt){
	if(!rt)return;
	int x=t[rt].le;
	if(x>t[rt].siz)return;
	Pi now=split(rt,x);
	modify(Root,a[getr(now.first)].y,0),merge(now.first,now.second);
}
inline void ins(int rt){
	if(!rt)return;
	int x=t[rt].le;
	if(x>t[rt].siz)return;
	Pi now=split(rt,x-1);
	int y=getl(now.second);
	if(y>tot)y-=tot;
	modify(Root,a[y].y,t[now.second].sm),merge(now.first,now.second);
}
inline void Clear(int x,int rt){
	int ps=getps(x);
	Pi A=split(rt,ps-1),B=split(A.second,1);
	t[x].k=t[x].sm=0,t[x].le=t[x].lp=t[x].mp=t[x].p=inf;
	merge(A.first,merge(B.first,B.second));
}
inline void Update(int x){
	if(!x)return;
	int rt=getrt(x),ps=getps(x);
	del(rt);
	Pi A=split(rt,ps-1),B=split(A.second,1);
	t[x].k=t[x].sm=t[x].le=t[x].lp=t[x].mp=t[x].p=1,merge(A.first,merge(B.first,B.second));
}
inline void Delete(int x){
	int pid=getid(a[x].y),nid; 
	v[x]=v[x+tot]=0,Q[a[x].y].erase(a[x].x),nid=getid(a[x].y);
	if(a[x].y<=n/2&&nid)nid+=tot;
	int rtl=getrt(x),rtr=getrt(x+tot);
	del(rtl),del(rtr),Clear(x,rtl),Clear(x+tot,rtr);
	if(pid==x)Update(nid);
	if(a[x].y!=1&&a[x].y!=n){
		int psl=getps(x),psr=getps(x+tot);
		Pi A=split(rtl,psl-1),B=split(rtr,psr-1);
		rtl=merge(A.first,B.second),rtr=merge(B.first,A.second);
	}
	ins(rtl),ins(rtr);
	if(pid==x){
		if(nid)ins(getrt(nid));
	}
}
inline void solve(int s){
	if(a[s].y<=n/2)s+=tot;
	tp=0;
	int rt=getrt(s),ps=getps(s);
	Pi now=split(rt,ps-1);
	now.second=got(now.second),rt=merge(now.first,now.second);
	rep(i,1,tp){
		int x=st[i];
		a[x].ty--;
		if(!a[x].ty)Delete(x);
	}
}
vector<int>p[N]; 
inline bool cmp(int x,int y){
	if(x>tot)x-=tot;if(y>tot)y-=tot;
	return a[x].x<a[y].x;
}
signed main(){
	n=read(),m=read(),k=read(),t[0].p=t[0].mp=t[0].le=t[0].lp=inf; 
	repm(i){
		int x=read(),y=read();
		P[{x,y}]++,Mx=max(Mx,x);
	}
	repm(i)modify(Root,i,0);
	for(auto y:P)tot++,a[tot]={y.first.first,y.first.second,tot,y.second},Q[a[tot].y][a[tot].x]=tot;
	repn(i){
		int id=getid(i);
		if(!id)continue;
		if(i<=n/2)v[idr(id)]=1;
		else v[idl(id)]=1;
	}
	rep(i,1,tot){
		if(a[i].y!=1)p[(a[i].x+a[i].y-1)%(n*2-2)].pb(i);
		if(a[i].y!=n)p[((a[i].x-a[i].y+1)%(n*2-2)+n*2-2)%(n*2-2)].pb(i+tot);
	}
	rep(i,1,tot)a[i+tot]=a[i];
	rep(i,0,n*2-3){
		sort(p[i].begin(),p[i].end(),cmp);
		int siz=p[i].size();
		rep(j,0,siz-2){
			int y=p[i][j+1];
			if(a[p[i][j+1]].y!=1&&a[p[i][j+1]].y!=n)y+=y<=tot?tot:-tot;
			nxt[p[i][j]]=y,pre[y]=p[i][j];
		}
	}
	rep(i,1,tot)create(i,0,v[i]?1:inf),create(i,1,v[i+tot]?1:inf);
	rep(i,1,tot*2)if(!pre[i])build(i);
	int sum=0;
	while(k--){
		printf("%d %d\n",xd[1].id,xd[1].mx);
		sum+=xd[1].mx;
		if(xd[1].mx>=1)solve(getid(xd[1].id));
	}
	cout<<sum;
	return 0;
}