题解 P5819 【【L&K R-03】音游大计算】
Alex_Wei
·
·
题解
\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} 按点击时间排序，方便统计答案。
该部分的注意点：
```cpp
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}$ 就行）
线段树的建造：
```cpp
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}$ 弹出。
给出此部分的代码：
```cpp
#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}$），跳过此部分，否则可能会导致死循环。
```cpp
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}$ 排序即可。
此部分代码：
```cpp
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}$$
给出完整的代码：
```cpp
#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}$](https://www.luogu.com.cn/record/30906960)（快了大概 $25\%$ 左右）
其实当时打这场比赛的时候就想写正解，但是细节太多写自闭了。。。
今天无意间翻到这道题，仍然用了很长时间才将其 $\sf{AC}$，可见我是多么的菜。
码字不易，既然你都看到这儿了，就顺手点个赞呗 =w=
当然，如果你发现了本题解的笔误/学术上的错误，欢迎在评论区指出或者直接私信通知我，万分感谢！
再次感谢你认真地翻到了这里，拜拜 ~~