15011418730 LV 7 @ 2025-8-24 22:14:39

自动搬运

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:14:39，当前版本为作者最后更新于2020-02-21 22:58:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

\mathsf{Preface}

题面传送门

题意简述：题面太长，细节太多，没法简述。。。

看起来现在的 $\sf{AC}$ 记录里面除了我和出题人，别的都是抄题解的。。（截至 $2020.2.21\ 23:08$ ）

锻炼码力 + $\rm{debug}$ 能力的题目。我对拍了无数次才把自己的错误一一找出来。

吐槽一下：这！题！的！细！节！是！真！T！M！多！

为了我花在这道题目上的 $\rm{3.5h}$ ，我一定得写篇题解。

\sf{Solution}

\sf{Step\ One:Prework}

敢做这道题目的应该都能一眼看出是线段树。。。

我们先把所有位置离散化，然后将 $\rm{key}$ 按下落时间排序，将 $\rm{click}$ 按点击时间排序，方便统计答案。

该部分的注意点：

和出题人给出的题解一样，尽量用整数存储答案，即将读入的数乘上 $10^5$ 。
化成整数的时候有精度误差，可以加上像四舍五入一样加上 $0.5$ 。

$\rm{key}$ 的读入及离散化：

const int N=1.2e5+5,inf=2e9+7;
struct key{
	int t,a,b,sta,ju;//sta是这个key的状态，ju是这个key被判定的时间
	bool operator < (const key &v) const {return t<v.t;}//按时间排序
}c[N];
struct click{
	int t,pos;
	bool operator < (const click &v) const {return t<v.t;}
}q[N];
int n,m,cnt,pos[N<<2];
......main函数内
	read(n),read(m);
	for(int i=1;i<=n;i++){
		double x,y,z; read(x),read(y),read(z);
		c[i]={x*1e5+0.5,y*1e5+0.5,z*1e5+0.5,0};
		pos[++cnt]=c[i].a,pos[++cnt]=c[i].b;
	}
	for(int i=1;i<=m;i++){
		double x,y; read(x),read(y);
		q[i]={x*1e5+0.5,y*1e5+0.5};
		pos[++cnt]=q[i].pos; 
	}
	sort(c+1,c+n+1),sort(q+1,q+m+1),c[0].t=inf;//c[0].t赋为inf，更方便
	sort(pos+1,pos+cnt+1);
	cnt=unique(pos+1,pos+cnt+1)-pos-1;

\sf{Step\ Two:Build\ SegmentTree}

将相应的 $\rm{key}$ 添加到线段树相应的位置上，因为线段树的一个区间可能会被多个 $\rm{key}$ 覆盖，所以每个区间可以存一个链表，链表里面存 $\rm{key}$ 的编号。

因为位置离散化后会达到 $2n+m$ ，所以空间要开大一些。（反正不会 $\sf{MLE}$ 就行）

线段树的建造：

int get(int x){return lower_bound(pos+1,pos+cnt+1,x)-pos;}//返回离散化后的值
int node,hd[N<<4],tl[N<<4],nxt[N<<7],val[N<<7];
void push(int x,int id){//链表添加
	if(!hd[x])hd[x]=tl[x]=++node;
	else nxt[tl[x]]=++node,tl[x]=node;
	val[node]=id;
}
void add(int l,int r,int ql,int qr,int x,int id){//添加key
	if(ql<=l&&r<=qr){
		push(x,id);
		return;
	}
	int m=l+r>>1;
	if(ql<=m)add(l,m,ql,qr,x<<1,id);
	if(m<qr)add(m+1,r,ql,qr,x<<1|1,id);
}
......main函数内
	for(int i=1;i<=n;i++){
		int p1=get(c[i].a),p2=get(c[i].b);
		add(1,cnt,p1,p2,1,i);
	}

\sf{Step\ Three:Query}

对每一个点击，先求出它产生判定效果的 $\rm{key}$ 是在什么时候下落的，如果此次点击时间为 $T$ ，位置为 $P$ ，也就是求出 $\min_{a_i\leq P\leq b_i,\ T-0.6s<t_i<T+1s}t_i$ ，记为 $t$ 。（区分 $t$ 和 $T$ ）

另外，在求 $t$ 的时候要将前面已经 “过期” 或者 “已被判定” 的 $\rm{key}$ 弹出。

给出此部分的代码：

#define d val[hd[x]]//宏定义方便
void update(int x,int t){//将过期或已被判定的key弹出
	while(hd[x]){
		if(c[d].t+60000<=t){//过期
			if(!c[d].sta)c[d].ju=c[d].t+60000,c[d].sta=1;
			hd[x]=nxt[hd[x]];
		}
		else if(c[d].sta)hd[x]=nxt[hd[x]];//已被判定
		else break;//否则break 
	}
}
int tim(int x,int t){//求一下会判定的key的下落时间
	if(c[d].t-t>=100000)return inf;//如果还没到判定范围就返回inf（如果链表为空，因为前面c[0].t赋为inf了，所以也会返回inf） 
	else return c[d].t;
}
int query(int l,int r,int pos,int x,int t){
	update(x,t);
	if(l==r)return tim(x,t);//如果到底了就返回
	int m=l+r>>1;
	if(pos<=m)return min(tim(x,t),query(l,m,pos,x<<1,t));
	else return min(tim(x,t),query(m+1,r,pos,x<<1|1,t));//因为判定的是最低的key，所以取min
}

接下来判定所有下落时间为 $t$ 的 $\rm{key}$ 。

注意点：如果没有可以判定的 $\rm{key}$ （即代码中 $t=\rm{inf}$ ），跳过此部分，否则可能会导致死循环。

void modify(int l,int r,int pos,int x,int t,int T){
	while(c[d].t==t){//如果下落时间为本次key的判定下落时间t
		if(!c[d].sta){//如果没有被判定
			c[d].ju=T;//记录被判定的时间T（再次说明，请区分t和T）
			if(abs(c[d].t-T)<20000)c[d].sta=3;//根据题目所给的条件进行判定，下同 
			else if(abs(c[d].t-T)<60000)c[d].sta=2;
			else c[d].sta=1;
		}
		hd[x]=nxt[hd[x]];
	}
	if(l==r)return;
	int m=l+r>>1;
	if(pos<=m)modify(l,m,pos,x<<1,t,T);
	else modify(m+1,r,pos,x<<1|1,t,T);
}
......main函数内
	for(int i=1;i<=m;i++){
		int p=get(q[i].pos),t=query(1,cnt,p,1,q[i].t);
		if(t!=inf)modify(1,cnt,p,1,t,q[i].t);//如果有判定的key就判定
	}

\sf{Step\ Four:Calculate\ Answer}

有了每个 $\rm{key}$ 的判定时间和判定状态，答案就很好计算了，将每个 $\rm{key}$ 按照判定时间排序，判定时间相同按 $\sf{miss,good,perfect}$ 排序即可。

此部分代码：

bool cmp(key a,key b){return a.ju<b.ju||a.ju==b.ju&&a.sta<b.sta;}
int mis,goo,per,com,tmp;
......main函数内
	for(int i=1;i<=n;i++)if(!c[i].sta)c[i].sta=1,c[i].ju=c[i].t+60000;//如果未被判定，那就是miss，判定时间为下落时间+0.6s 
	sort(c+1,c+n+1,cmp);//根据判定时间排序
	for(int i=1;i<=n;i++){
		if(c[i].sta==1)com=max(com,tmp),mis++,tmp=0;
		else tmp++,c[i].sta==2?goo++:per++;//计算答案
	}
	cout<<per<<" "<<goo<<" "<<mis<<" "<<max(tmp,com)<<endl;

至此，本题被我们完美解决！

\sf{Code}

给出完整的代码：

#include<bits/stdc++.h>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void read(int &x){
	bool sign=0; char s=getchar(); x=0;
	while(!isdigit(s))sign|=s=='-',s=getchar();
	while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=getchar();
	x=sign?-x:x;
}
inline void read(double &x){
	bool sign=0; char s=getchar(); int a=0; x=0;
	while(!isdigit(s))sign|=s=='-',s=getchar();
	while(isdigit(s))a=(a<<1)+(a<<3)+s-'0',s=getchar();
	if(s=='.'){
		double tmp=1; s=getchar();
		while(isdigit(s))tmp/=10,x+=tmp*(s-'0'),s=getchar();
	}
	x+=a,x=sign?-x:x;
}
#define d val[hd[x]]//宏定义方便
const int N=1.2e5+5,inf=2e9+7;
struct key{
	int t,a,b,sta,ju;//sta是这个key的状态，ju是这个key被判定的时间
	bool operator < (const key &v) const {return t<v.t;}//按时间排序
}c[N];
struct click{
	int t,pos;
	bool operator < (const click &v) const {return t<v.t;}
}q[N];
bool cmp(key a,key b){return a.ju<b.ju||a.ju==b.ju&&a.sta<b.sta;}
int n,m,cnt,pos[N<<2];
int get(int x){return lower_bound(pos+1,pos+cnt+1,x)-pos;}//返回离散化后的值
int node,hd[N<<4],tl[N<<4],nxt[N<<7],val[N<<7];
void push(int x,int id){//链表添加
	if(!hd[x])hd[x]=tl[x]=++node;
	else nxt[tl[x]]=++node,tl[x]=node;
	val[node]=id;
}
void add(int l,int r,int ql,int qr,int x,int id){//添加key 
	if(ql<=l&&r<=qr){
		push(x,id);
		return;
	}
	int m=l+r>>1;
	if(ql<=m)add(l,m,ql,qr,x<<1,id);
	if(m<qr)add(m+1,r,ql,qr,x<<1|1,id);
}
void update(int x,int t){//将过期或已被判定的key弹出
	while(hd[x]){
		if(c[d].t+60000<=t){//过期
			if(!c[d].sta)c[d].ju=c[d].t+60000,c[d].sta=1;
			hd[x]=nxt[hd[x]];
		}
		else if(c[d].sta)hd[x]=nxt[hd[x]];//已被判定
		else break;//否则break 
	}
}
int tim(int x,int t){//求一下会判定的key的下落时间
	if(c[d].t-t>=100000)return inf;//如果还没到判定范围就返回inf（如果链表为空，因为前面c[0].t赋为inf了，所以也会返回inf） 
	else return c[d].t;
}
int query(int l,int r,int pos,int x,int t){
	update(x,t);
	if(l==r)return tim(x,t);//如果到底了就返回
	int m=l+r>>1;
	if(pos<=m)return min(tim(x,t),query(l,m,pos,x<<1,t));
	else return min(tim(x,t),query(m+1,r,pos,x<<1|1,t));//因为判定的是最低的key，所以取min
}
void modify(int l,int r,int pos,int x,int t,int T){
	while(c[d].t==t){//如果下落时间为本次key的判定下落时间t
		if(!c[d].sta){//如果没有被判定
			c[d].ju=T;//记录被判定的时间T（再次说明，请区分t和T）
			c[d].sta=abs(c[d].t-T)<20000?3:abs(c[d].t-T)<60000?2:1;//根据题目所给的条件进行判定
		}
		hd[x]=nxt[hd[x]];
	}
	if(l==r)return;
	int m=l+r>>1;
	if(pos<=m)modify(l,m,pos,x<<1,t,T);
	else modify(m+1,r,pos,x<<1|1,t,T);
}
int mis,goo,per,com,tmp;
int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++){
		double x,y,z; read(x),read(y),read(z);
		c[i]={x*1e5+0.5,y*1e5+0.5,z*1e5+0.5,0};
		pos[++cnt]=c[i].a,pos[++cnt]=c[i].b;
	}
	for(int i=1;i<=m;i++){
		double x,y; read(x),read(y);
		q[i]={x*1e5+0.5,y*1e5+0.5};
		pos[++cnt]=q[i].pos; 
	}
	sort(c+1,c+n+1),sort(q+1,q+m+1),c[0].t=inf;//c[0].t赋为inf，更方便
	sort(pos+1,pos+cnt+1),cnt=unique(pos+1,pos+cnt+1)-pos-1;//离散化
	for(int i=1;i<=n;i++)add(1,cnt,get(c[i].a),get(c[i].b),1,i);
	for(int i=1;i<=m;i++){
		int p=get(q[i].pos),t=query(1,cnt,p,1,q[i].t);
		if(t!=inf)modify(1,cnt,p,1,t,q[i].t);//如果有判定的key就判定
	}
	for(int i=1;i<=n;i++)if(!c[i].sta)c[i].sta=1,c[i].ju=c[i].t+60000;//如果未被判定，那就是miss，判定时间为下落时间+0.6s 
	sort(c+1,c+n+1,cmp);//根据判定时间排序
	for(int i=1;i<=n;i++){
		if(c[i].sta==1)com=max(com,tmp),mis++,tmp=0;
		else tmp++,c[i].sta==2?goo++:per++;//计算答案
	}
	cout<<per<<" "<<goo<<" "<<mis<<" "<<max(tmp,com)<<endl;
	return 0;
}

开了 $\sf{O2}$ 跑得飞快，不开 $\sf{O2}$ 可能会因为评测机波动 $\sf{TLE}$ （只是可能，因为还没背卡过，最长的测试点在 $\sf{900ms}$ 左右）

\sf{Ending}

如果你只对 $\rm{key}$ 的位置离散化，其实会快不少，但细节更多，有一些边界情况需要考虑。如果你想追求更快的解法，可以参考我的这份评测记录： $\sf{link}$ （快了大概 $25\%$ 左右）

其实当时打这场比赛的时候就想写正解，但是细节太多写自闭了。。。

今天无意间翻到这道题，仍然用了很长时间才将其 $\sf{AC}$ ，可见我是多么的菜。

码字不易，既然你都看到这儿了，就顺手点个赞呗 =w=

当然，如果你发现了本题解的笔误/学术上的错误，欢迎在评论区指出或者直接私信通知我，万分感谢！

再次感谢你认真地翻到了这里，拜拜 ~~

ID

4580

时间

1000ms

内存

125MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

【L&K R-03】音游大计算

信息

1 条题解

自动搬运

以下是正文

【L&K R-03】音游大计算

信息

还没有账户？

登录