题解：P5819 【L&K R-03】音游大计算
Description
你需要实现一个音游判定，但是玩家是只会单指的奥托普雷先生。
话说什么粪谱物量 114514 啊？
Solution
敢开这道题的应该都能看出是线段树吧
首先把所有出现过的横坐标离散化，最终化为一个只有横坐标的判定线，有点像中二节奏的判定，有的键大，有的小，对于每个线段树的结点开一条链表，表示该区间点击时一定会被判定的按键编号。
链表代码：
int head[maxn<<6],tail[maxn<<6],chaintot;
int nxt[maxn<<7],uid[maxn<<7],pre[maxn<<7];
void push(int st,int u){
if(!head[st])head[st]=tail[st]=++chaintot;
else nxt[tail[st]]=++chaintot,pre[chaintot]=tail[st],tail[st]=chaintot;
uid[chaintot]=u;return;
}每次点击只会对可能产生判定效果的 key 中位置（纵向高度）最低（离屏幕顶端最远）的一个产生判定效果。
可是连 rks=12.22 的 yyw 都知道在 phigros 的 stasis 谱面中存在大量纵连，显然我们要先判定先落下的按键。
因此我们先对所有按键进行排序，按顺序插入即可。
开一个结构体排序，由于会爆精度，我们把每个时间映射成一个整数。
代码：
struct Key{int t;double aa,bb;int a,b;}key[maxn<<1];
for(int i=1;i<=n;++i){
cin>>dub>>key[i].aa>>key[i].bb;
key[i].t=dub*1e5+0.5;//映射
}
inline bool cmp(Key drag,Key flick){return drag.t<flick.t;}
sort(key+1,key+1+n,cmp);如果我先加入了所有按键再直接处理的话，会遇到一个问题，我们联想到 phigros 中山茶花的某张 AT 铺面，存在双押三押交替的情况，而这里的玩家是不会双押多押的，如图。
那么根据先判 miss 的规则，太麻烦了。
不妨定义事件有三种类型。
1.音符进入判定区域。定义为 insert 。
2.音符推出判定区域，即为自动 miss。定义为 miss。
3.玩家点击。定义为 tap。
对于 insert 事件，我们直接将音符压入线段树中。
对于 miss 事件，我们开一个布尔数组表示按键是否被判定过，直接修改布尔数组对应位置即可。
对于 tap 事件，我们根据点击位置遍历线段树对应位置，将有可能被判定的按键压入一个栈中，再利用先前定义下标越小，时间越小的性质，根据下标排序，处理栈中时间相同的前几项即可。
下面给出关于事件的处理代码。
音符进入判定区域。
void insert(int id,int nowl,int nowr,int tol,int tor,int UID){
if(tol<=nowl&&nowr<=tor){push(id,UID);return;}
if(tol>nowr||tor<nowl)return;
int mid=(nowl+nowr)>>1;
insert(id<<1 ,nowl , mid,tol,tor,UID);
insert(id<<1|1,mid+1,nowr,tol,tor,UID);
return;
}
if(now.op==1){
if(js[now.keyid])continue;
insert(1,1,tot,key[now.keyid].a,key[now.keyid].b,now.keyid);
cerr<<"insert\n";
}音符自动判定为 miss。
else if(now.op==2){
if(js[now.keyid])continue;
maxcombo=max(maxcombo,combo);
combo=0;js[now.keyid]=1;
miss++;
cerr<<"miss\n";
}将可能结算的音符压入栈中。
void update(int id,int nowl,int nowr,int place,int t){
if(nowr<place||nowl>place)return;
bool Vis=false;int first_t=0;
for(int i=head[id];i;i=nxt[i]){
if(!i)break;
if(js[uid[i]]){
nxt[pre[i]]=nxt[i];
pre[nxt[i]]=pre[i];
if(i==head[id])head[id]=nxt[i];
if(i==tail[id])tail[id]=pre[i];
continue;
}
if(Vis&&first_t!=key[uid[i]].t)break;
stk[++top]=uid[i];
first_t=key[uid[i]].t;
Vis=1;
if(i==tail[id])break;
}
if(nowl==nowr)return;
int mid=(nowl+nowr)/2;
update(id<<1 ,nowl , mid,place,t);
update(id<<1|1,mid+1,nowr,place,t);
return;
}按照 miss，good，perfect 的顺序结算。
else{
top=0;
update(1,1,tot,now.place,now.tl);
sort(stk+1,stk+1+top);
int stk2[maxn],top2=0;
for(int i=1;i<=top;++i){
if(key[stk[i]].t!=key[stk[1]].t)break;
stk2[++top2]=stk[i];
}
for(int i=1;i<=top2;++i){
if(js[stk2[i]])continue;
int delta=key[stk2[i]].t-now.tl;
if(delta>=60000||delta<=-60000){
maxcombo=max(maxcombo,combo);
combo=0;js[stk2[i]]=1;
miss++;
cerr<<"miss\n";
}
}
for(int i=1;i<=top2;++i){
if(js[stk2[i]])continue;
int delta=key[stk2[i]].t-now.tl;
if((delta>=20000&&delta<60000)||(delta<=-20000&&delta>-60000)){
cerr<<"good\n";
js[stk2[i]]=1;
combo++;
good++;
}
}
for(int i=1;i<=top2;++i){
if(js[stk2[i]])continue;
int delta=key[stk2[i]].t-now.tl;
if(-20000<delta&&delta<20000){
cerr<<"perfect\n";
combo++;
js[stk2[i]]=1;
perfect++;
}
}
}那么就只剩事件排序的问题了，如图。
考虑到按键进入判定区间与按键自动miss是开区间，我们在排序时若两个事件同时发生应遵循以下规则：
1.事件 miss 优先于事件 tap。
2.事件 tap 优先于事件 insert。
体现在排序中是这样的：
struct event{int op,keyid,place;int tl;};//op=1音符进入判定区间 op=2音符推出判定区间 op=3点击
queue<event>q;
event events[maxn<<3];int evecnt;
bool Cmp(event drag,event flick){
if(drag.tl==flick.tl){
if(drag.op<=2&&flick.op<=2)return 1;
if(drag.op==3&&flick.op==3)return 1;
if(drag.op==1&&flick.op==3)return 0;
if(drag.op==2&&flick.op==3)return 1;
if(drag.op==3&&flick.op==1)return 1;
if(drag.op==3&&flick.op==2)return 0;
}
return drag.tl<flick.tl;
}总代码如下：
#include<bits/stdc++.h>
#define maxn 114514+10
using namespace std;
int n,m,tot;double tong[maxn<<4];
bool js[maxn];double dub;
int combo,maxcombo,perfect,good,miss;
struct Key{int t;double aa,bb;int a,b;}key[maxn<<1];
struct Tap{int t;double xx;int x;}tap[maxn<<1];
inline bool cmp(Key drag,Key flick){return drag.t<flick.t;}
inline bool CMP(Tap drag,Tap flick){return drag.t<flick.t;}
int stk[maxn<<6],top;
int head[maxn<<6],tail[maxn<<6],chaintot;
int nxt[maxn<<7],uid[maxn<<7],pre[maxn<<7];
void push(int st,int u){
if(!head[st])head[st]=tail[st]=++chaintot;
else nxt[tail[st]]=++chaintot,pre[chaintot]=tail[st],tail[st]=chaintot;
uid[chaintot]=u;return;
}
void insert(int id,int nowl,int nowr,int tol,int tor,int UID){
if(tol<=nowl&&nowr<=tor){push(id,UID);return;}
if(tol>nowr||tor<nowl)return;
int mid=(nowl+nowr)>>1;
insert(id<<1 ,nowl , mid,tol,tor,UID);
insert(id<<1|1,mid+1,nowr,tol,tor,UID);
return;
}
void update(int id,int nowl,int nowr,int place,int t){
if(nowr<place||nowl>place)return;
bool Vis=false;int first_t=0;
for(int i=head[id];i;i=nxt[i]){
if(!i)break;
if(js[uid[i]]){
nxt[pre[i]]=nxt[i];
pre[nxt[i]]=pre[i];
if(i==head[id])head[id]=nxt[i];
if(i==tail[id])tail[id]=pre[i];
continue;
}
if(Vis&&first_t!=key[uid[i]].t)break;
stk[++top]=uid[i];
first_t=key[uid[i]].t;
Vis=1;
if(i==tail[id])break;
}
if(nowl==nowr)return;
int mid=(nowl+nowr)/2;
update(id<<1 ,nowl , mid,place,t);
update(id<<1|1,mid+1,nowr,place,t);
return;
}
struct event{int op,keyid,place;int tl;};//op=1音符进入判定区间 op=2音符推出判定区间 op=3点击
queue<event>q;
event events[maxn<<3];int evecnt;
bool Cmp(event drag,event flick){
if(drag.tl==flick.tl){
if(drag.op<=2&&flick.op<=2)return 1;
if(drag.op==3&&flick.op==3)return 1;
if(drag.op==1&&flick.op==3)return 0;
if(drag.op==2&&flick.op==3)return 1;
if(drag.op==3&&flick.op==1)return 1;
if(drag.op==3&&flick.op==2)return 0;
}
return drag.tl<flick.tl;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>dub>>key[i].aa>>key[i].bb;
key[i].t=dub*1e5+0.5;//映射
}
for(int i=1;i<=n;++i){
tong[++tot]=key[i].aa;
tong[++tot]=key[i].bb;
}
for(int i=1;i<=m;++i){
cin>>dub>>tap[i].xx;
tap[i].t=dub*1e5+0.5;
tong[++tot]=tap[i].xx;
}
sort(tong+1,tong+1+tot);tot=unique(tong+1,tong+1+tot)-(tong+1);
for(int i=1;i<=n;++i){
key[i].a=lower_bound(tong+1,tong+1+tot,key[i].aa)-(tong);
key[i].b=lower_bound(tong+1,tong+1+tot,key[i].bb)-(tong);
}
for(int i=1;i<=m;++i)tap[i].x=lower_bound(tong+1,tong+1+tot,tap[i].xx)-(tong);
//离散化
sort(key+1,key+1+n,cmp);
sort(tap+1,tap+1+m,CMP);
//排序
for(int i=1;i<=n;++i){
events[++evecnt]={1,i,114514,key[i].t-100000};
events[++evecnt]={2,i,114514,key[i].t+60000};
}
cerr<<"track completed\n";
//导入音符进入事件
for(int i=1;i<=m;++i)events[++evecnt]={3,114514,tap[i].x,tap[i].t};
cerr<<"player completed\n";
//导入点击时间
sort(events+1,events+1+evecnt,Cmp);
for(int i=1;i<=evecnt;++i)q.push(events[i]);
//排序事件并压入队列
//计算
while(q.size()){
event now=q.front();q.pop();
if(now.op==1){
if(js[now.keyid])continue;
insert(1,1,tot,key[now.keyid].a,key[now.keyid].b,now.keyid);
cerr<<"insert\n";
}
else if(now.op==2){
if(js[now.keyid])continue;
maxcombo=max(maxcombo,combo);
combo=0;js[now.keyid]=1;
miss++;
cerr<<"miss\n";
}
else{
top=0;
update(1,1,tot,now.place,now.tl);
sort(stk+1,stk+1+top);
int stk2[maxn],top2=0;
for(int i=1;i<=top;++i){
if(key[stk[i]].t!=key[stk[1]].t)break;
stk2[++top2]=stk[i];
}
for(int i=1;i<=top2;++i){
if(js[stk2[i]])continue;
int delta=key[stk2[i]].t-now.tl;
if(delta>=60000||delta<=-60000){
maxcombo=max(maxcombo,combo);
combo=0;js[stk2[i]]=1;
miss++;
cerr<<"miss\n";
}
}
for(int i=1;i<=top2;++i){
if(js[stk2[i]])continue;
int delta=key[stk2[i]].t-now.tl;
if((delta>=20000&&delta<60000)||(delta<=-20000&&delta>-60000)){
cerr<<"good\n";
js[stk2[i]]=1;
combo++;
good++;
}
}
for(int i=1;i<=top2;++i){
if(js[stk2[i]])continue;
int delta=key[stk2[i]].t-now.tl;
if(-20000<delta&&delta<20000){
cerr<<"perfect\n";
combo++;
js[stk2[i]]=1;
perfect++;
}
}
}
}
maxcombo=max(maxcombo,combo);
combo=0;
cout<<perfect<<" "<<good<<" "<<miss<<" "<<maxcombo;
if(perfect==maxcombo&&(good==0&&miss==0))cerr<<"All Perfect\n";
else if(maxcombo==n)cerr<<"Full Combo\n";
return 0;
}