結果
問題 |
No.868 ハイパー部分和問題
|
ユーザー |
|
提出日時 | 2025-08-17 23:51:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 822 ms / 7,000 ms |
コード長 | 4,192 bytes |
コンパイル時間 | 389 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 111,584 KB |
最終ジャッジ日時 | 2025-08-17 23:52:19 |
合計ジャッジ時間 | 19,085 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
import os,sys,random,threading from random import randint,choice,shuffle from copy import deepcopy from io import BytesIO,IOBase from types import GeneratorType from functools import lru_cache,reduce from bisect import bisect_left,bisect_right from collections import Counter,defaultdict,deque from itertools import accumulate,combinations,permutations from heapq import heapify,heappop,heappush from typing import Generic,Iterable,Iterator,TypeVar,Union,List from string import ascii_lowercase,ascii_uppercase,digits from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf from decimal import Decimal,getcontext from sys import stdin, stdout, setrecursionlimit input = lambda: sys.stdin.readline().rstrip("\r\n") MI = lambda :map(int,input().split()) li = lambda :list(MI()) ii = lambda :int(input()) mod = int(1e9 + 7) inf = 1<<60 py = lambda :print("YES") pn = lambda :print("NO") # ----------------------------- # 读入:一次性读完并切成整数 # 输入格式与原题一致: # n k # A1 ... An # q # (x1 v1) # (x2 v2) # ... # (xq vq) # ----------------------------- n,k=li() a=li() q=ii() # ----------------------------------------------------------- # 把“点修改”转成“时间区间”: # 对每个位置 i 维护当前值 val 在 [st, ed) 这个时间区间内“始终存在”。 # 初始 st=0、ed=q;有修改就把旧值那段区间 [st, now) 记录下来, # 然后从 now 开始把该位置的值改成新值(新的 st=now,ed 仍是 q)。 # 最终再把所有“未闭合”的区间 [st, q) 补上。 # 区间三元组形如:(l, r, v) # ----------------------------------------------------------- cur_st = [0] * n # 每个位置当前值的生效起点 cur_val = a[:] # 每个位置当前值 intervals = [] # 所有值的“存在区间” for t in range(q): x,v=li() x-=1 # 旧值在 [cur_st[x], t) 这一段有效,先收集为一个区间 intervals.append((cur_st[x], t, cur_val[x])) # 从 t 开始生效的新值 cur_st[x] = t cur_val[x] = v # 把还“开着”的区间收尾(直到 q) for i in range(n): intervals.append((cur_st[i], q, cur_val[i])) # ----------------------------------------------------------- # 时间分治(线段树分治)的 DFS # 节点负责时间区间 [st, ed)。 # items: 与该区间“有关”的所有 (l, r, v) 区间(可能覆盖、也可能部分相交) # bs: 当前可达子集和的位集合(Python int),bs 的第 s 位为 1 表示能凑出和 s # 规则: # - 若 (l,r) 与 [st,ed) 不相交:忽略 # - 若 完全覆盖 [st,ed):把 v 合并到 bs(bs |= (bs << v)) # - 若 部分相交:继续下传给子节点 # 叶子 [t, t+1) 对应“第 t 次修改之后”的时刻,输出答案 bs[k] # ----------------------------------------------------------- mask = (1 << (k + 1)) - 1 # 只保留 0..k 的位,避免无意义的高位增长 ans = [0] * q # 每次修改后的回答(0/1) def dc(st: int, ed: int, items, bs: int): # 先吸收在整个 [st,ed) 内“始终存在”的值 pass_down = [] # 与 [st,ed) 部分交叠、需要继续下传的区间 for l, r, v in items: if r <= st or ed <= l: # 与本节点时间区间无交集 continue if l <= st and ed <= r: # 在本节点整个时间段内始终存在,直接合入 bitset if v <= k: # v>k 对答案无贡献,可跳过 bs = bs | ((bs << v) & mask) else: # 只在子时间段里才完整/部分存在,留给子节点处理 pass_down.append((l, r, v)) if ed - st == 1: # 叶子:对应第 st 次修改后的时刻 ans[st] = 1 if (bs >> k) & 1 else 0 return mid = (st + ed) // 2 # 注意:Python int 不可变,传参相当于值拷贝;左右子树互不影响 dc(st, mid, pass_down, bs) dc(mid, ed, pass_down, bs) # 初始:未修改前可达集合只有和 0(空集) initial_bs = 1 # 二进制 ...0001 dc(0, q, intervals, initial_bs) # 输出 out = ''.join('1\n' if x else '0\n' for x in ans) sys.stdout.write(out)