結果

問題 No.2327 Inversion Sum
ユーザー とりゐとりゐ
提出日時 2023-05-28 14:03:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 387 ms / 2,000 ms
コード長 2,926 bytes
コンパイル時間 1,002 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 85,376 KB
最終ジャッジ日時 2024-12-26 23:11:22
合計ジャッジ時間 7,256 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segtree():
  def __init__(self,init,func,ide):
    self.n=len(init)
    self.func=func
    self.ide=ide
    self.size=1<<(self.n-1).bit_length()
    self.tree=[self.ide for i in range(2*self.size)]
    for i in range(self.n):
      self.tree[self.size+i]=init[i]
    for i in range(self.size-1,0,-1):
      self.tree[i]=self.func(self.tree[2*i], self.tree[2*i|1])
  
  def update(self,k,x):
    k+=self.size
    self.tree[k]=x
    k>>=1
    while k:
      self.tree[k]=self.func(self.tree[2*k],self.tree[k*2|1])
      k>>=1
  
  def get(self,i):
    return self.tree[i+self.size]
  
  def query(self,l,r):
    l+=self.size
    r+=self.size
    l_res=self.ide
    r_res=self.ide
    while l<r:
      if l&1:
        l_res=self.func(l_res,self.tree[l])
        l+=1
      if r&1:
        r-=1
        r_res=self.func(self.tree[r],r_res)
      l>>=1
      r>>=1
    return self.func(l_res,r_res)

  def max_right(self,l,f):
    assert 0<=l<=self.n 
    assert f(self.ide)
    if l==self.n:
      return self.n
    l+=self.size
    res=self.ide
    while True:
      while l&1==0:
        l>>=1
      if not f(self.func(res,self.tree[l])):
        while l<self.size:
          l*=2
          if f(self.func(res,self.tree[l])):
            res=self.func(res,self.tree[l])
            l+=1
        return l-self.size
      res=self.func(res,self.tree[l])
      l+=1
      if l&(-l)==l:
        break
    return self.n
  
  def min_left(self,r,f):
    assert 0<=r<=self.n
    assert f(self.ide)
    if r==0:
      return 0
    r+=self.size
    res=self.ide
    while True:
      r-=1
      while r>1 and r&1:
        r>>=1
      if not f(self.func(self.tree[r],res)):
        while r<self.size:
          r=2*r+1     
          if f(self.func(self.tree[r],res)):
            res=self.func(self.tree[r],res)
            r-=1
        return r+1-self.size
      res=self.func(self.tree[r],res)
      if r&(-r)==r:
        break
    return 0
    
  def __getitem__(self,i):
    return self.get(i)
  
  def __setitem__(self,key,val):
    self.update(key,val)

  def __iter__(self):
    for i in range(self.n):
      yield self.tree[i+self.size]
          
  def __str__(self):
    return str(list(self))



n,m=map(int,input().split())
mst=[-1]*n
use=[1]*n
for _ in range(m):
  p,k=map(int,input().split())
  mst[k-1]=p-1
  use[p-1]=0

free=[0]*n
for i in range(n):
  if i>=1:
    free[i]=free[i-1]
  if mst[i]==-1:
    free[i]+=1

mod=998244353
rem=segtree(use,lambda x,y:x+y,0)
seg=segtree([0]*n,lambda x,y:x+y,0)
ans1=0
ans2=0
for i in range(n):
  if mst[i]!=-1:
    ans1+=seg.query(mst[i],n)
    seg.update(mst[i],1)
    L=rem.query(0,mst[i])
    R=rem.query(mst[i],n)
    ans2+=free[i]*(R)%mod*pow(L+R,mod-2,mod)%mod
    ans2+=(L+R-free[i])*L%mod*pow(L+R,mod-2,mod)%mod
    ans2%=mod

ans3=free[-1]*(free[-1]-1)%mod*pow(4,mod-2,mod)%mod

ans=ans1+ans2+ans3
ans%=mod
for i in range(1,free[-1]+1):
  ans*=i
  ans%=mod

print(ans)
0