题目大意
有一个长度为 (L) 的环 ((2 le L le 10^9)),
环上有 (n) 个人, (m) 个出口 ((1 le n,m le 2 imes 10^5)).
规定第一个出口的位置为 (0), 并将 "到第一个出口的距离" 定义为 "从顺时针方向走到第一个路口所走的路程".
每个人有两个属性 (t_i, x_i), 分别表示这个人的前进方向 ((0) 为逆时针, (1) 为顺时针), 以及这个人到第一个出口的距离.
每个出口有两个属性 (lim_i, a_i), 分别表示这个出口的人数限制 (即最多能从这个出口出去多少人), 以及这个出口到第一个出口的距离.
在每个单位时间内, 所有人都会朝着他们的前进方向移动一个单位距离,
若有一个人 (i) 走到了一个人数没有达到上限的出口 (j), 他就会从这个出口出去, 则 (k[i]=j).
特别地, 若有两个人同时到达了一个只能出去一个人的出口, 则编号较小的那个人可以出去.
最终输出 (i imes k[i]) 的异或和, 即
(注: (oplus) 为异或符号)
思路
(O(n^2)) 52pts
首先, 最暴力的思路就是大模拟, 每次把每一个人往他的移动方向移一格, 然后从小到大扫一遍, 看哪个人可以出去.
可以发现, 我们其实只需要找到离他下一个出口最近的那个人, 记他离出口的距离为 (mind), 把所有人往前移动 (mind) 个单位距离就行了.
当然, 有可能出现这个人到了出口后, 发现出口已经被填满了, 那么我们就需要再去找他的下一个出口, 而这是一个最劣能达到 (O(n)) 的操作, 这样的话复杂度就有可能退化到 (O(n^3)).
所以, 我们需要用(双向的)并查集优化一下这个过程, 总复杂度为 (O(alpha n^3)).
但还要注意的是, 不是每一次都能使得至少有一个人出去, 因为当前离出口最近的那个人他指向的出口已经被填满了, 所以复杂度应该是 (O(玄学 imes alpha n^3))
代码在下面.
(O(n log n)) 100pts
稍微思考一下, 我们可以发现, 并不需要维护每一个人的位置. 因为一个人出去后, 其他人到达每一个出口的相对时间并没有改变, 每次我们只需要取 到下一个出口最近的人, 然后把它移到出口即可.
找 距离最小的人 的操作可以在线段树上二分解决, 那我们再考虑把一个人从出口移出去后需要进行的操作.
如果这个出口没有满, 则不需要进行操作, 下一次直接查找最小值即可.
如果这个出口满了, 那么我们需要修改 原来要从这个出口出去的人离它下一个出口的位置,
可以把这些人分为 在这个出口左边的 和 在这个出口右边的.
对于左边的人, 把他们的目标转移到该出口右边第一个没有满的出口,
对于右边的人, 把他们的目标转移到该出口左边第一个没有满的出口,
我们考虑把所有人排序, 往逆时针方向走的排在左边, 往顺时针方向走的排在右边, 这两边再分别按他们的位置排序.
进行上述操作后, 可以发现,
在一个出口左边 且 要从这个出口出去的人 是一个连续的区间,
在一个出口右边 且 要从这个出口出去的人 也是一个连续的区间,
所以, 我们可以在线段树上区间修改这些人到下一个出口的距离.
至于查找两边 第一个没有满的出口, 可以用并查集解决.
分析一下复杂度: 每次都会让一个人从出口出去, 所以最多循环 (n) 次, 每次要查找最小值和区间修改, 还要在并查集中查找下一个出口,
所以总复杂度为 (O(nlog n alpha))
还有一点要注意的是, 当我们按上述策略排好序后, 每个人的新的编号和原来是不一样的,
所以我们需要在线段树上建一个 num 数组, 表示 以 (k) 为根节点的子树中 距离下一个出口最近的人的最小编号, 以便在线段树上二分查找
代码
(O(n^2)) 52pts
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;
const int inf=0x3f3f3f3f;
int n,m,L,d[N],nxt[N],le[N],ri[N],ans,a[N],x[N],minx=inf,nm,nn,lim[N];
bool t[N],gon[N];
int exi[N];
int dis(int i,int j){
if(!j) return inf;
int di=abs(x[i]-a[j]);
if((a[j]>x[i]&&t[i])||(a[j]<x[i]&&!t[i])) di=L+1-di;
return di;
}
int fl(int x){ return le[x]==x ?x :le[x]=fl(le[x]); }
int fr(int x){ return ri[x]==x ?x :ri[x]=fr(ri[x]); }
int main(){
\freopen("walk.in","r",stdin);
\freopen("walk.out","w",stdout);
cin>>n>>m>>L;
for(int i=2;i<=m;i++){
scanf("%d",&a[i]);
le[i]=ri[i]=i;
}
le[1]=ri[1]=1;
for(int i=1;i<=m;i++) scanf("%d",&lim[i]);
for(int i=1;i<=n;i++){
scanf("%d%d",&t[i],&x[i]);
for(int j=1;j<=m;j++)
if(dis(i,j)<dis(i,nxt[i])) nxt[i]=j;
minx=min(minx,dis(i,nxt[i]));
}
while(nm<m&&nn<n){
int mind=minx; minx=inf;
for(int i=1;i<=n;i++){
if(gon[i]) continue;
if(t[i]) x[i]-=mind;
else x[i]+=mind;
if(x[i]<0) x[i]+=L+1;
else if(x[i]>L) x[i]-=L+1;
if(x[i]==a[nxt[i]]){
if(!lim[nxt[i]]){
int tmp=0;
while(!lim[nxt[i]]){
if(t[i]){ le[tmp]=nxt[i]; nxt[i]=fl(nxt[i])-1; }
else{ ri[tmp]=nxt[i]; nxt[i]=fr(nxt[i])+1; }
if(!nxt[i]) nxt[i]=m;
if(nxt[i]>m) nxt[i]=1;
tmp=nxt[i];
}
}
else{
lim[nxt[i]]--;
if(!lim[nxt[i]]) nm++;
gon[i]=1; nn++;
ans^=i*nxt[i];
exi[i]=nxt[i];
}
}
if(!gon[i]) minx=min(minx,dis(i,nxt[i]));
}
}
printf("%d
",ans);
//for(int i=1;i<=n;i++) printf("%d ",exi[i]); putchar('
');
return 0;
}
(O(n log n)) 100pts
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
const int inf=0x3f3f3f3f;
int n,m,L;
int a[N],lim[N],t[N],x[N],id[N],ll[N],lr[N],rl[N],rr[N],le[N],ri[N],minx[4*N],tag[4*N],divd,d[N],nxt[4*N],dye[4*N],num[4*N],bel[N];
int seq[N],pac[N][2],nn,nm;
long long ans;
bool rule(int i,int j){
if(!(pac[i][0]^pac[j][0])) return pac[i][1]<pac[j][1];
else return pac[i][0]<pac[j][0];
}
int dis(int i,int j,int ty){
if((!ty&&i<j)||(ty&&i>j)) return abs(a[i]-a[j]);
else if(!ty) return a[j]+L-a[i]+1;
else return a[i]+L-a[j]+1;
}
int fl(int x){ return le[x]==x ?x :le[x]=fl(le[x]); }
int fr(int x){ return ri[x]==x ?x :ri[x]=fr(ri[x]); }
void read(){
cin>>n>>m>>L;
for(int i=2;i<=m;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
scanf("%d",&lim[i]);
le[i]=ri[i]=i;
}
for(int i=1;i<=n;i++){
scanf("%d%d",&pac[i][0],&pac[i][1]);
if(!pac[i][0]) divd++;
seq[i]=i;
}
sort(seq+1,seq+1+n,rule);
for(int i=1;i<=n;i++){
id[i]=seq[i];
t[i]=pac[id[i]][0];
x[i]=pac[id[i]][1];
}
}
void pre(){
int t1=divd,t2=1;
while(t1&&x[t1]>a[m]){ d[t1]=L-x[t1]+1; bel[t1]=1; t1--; }
ll[1]=t1+1; t1=1;
if(ll[1]>divd) ll[1]=0;
while(t2<=m){
while(t1<=divd&&x[t1]<=a[t2]){ d[t1]=a[t2]-x[t1]; bel[t1]=t2; t1++; }
lr[t2]=t1-1;
if(t2!=1) ll[t2]=lr[t2-1]+1;
t2++;
}
if(!lr[1]) lr[1]= ll[1] ?divd :0 ;
else if(!ll[1]) ll[1]=1;
t1=n; t2=m;
rr[m]=n;
while(t2){
while(t1>divd&&x[t1]>=a[t2]){ d[t1]=x[t1]-a[t2]; bel[t1]=t2; t1--; }
rl[t2]=t1+1;
if(t2!=m) rr[t2]=rl[t2+1]-1;
t2--;
}
for(int i=1;i<=m;i++){
if(i!=1&&ll[i]>lr[i]) ll[i]=lr[i]=0;
if(rl[i]>rr[i]) rl[i]=rr[i]=0;
}
}
void rfs(int k){
int tmp=minx[k<<1]-minx[k<<1|1];
if(tmp<0){ minx[k]=minx[k<<1]; num[k]=num[k<<1]; }
else if(tmp>0){ minx[k]=minx[k<<1|1]; num[k]=num[k<<1|1]; }
else{ minx[k]=minx[k<<1]; num[k]=min(num[k<<1],num[k<<1|1]); }
}
void build(int k,int l,int r){
if(l==r){ minx[k]=d[l]; num[k]=id[l]; nxt[k]=bel[l]; return; }
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
rfs(k);
}
void upd(int k,int w,int v){
minx[k]+=w; tag[k]+=w;
if(v) nxt[k]=dye[k]=v;
}
void psd(int k){
upd(k<<1,tag[k],dye[k]);
upd(k<<1|1,tag[k],dye[k]);
tag[k]=dye[k]=0;
}
int query(int k,int l,int r,int x,int y,int id){
if(l>=x&&r<=y) return id ?minx[k] :nxt[k];
psd(k);
int mid=(l+r)>>1,t1=inf,t2=inf;
if(x<=mid) t1=query(k<<1,l,mid,x,y,id);
if(y>mid) t2=query(k<<1|1,mid+1,r,x,y,id);
return min(t1,t2);
}
void modify(int k,int l,int r,int x,int y,int w,int v){
if(!x||!y) return;
if(l>=x&&r<=y){ upd(k,w,v); return; }
psd(k);
int mid=(l+r)>>1;
if(x<=mid) modify(k<<1,l,mid,x,y,w,v);
if(y>mid) modify(k<<1|1,mid+1,r,x,y,w,v);
rfs(k);
}
void recon(int k){
if(nm==m) return;
if(ll[k]){
int t1=k,t2=0;
do{
ri[t2]=t1;
t2=fr(t1);
t1=t2+1;
if(t1>m) t1=1;
}while(!lim[t1]);
if(!ll[t1]){ ll[t1]=ll[k]; lr[t1]=lr[k]; }
else ll[t1]=ll[k];
if(ll[k]<=lr[k]) modify(1,1,n,ll[k],lr[k],dis(k,t1,0),t1);
else{
modify(1,1,n,ll[k],divd,dis(k,t1,0),t1);
modify(1,1,n,1,lr[k],dis(k,t1,0),t1);
}
}
if(rl[k]){
int t1=k,t2=0;
do{
le[t2]=t1;
t2=fl(t1);
t1=t2-1;
if(!t1) t1=m;
}while(!lim[t1]);
if(!rl[t1]){ rl[t1]=rl[k]; rr[t1]=rr[k]; }
else rr[t1]=rr[k];
if(rl[k]<=rr[k]) modify(1,1,n,rl[k],rr[k],dis(k,t1,1),t1);
else{
modify(1,1,n,rl[k],n,dis(k,t1,1),t1);
modify(1,1,n,divd+1,rr[k],dis(k,t1,1),t1);
}
}
}
void find(int k,int l,int r){
if(l==r){
ans^=(long long)id[l]*nxt[k];
nn++;
modify(1,1,n,l,l,inf,nxt[k]);
lim[nxt[k]]--;
if(!lim[nxt[k]]){ nm++; recon(nxt[k]); }
return;
}
psd(k);
int mid=(l+r)>>1,t1=minx[k<<1]-minx[k<<1|1],t2=num[k<<1]-num[k<<1|1];
if(t1<0||(t1==0&&t2<0)) find(k<<1,l,mid);
else if(t1>0||(t1==0&&t2>0)) find(k<<1|1,mid+1,r);
}
int main(){
//freopen("walk.in","r",stdin);
//freopen("x.out","w",stdout);
read();
pre();
build(1,1,n);
while(nn<n&&nm<m) find(1,1,n);
printf("%lld
",ans);
return 0;
}