T1

【问题描述】
大武在和它的机器玩猜数字，可是机器好像坏了……
具体来说，机器首先会随机生成一个 1…n 的数字 k ，紧接着机器会给大武 m 条指令，指令的格式有如下三种：
1. op x y ；这里 op=1 ，代表有 x≤k≤y
2. op x ；这里 op=2 ，代表有 x≤k≤n
3. op x ；这里 op=3 ，代表有 1≤k≤x
大武知道这台机器已经学会了说谎，所以它所描述的指令可能都是错误的，现在大武想知道机器错误的程度以便来制定修理它的方案。
所以大武想请你告诉它，当 k 取 1…n 这个范围内的值时，机器最多有多少条指令是错误的，而 k 又有多少种取值方式使得机器的错误指令数最多。
【输入格式】
第一行两个整数代表 n,m
接下来 m 行每行一条指令，指令格式见题面。
【输出格式】
输出共一行两个整数，分别代表机器最多的错误指令数，以及有多少种 k 的取值会使得机器的错误
指令数最多。
【样例输入】
9 5
1 3 6
2 7
1 2 3
3 2
1 5 8
【样例输出】
4 3
【样例说明】
最多的错误指令数为 4 。
使得错误指令数最多的取值有 3 种，分别是：
取值为 1 ，此时第 1, 2, 3, 5 条指令是错误的。
取值为 4 ，此时第 2, 3, 4, 5 条指令是错误的。
取值为 9 ，此时第 1, 3, 4, 5 条指令是错误的。
【数据范围】
1<=x<=y<=n<=10^6,1<=m<=2*10^5

T2

【问题描述】
大武参加了小武的派对。
大武面前有一个圆桌，圆桌边缘按顺序摆上了 n 个蛋糕（第一个蛋糕和第 n 个蛋糕相邻）。
每个蛋糕都有一个饱腹值和奶油含量。
大武不喜欢吃奶油，所以他想要在保证自己能吃饱（所吃蛋糕的饱腹度的和大于等于 s ）的情况下，所选择的蛋糕中奶油含量最大的那一个的奶油含量越低越好。大武一直都是个绅士。所以他选择的蛋糕应该是相邻的（也就是对应圆上的一段弧（也可以是整个圆））。
现在请你帮大武计算在能够吃饱的情况下，他吃到蛋糕中奶油含量最高的那一个最低会是多少？
【输入格式】
输入共三行。
第一行两个正整数 n,s。
接下来的一行n 个整数 a[i]代表第i个蛋糕的饱腹值。
接下来的一行n 个整数 b[i]代表第i个蛋糕的奶油含量。
【输出格式】
输出共一行代表答案。
特别的，若牛牛吃掉所有蛋糕都无法吃饱则输出 -1 。
【样例输入】
5 9
4 3 7 6 1
1 3 9 2 5
【样例输出】
5
【样例说明】
选择第 1, 2, 4, 5 个蛋糕：
饱腹值： 4+3+6+1=14>94+3+6+1=14>9
最大奶油含量： max{1,3,2,5}=5
所以输出 5 。
【数据范围】
n<=2*10^5,s<=10^9,1<=a[i],b[i]<=10^9

T3

发展采矿业当然首先得有矿井，大武花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井，但他似乎忘记考虑的矿井供电问题……
为了保证电力的供应，大武想到了两种办法：
在这一口矿井上建立一个发电站，费用为 v （发电站的输出功率可以供给任意多个矿井）。
将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 p 。
大武希望身为计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。
【输入格式】
第一行一个整数n ，表示矿井总数。
第 2-n+1行，每行一个整数，第 i个数表示在第 i口矿井上建立发电站的费用。
接下来为一个n*n 的矩阵 p，p[i][j]表示在第i 口矿井和第 j口矿井之间建立电网的费用（数据保证有 p[i][j]=p[j][i]，且 p[i][i]=0）。
【输出格式】
输出仅一个整数，表示让所有矿井获得充足电能的最小花费。
【样例输入】
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
【样例输出】
9
【样例解释】
可以选择在 4 号矿井建立发电站然后把所有矿井都不其建立电网，总花费是 3+2+2+2=9 。
【数据范围】
n<=300,0<=u[i],p[i][j]<=10^5