結果

問題 No.868 ハイパー部分和問題
ユーザー 已经死了
提出日時 2025-08-18 13:52:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 705 ms / 7,000 ms
コード長 1,168 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 90,544 KB
最終ジャッジ日時 2025-08-18 13:52:21
合計ジャッジ時間 15,174 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1<<20)
input=sys.stdin.readline
MI=lambda:map(int,input().split())
li=lambda:list(MI())
ii=lambda:int(input())

n,k=li()
a=li()
q=ii()

# --- 把点修改转成存在区间 (l,r,v) ---
cur_st=[0]*n
cur_val=a[:]
iv=[]
for t in range(q):
    x,v=li()
    x-=1
    iv.append((cur_st[x],t,cur_val[x]))
    cur_st[x]=t
    cur_val[x]=v
for i in range(n):
    iv.append((cur_st[i],q,cur_val[i]))

# --- 线段树挂桶 ---
seg=[[] for _ in range(4*max(1,q))]
def upd(i,l,r,ql,qr,v):
    if ql<=l and r<=qr:
        seg[i].append(v);return
    m=(l+r)//2
    if ql<m: upd(i*2,l,m,ql,qr,v)
    if qr>m: upd(i*2+1,m,r,ql,qr,v)

if q>0:
    for l,r,v in iv:
        if l<r and v<=k:  # v>k对答案无贡献，直接跳过
            upd(1,0,q,l,r,v)

# --- 分治 DFS：在节点吸收整段覆盖的值 ---
mask=(1<<(k+1))-1
ans=[0]*q
def dfs(i,l,r,bs):
    for v in seg[i]:
        bs=(bs|((bs<<v)&mask))
    if r-l==1:
        ans[l]=1 if (bs>>k)&1 else 0
        return
    m=(l+r)//2
    dfs(i*2,l,m,bs)
    dfs(i*2+1,m,r,bs)

if q>0:
    dfs(1,0,q,1)  # 初始只含和0
    sys.stdout.write(''.join('1\n' if x else '0\n' for x in ans))
0