[JOIGST 2024] 年轮蛋糕 2 题解

· · 题解

之前把这题搬进了模拟赛，直接把当时写的题解弄过来。

考虑到如果一个人提出过要求，那么在蛋糕切割之后他需要拿的部分就唯一确定了。如果一个人提出过多次要求，那么蛋糕的某些切割方法（即选择切口的方法）将会变得不合法。

设没有提出过要求的人有 x 个，有 y 种合法的切割方法，那么答案为 x!\cdot y。

使用 std::set 维护合法的切割方法：具体地，维护合法的切割方法（切口的编号 \bmod l 的值），每次如果一个人提出了一个新的要求，考虑同时满足这个要求和之前所有的要求的切割方法集合的交集（显然是一段区间）；同时还需考虑这个要求和其他人的要求形成的交集。把上述所有情况取交集即可。更多实现细节可以参照代码。

令 k,l,q 同阶，则时间复杂度为 O(k\log k)。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
static int p,f[200001];
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int k,l,q,c,r; cin>>k>>l>>p>>q,r=((c=k)*l);
  for(int i=f[0]=1;i<=k;i++)
    f[i]=f[i-1]*i%p;
  bool w=true;
  set<int> ps;
  for(int i=0;i<l;i++)
    ps.emplace(i);
  vector<int> id(k);
  vector<set<int> > s(k);
  set<pii> as;
  auto upd=[&](int a,int b){
    if(a<=b){
      while(!ps.empty()&&*ps.begin()<a)ps.erase(ps.begin());
      while(!ps.empty()&&*prev(ps.end())>b)ps.erase(prev(ps.end()));
    }
    else{
      auto it=ps.upper_bound(b);
      while(it!=ps.end()&&*it<a)it=ps.erase(it);
    }
  }; // 与 [a,b] 取交集
  while(q--){
    int x,y; cin>>x>>y,x--,y--,as.emplace(x,y);
    if(s[y].empty())c--,id[y]=x,s[y].emplace(0);
    else if((x-id[y]+r)%r<l||(id[y]-x+r)%r<l){
      if((x-id[y]+r)%r<l)s[y].emplace((x-id[y]+r)%r);
      else s[y].emplace(-(id[y]-x+r)%r);
      if(*prev(s[y].end())-*s[y].begin()>=l)w=false;
      else upd((*prev(s[y].end())+1+id[y]+l)%l,(*s[y].begin()+id[y]+l)%l);
    }
    else w=false;
    if(as.size()>1){
      auto p1=as.upper_bound(make_pair(x,2e9));
      if(p1==as.end())p1=as.begin();
      auto [x1,g1]=*p1;
      auto p2=as.lower_bound(make_pair(x,0));
      if(p2==as.begin())p2=as.end();
      auto [x2,g2]=*--p2;
      if(y!=g1&&x1!=x2&&g1==g2&&(x1-x2+r)%r<l)w=false;
      else{
        if(!s[g2].empty()&&(x-(*s[g2].begin()+id[g2])+r)%r<l)
          upd((*prev(s[g2].end())+1+id[g2]+l)%l,x%l);
        if(!s[g1].empty()&&(*prev(s[g1].end())+id[g1]-x+r)%r<l)
          upd((x+1)%l,(*s[g1].begin()+id[g1]+l)%l);
      }
    }
    if(w)cout<<f[c]*ps.size()%p<<'\n';
    else cout<<"0\n";
  }
  return 0;
}