题解 P3090 【[USACO13NOV]Empty Stalls G】
小柯
2020-07-27 09:16:22
题意:有 $n$ 头牛,每头牛有一个喜欢的位置 $like_i$ ,在为每头牛分配了 $like_i$ 以后第一个未被占用的位置(包括该位置),若不存在,则选择第一个未被占用的位置以后,第一个被剩下的位置。
分析:
若当前位置前有 $x$ 个位置未被占用,那么分两种情况:
>1.当前位置未被占用:则占用该位置。
>2.当前位置已被占用:则占用第 $x+1$ 个未被占用的位置,若不存在第 $x+1$ 个,则占用第一个未被占用的位置。
对于第一种情况,直接由数组维护每个位置的占用情况即可。
对于第二种情况,如果把所有位置看做一个序列,已被占用的为 $0$,未被占用的为 $1$,则问题可以转化:
>求 $x$ -> 求该序列的前缀和 $sum_x$。
>求第 $x+1$ 个未被占用的位置 -> 求第一个前缀和 $sum_i$ 为 $x+1$ 的位置 $i$。
很显然,这些操作就是单点修改,区间查询,查询排名,可以用权值树状数组、权值线段树、平衡树等数据结构维护。(可以用树状数组的话,当然不可能用其他的啊qwq,但是注意树状数组下标不支持 $0$,需要下标手动加一)
综上,时间复杂度为 $O(n$ $logn)$,~~勉强能卡过~~。
$code:$
```cpp
#include<iostream>
#include<cstdio>
#define maxn 3000005
#define lowbit(x) (x&-x)
using namespace std;
int n,k,cnt;
int t[maxn];
int lg[maxn];
int used[maxn];
int like[maxn];
long long x,y,a,b;
inline void add(int pos,int val){
for(;pos<=n;pos+=lowbit(pos))t[pos]+=val;
}
inline int sum(int pos){
int ans=0;
for(;pos;pos-=lowbit(pos))ans+=t[pos];
return ans;
}
inline int qry(int rank){
int ans=0,pos=0,nxt_pos;
for(int step=lg[n];~step;step--){
nxt_pos=pos+(1<<step);
if(nxt_pos<=n&&ans+t[nxt_pos]<rank)ans+=t[pos=nxt_pos];
}
return pos+1;
}
int main(){
scanf("%d%d",&n,&k);
for(int line=1;line<=k;line++){
scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
for(int i=1;i<=y;i++){
for(int j=1;j<=x;j++){
like[++cnt]=(a*i+b)%n;
}
}
}
//for(int i=1;i<=cnt;i++)printf("%d ",like[i]);printf("/n");
++n;
for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++)add(i,1);
for(int i=1;i<=cnt;i++){
++like[i];
if(!used[like[i]])x=like[i];
else if((x=qry(sum(like[i])+1))==n)x=qry(1);
//printf("%d ",x);
used[x]=1,add(x,-1);
}
//printf("\n");
printf("%d",qry(1)-1);
return 0;
}
```