bzoj 5368:[Pkusc 2018]リアルランキング線分ツリー+組合せ数

に言及
Cさんはある有名な試合の組織者で、この試合には全部でn人の選手が参加して、選手一人一人の成績は非負の整数で、1人の選手の順位を定義するのは、成績が彼の選手の数(彼自身を含む)より小さくないことです.例えば、333人の選手の成績がそれぞれ[1,2,2]であれば、彼らの順位はそれぞれ[3,2,2]です..神の視点を持つあなたはすべての選手の実力を知っているので、試験の前に一人一人の成績を正確に推定し、iii番目の選手の成績をAiとし、神の視点であるため、何の意外も起こらなければ、あなたの推定成績は選手の最終成績です.しかし、試合当日には耐えられない事故が発生した.(例えば宇宙人の攻撃を受けた)結果、一部の選手の成績が最終成績の2倍になった.神の視点を持つあなたでも、具体的にどの選手の成績が2倍になったのか分からない.唯一知っている情報は、このような選手がちょうどk人いることだ.今、不可抗事故を経て、i番目の選手に対して、どれだけの状況が満たされているかを計算する必要がある.彼の順位は変わっていない.答えが大きすぎる可能性があるので、998244353の型を取る値を出力するだけでいいです.
ぶんせき
議論すればいいでしょう.細かいことは、この数を取るたびに取らないことです.最後に私のやり方でこの数が0だと判断したとき、実は線分樹を使わなくてもいいと判断します.
コード#コード#

#include 
using namespace std;
typedef long long ll;
const ll N = 3000010;
const ll inf = 1e9;
const ll Mod = 998244353;
inline ll read()
{
  ll p=0; ll f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}
ll rt,tot = 0,lc[N],rc[N],c[N],a[N];
void link(ll &u,ll L,ll R,ll k)
{
  if(!u) u = ++tot;
  if(L==R){c[u] ++; return ;}
  ll mid=(L+R)>>1;
  if(k<=mid) link(lc[u],L,mid,k);
  else link(rc[u],mid+1,R,k);
  c[u] = c[lc[u]] + c[rc[u]];
}
ll qry(ll u,ll L,ll R,ll l,ll r)
{
  if(l>r) return 0;
  if(L==l && R==r) return c[u];
  ll mid=(L+R)>>1;
  if(r<=mid) return qry(lc[u],L,mid,l,r);
  else if(l>mid) return qry(rc[u],mid+1,R,l,r);
  else return qry(lc[u],L,mid,l,mid) + qry(rc[u],mid+1,R,mid+1,r);
}
ll inv[N],fac[N];
ll C(ll x,ll y){if(x<y || x<0 || y<0) return 0; return fac[x] * inv[y] % Mod * inv[x-y] % Mod;}
int main()
{
  ll n = read(); ll k = read();
  rt=tot=0; for(ll i=1;i<=n;i++) link(rt,0,inf,a[i] = read());
  fac[0] = 1; for(ll i=1;i<=n;i++) fac[i] = i;
  inv[0] = inv[1] = 1; for(ll i=2;i<=n;i++) inv[i] = (Mod - Mod/i) * inv[Mod % i] % Mod;
  for(ll i=1;i<=n;i++) fac[i] = fac[i-1] * fac[i] % Mod,inv[i] = inv[i-1] * inv[i] % Mod;
  for(ll i=1;i<=n;i++)
  {
    if(!a[i]){printf("%lld
",C(n,k)); continue;}
    ll s1 = qry(rt,0,inf,(a[i]+1)/2,a[i]-1)+1; s1 = n - s1;
    ll s2 = qry(rt,0,inf,a[i],min(inf,a[i]*2-1));
    printf("%lld
",(C(s1,k) + ((s2<=k) ? C(n-s2,k-s2) : 0))%Mod);
  }
  return 0;
}