Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P3527 【[POI2011]MET-Meteors】

posted on 2019-09-01 11:02:42 | under 题解 |

在发现此题前,我以为整体二分只能求第K大来着,我还是太菜了

我们先不考虑多组询问,假设只有一组询问

不难发现,答案具有明显的单调性,所以我们考虑二分来做

对于我们二分的值 $mid$ ,我们先假设 $l-mid$ 的雨全部下下来

如果当前的降雨量大于我们所需要的,那么答案大了,否则答案小了,就把所需要的降雨量变为:原本所需要的降雨量 $-(l-mid$ 的降雨量 $)$

那么有多组询问要怎么做呢?

我们考虑整体二分,我们定义函数solve(l, r, L, R)为我们二分的值为 $[l, r]$ (也就是单组询问的 $l, r$ ),目前的操作区间为 $[L,R]$ (如果是单组询问的话就是 $[L==R]$ )

我们可以将 $[L, R]$ 区间内所有的操作进行分类:分成答案大的和答案小的(见单组二分的分类),将答案小的放在前面(类似于归并排序),将答案大的放在后面,于是我们就可以继续二分递归了

我们假设在 $[L, R]$ 内有 $cnt1$ 个操作比答案小,那么我们递归应该是:

solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R);

最后,我们最开始的假设 $[l, mid]$ 的雨全部下下来,可以用树状数组来实现,在每次递归进入下一次的时候,树状数组需要清空,但我们并不需要 $memset$ ,只需要把这一层递归修改的值改回来就行了

$Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
#define inf 1000000000 
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define lb(x) (x)&(-(x))
#define maxn 300005
int n, m, ans[maxn], tr[maxn * 2], T;
struct ques {
    int l, r, a, id;
}e[maxn];
struct node {
    int ned, id;
}p[maxn], p1[maxn], p2[maxn];
vector<int> q[maxn];
il void add(int x, int v) {
    for(re int i = x; i <= 2 * m; i += lb(i)) tr[i] += v;
}
il int query(int x) {
    int ans = 0;
    for(re int i = x; i; i -= lb(i)) ans += tr[i];
    return ans;
}
il int Query(int x) {
    int ans = 0;
    for(re int i = 0; i < q[p[x].id].size(); ++ i) {
        ans += query(q[p[x].id][i]) + query(q[p[x].id][i] + m);
        if(ans >= p[x].ned) return ans;
    }
    return ans;
}
il void solve(int l, int r, int L, int R) {
    if(L > R) return;
    if(l == r) {
        //如果二分到了终点,显然当前操作区间的答案都等于二分的答案
        rep(i, L, R) ans[p[i].id] = l;
        return;
    }
    int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
    //差分,假设[l, mid]的雨全部下下来
    rep(i, l, mid) add(e[i].l, e[i].a), add(e[i].r + 1, -e[i].a);
    //判断哪些答案大了,那些小了
    rep(i, L, R) {
        int temp = Query(i);
        if(temp >= p[i].ned) p1[++ cnt1] = p[i];
        else p[i].ned -= temp, p2[++ cnt2] = p[i];
    }
    //清空树状数组
    rep(i, l, mid) add(e[i].l, -e[i].a), add(e[i].r + 1, e[i].a);
    //归并排序
    rep(i, L, L + cnt1 - 1) p[i] = p1[i - L + 1];
    rep(i, L + cnt1, R) p[i] = p2[i - L - cnt1 + 1];
    //继续二分
    solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R);
}
signed main() {
    n = read(), m = read();
    rep(i, 1, m) q[read()].push_back(i);
    rep(i, 1, n) p[i].ned = read(), p[i].id = i;
    T = read();
    rep(i, 1, T) {
        e[i].l = read(), e[i].r = read(), e[i].a = read(), e[i].id = i;
        if(e[i].r < e[i].l) e[i].r += m;
    }
    ++ T, e[T].id = T, e[T].l = 1, e[T].r = 2 * m, e[T].a = inf;
    solve(1, T, 1, n);
    rep(i, 1, n) ans[i] == T ? puts("NIE") : printf("%lld\n", ans[i]);
    return 0;
}