HDU 6047 Maximum Sequence

hdu6047多校2-1003

这个问题，解法很多，线段树，优先队列，还有离线预处理A数组。
下面这份代码就是离线预处理A数组做的，复杂度是O（n）。
线段树和优先队列都是在线处理。

不想画图说明了，看不看得懂看缘分吧
这个题其实读完题后，需要处理的问题，就只有三个问题
1，处理1~~n区间上的最大值
2，处理B数组的区间限制
3，处理新增区间的最大值
其中线段树和优先队列都是把1--n区间和新增区间的最大值合在一起弄的
线段树自带区间处理优势，优先队列需要处理一下B数组，稍微有点麻烦，
所以优先队列的做法，其实很暴力，没有利用区间和最大值的联系，而是分开来暴力处理。但是时间复杂度还行，也比较好想，按贪心的思路很容易就能想到
优先队列，暴力神器
然后吃了个午饭，然后我忘了
然后我想想
然后我贴的这个代码是离线预处理A数组
这个东西其实是这个样子的
我们可以用一个巧妙的办法预处理A数组
这个问题实际上是我们在n+1到2n这个位置上，不断地求出我们在限制条件下能获得的最大值。本质上是一个贪心
离线预处理巧妙的利用了区间的优势，也就是利用区间和区间最值的联系
B数组只是限制你查找的区间，区间本质上是没有改变的，而每次查询需要尽可能的取得当前的最大值。因为区间的右端是固定的，B数组只是限制了[1，n]这个区间查找的左端，而且只需要查询最值，其他的值都没有用，那么我们完全可以通过预处理出 [1,n] 到 [n,n] 区间上的最值。那我们可以在用一个数组D[i]来保存[i，n]这个区间上的最值。对于新增区间我们只需要用一个变量来保存，新增区间上的最大值，因为新增区间的值的取用次数是无限，并不会受到限制，所以只有最大的那个可以无限次的发挥作用。所以用一个变量保存就好，然后依次计算[n+1，2n]这个区间上的值，把他们加起来就可以啦！
完事

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 250500;
const LL mod = (LL)1e9+7;
int n;
LL a[maxn], b[maxn];

signed main() {
    // freopen("in", "r", stdin);
    while(~scanf("%d", &n)) {
        a[n+1] = 0;
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);
        for(int i = n; i >= 1; i--) {
            a[i] -= i;
            a[i] = max(a[i], a[i+1]);
        }
        sort(b+1, b+n+1);
        LL ret = 0, flag = 0;
        for(int i = 1; i <= n; i++) {
            LL x = max(flag, a[b[i]]);
            ret = (ret + x) % mod;
            flag = max(flag, x-(n+i));
        }
        printf("%lld\n", ret);
    }
    return 0;
}