bzoj#P4717. 改装
改装
题目描述
(reequip.pas/c/cpp/in/out) 【题目背景】 小Q最近喜欢上了一款游戏,名为《舰队connection》,在游戏中,小Q指挥强大的舰队南征北战,从而成为了一名 dalao。在游戏中,不仅船只能力很重要,搭配合适的装备更是如虎添翼。小Q潜心研究配装三十年,终于——把装 备凑齐了。 【题意描述】 小Q有n艘船,m件装备。为了简单起见,我们假定每艘船都只能携带一件装备,且可以携带任何一件装备。每艘船 和每件装备都有自己的能力值。船携带装备时,能力值为两者相乘。另外,小q还有可能对船或装备进行改修(强化 )。改修成功会让能力提升,失败则会让能力降低。由于最佳配置已经用了无数次了毫无挑战性,因此,小Q并不打 算直接使用最佳配置,而是使用相对弱一些的第k佳配置。具体来说,每次选择船只时,由于关卡限制,小Q需要在 编号为L到R的船只中选择一艘,并在编号为a和b之间的装备选择一架,组成出击用的船只。于是,小Q总共有(R-L+ 1)(b-a+1)种选择,小Q希望知道,所有这些选择中,第k大的能力值是多少。例如: 船只:5 3 7 装备:4 2 1 8 16 对于L=1,R=3,a=1,b=5,k=10的询问,将所有可能的能力值排序,分别为716=102,516=80,78=56,316=48,5 8=40,74=28,38=24,54=20,72=14,34=12,52=10,71=7,32=6,51=5,31=3,其中第10大的是12。 对于L=2,R=3,a=2,b=4,k=5的询问,将所有可能的能力值排序,分别为78=56,38=24,72=16,71=7,32=6,3 1=3,其中第5大的是6。假定小Q改修了第二艘船使其能力值成功增加至4,并改修了第5件装备但由于失败使得它 的能力值减小为9。现在,对于L=1,R=2,A=4,B=5,K=3的询问,所有可能的能力值分别为59=45,58=40,49=36, 48=32,其中第3大的是36。现在,你要编写一个程序回答这些问题。提示:由于游戏的特殊性,装备比船多得不 知道到哪里去了,另外,作为一个人类,小Q才不会在一秒钟之内问几百万个问题让你回答,他只会问几百个,而 且给你好几秒钟的时间回答。
输入格式
第一行两个数n,m,空格分隔,表示小Q的船的数量和装备的数量。 第二行n个数,空格分隔,表示小Q的船的能力值(按编号)。 第三行m个数,空格分隔,表示小Q的装备的能力值(按编号)。 第四行一个数q,表示小q的操作数量。 接下来q行,每行描述一个操作,操作要么为一个改修事件,要么为一个询问。 对于改修事件,该行4个数0,type,pos,val,type为0或1,0表示把pos号船改修成val的能力值 1表示把pos号装备改修成val的能力值。 对于询问操作,该行6个数1,L,R,a,b,k,空格分隔,表示一个询问。 n<=250,m<=100000,q<=100000,其中询问操作不会超过200。 对于100%的数据,1<=L<=R<=n,1<=a<=b<=m,1<=k<=(R-L+1)*(b-a+1) 任何时候船能力值为不超过2000的正整数,装备能力值为不超过1000000的正整数。
输出格式
对于每个询问操作,输出一行,包含一个数,表示询问的答案。
3 5
5 3 7
4 2 1 8 16
5
1 1 3 1 5 10
1 2 3 2 4 5
0 0 2 4
0 1 5 9
1 1 2 4 5 3
12
6
36
提示
没有写明提示
题目来源
没有写明来源