#P13763. [2019年备战北大冬令营]举重

    ID: 12965 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-FHQ Treap 分裂合并区间翻转离散化完全背包普通生成函数容斥原理全子集枚举零贡献剪枝高精度加法高精度减法

[2019年备战北大冬令营]举重

题目描述

有一排 nn 个铁饼,每个铁饼有一个正整数重量。按顺序处理 QQ 次操作。

  • 1 x y:把第 xx 个铁饼的重量改为 yy。
  • 2 L R:将第 LL 个到第 RR 个铁饼的顺序反转。
  • 3 L R W:询问能否从第 LL 个到第 RR 个铁饼中选出一些,使它们的总重量恰好为 WW。每个铁饼最多选择一次。

所有时刻出现过的铁饼重量种类合计不超过 kk,包含初始重量以及修改操作指定的重量。

输入格式

第一行三个整数 n,Q,kn,Q,k。第二行 nn 个正整数,依次表示初始重量。接下来 QQ 行,每行给出一次操作,格式见题目描述。

输出格式

每次操作 3 输出一行。若可以拼出目标重量,输出 Yes,否则输出 No。

样例

原样例数据

数据范围

所有测试点满足 n,Q,W≤105n,Q,W\le10^5,k≤10k\le10。

子任务 分值 额外限制
1 30 n,Q,W≤1000n,Q,W\le1000
2 20 k=1k=1
3 操作 3 至多 500500 次
4 30 无

原 PDF 题面