**优惠

时间限制: 3000MS

内存限制: 589824KB

题目描述:

现在给你一张优重券。优重券上有两个正整数LLL和RRR。

该优重券的使用规则是:

• 你可以任意选取一个位于 [L,R][L, R][L,R] 之间的正整数(不妨令其为xxx) ,抵扣xxx和xxx各个数位上的数字之和的乘积的金额。

比如当你选择数字69时，你可以抵扣的金额为
69∗(6+9)=103569*(6+ 9)= 103569∗(6+9)=1035

现在询问你最大可以利用手中这张优重券抵扣多少金额?

输入描述

一行， 给出两个整数L R以空格隔开，代表手中优惠券上的数。
1≤L≤R≤1e51≤L≤R≤1e51≤L≤R≤1e5

输出描述

输出行，代表最大优重金额。

样例输入
36

样例输出
36

提示

样例解释1
选取数字为333的折扣金额是3∗3=93*3=93∗3=9,数字为444的折扣金额是4∗4=164*4=164∗4=16,数字为555的
折扣金额是5∗5=255*5=255∗5=25,数字为666的折扣金额是6∗6=366*6=366∗6=36,故最大折扣金额为363636.

输入样例2
11 31
输出样例2
319

样例解释2
选取数字为292929的折扣金额是29∗(2+9)=31929 * (2+9)=31929∗(2+9)=319,可以证明这是手上优惠金额最大的一张优惠券。

---

static int miniTask(int input) {int out = 0;int t = input;while (t > 0) {out += t % 10;t /= 10;}out = out * input;return out;}static int findMax(int L, int R, int step) {int out = 0;if (step == 1) {for (int i = L; i < R; i++) {out = Math.max(miniTask(i), out);}} else {int left = (L / step + 1) * step - 1;for (; left <= R; left += step) {out = Math.max(out, miniTask(left));}left -= step;out = Math.max(out, findMax(left, R, step / 10));}return out;}static int task1() {Scanner scanner = new Scanner(System.in);int L = scanner.nextInt();int R = scanner.nextInt();int out = Math.max(miniTask(L), miniTask(R));int mark = 1;int dis = R - L;if (dis < 10) {out = Math.max(out, findMax(L, R, mark));} else {while (dis >= 10) {mark *= 10;dis /= 10;}out = Math.max(out, findMax(L, R, mark));}return out;}

---

---

玩具士兵

时间限制：3000MS
内存限制：589824KB

题目描述：

小明买了一些玩具士兵，他邀请小红一起玩。他总共有n个士兵，刚开始时，这nnn个士兵被排成一列，第i个士兵的战斗力为hjh_jhj​。然后小明和小红开始给它们排序。

二人总共进行了mmm次操作。小明的每次操作会选择一个数k，将前kkk个士兵按战斗力从小到大排序。

小红的每次操作会选择一个数kkk，将前kkk个士兵按战斗力从大到小排序。

请问所有操作结束后从前往后每个士兵的战斗力是多少？

输入描述

第一行有两个整数n、mn、mn、m（1≤nm≤2×1051≤nm≤2×10^51≤nm≤2×105），分别代表士兵的数量与操作次数。第二行有n个整数h1，h2，……，hnh_1，h_2，……，h_nh1​，h2​，……，hn​（−109≤hj<109-10^9≤h_j<10^9−109≤hj​<109），代表初始状态下从前往后各个士兵的战斗力。

接下来mmm行按顺序给出所有操作，每行有两个整数t、kt、kt、k（1≤t≤2，1≤k≤n1≤t≤2，1≤k≤n1≤t≤2，1≤k≤n），t=1代表是小明的操作，否则是小红的操作，代表是小明的操作，否则是小红的操作，代表是小明的操作，否则是小红的操作，k代表对前代表对前代表对前k$个士兵进行排序。

输出描述

输出nnn个整数，代表所有操作结束后从前往后每个士兵的战斗力。

样例输入
4 2
1 2 4 3
2 3
1 2

样例输出
2 4 1 3

---

思路：如果后一个操作的k大于之前的任何一个操作，则之前的任何一个操作不会影响最终的结果

#输入测试用例

n,m = 4,2tgt = [1,2,4,3,9,8,0]ops = [[1,5],[1,7],[2,2],[2,3],[1,2]]

从后向前搜索所有操作，使用curmaxcur_maxcurm​ax记录当前最大的kkk

cur_max = [ops[-1]]

#从后向前，找到对最终结果能产生影响的操作

ops.reverse()for op in ops:# 如果该操作大于“当前最大的k”，则该记录能对最终结果造成影响if cur_max[-1][1]<op[1]:cur_max.append(op)cur_max.reverse()

#依据curmaxcur_maxcurm​ax记录的操作，对玩具士兵进行操作

for op in cur_max:temp = tgt[:op[1]]temp.sort(reverse=(op[0]!=1))tgt[:op[1]]=tempprint(tgt)