Chlience

【题解】LOJ 2019 「AHOI / HNOI2017」影魔
Problem给定一个序列 $a$ ,对于每个二元组 $(i,j)$ 可能会对答案做出 $p_1$ 或者 $p_2...
扫描右侧二维码阅读全文
02
2019/02

【题解】LOJ 2019 「AHOI / HNOI2017」影魔

Problem

给定一个序列 $a$ ,对于每个二元组 $(i,j)$ 可能会对答案做出 $p_1$ 或者 $p_2$ 的贡献

  1. 若 $max\{a_k|i<k<j\}<a_i​$ 并且 $max\{a_k|i<k<j\}<a_j​$,则有 $p_1​$ 的贡献
  2. 若 $max\{a_k|i<k<j\}>min\{a_i,a_j\}$ 并且 $max\{a_k|i<k<j\}<max\{a_i,a_j\}$,则有 $p_2$ 的贡献

每次给定一个区间 $[l,r]$ ,求区间贡献和

Thought

尝试着分步进行计算?

首先考虑下情况 1

处理出每个点 $x$ 比他大的左右端点,设为 $L_x,R_x$
显然它是区间$(L_x.R_x)$ 中最大的点,并且小于 $L_x$ 和 $R_x$ 上的点

然后它就会对这样的左右端点做出贡献 $p_1$,记录下 $(L_x,R_x,p_1)$
这傻逼东西可以用主席树维护

接下来考虑情况 2

要询问一端高,一端低的情况,首先,如果该点是区间中最大值,那么仍然周到每个点 $x$ 比他大的左右端点,设为 $L_x,R_x$

对于二元组 $(l,R_x),l\in(L_x,x)$ 和 $(L_x,r),r\in(x,R_x)$ 均满足比一端大,比一端小,并且为区间内的最大值

但是这就有可能有很多种状态,可以达到 $O(n^2)$ 级别,显然直接存下来是不可以接受的

但是如果有个方法使得每个点只需要记录两个状态那岂不是美滋滋?

那我就开两个主席树?
分别按照左端点固定和右端点固定的情况,每次相当于在主席树上区间更新?
标记永久化一下即可

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
#define mid ((l + r) >> 1)
typedef long long LL;
const int N = 200010;
LL p1, p2;
int n, m;
int k[N];
int sta[N], top;
int lb[N], rb[N];
struct P {
    int x, l, r;
    LL key;
    bool operator < (const P a) const {
        return x < a.x;
    }
};
P que[N << 2];
int quecnt;

struct Tree {
    int l, r;
    LL sum, add;
};
Tree t[N * 200];
int rt[N], tot;
void insert(int &x, int l, int r, int ll, int rr, LL v) {
    t[++ tot] = t[x]; x = tot;
    if(l >= ll && r <= rr) {
        t[x].add += v;
        t[x].sum += v * (r - l + 1);
    }
    else {
        if(mid >= ll)
            insert(t[x].l, l, mid, ll, rr, v);
        if(mid < rr)
            insert(t[x].r, mid + 1, r, ll, rr, v);
        t[x].sum = t[t[x].l].sum + t[t[x].r].sum + (r - l + 1) * t[x].add;
    }
}
LL query(int x, int l, int r, int ll, int rr, LL pre) {
    if(l >= ll && r <= rr)
        return t[x].sum + pre * (r - l + 1);
    LL res = 0;
    if(mid >= ll)
        res += query(t[x].l, l, mid, ll, rr, pre + t[x].add);
    if(mid < rr)
        res += query(t[x].r, mid + 1, r, ll , rr, pre + t[x].add);
    return res;
}
void getLR() {
    for(int i = 1; i <= n; ++ i) {
        while(top && k[sta[top]] < k[i]) sta[top --] = 0;
        lb[i] = sta[top];
        sta[++ top] = i;
    }
    while(top) sta[top -- ] = 0;
    for(int i = n; i >= 1; -- i) {
        while(top && k[sta[top]] < k[i]) sta[top --] = 0;
        rb[i] = top ? sta[top] : n + 1;
        sta[++ top] = i;
    }
}
int main() {
    n = read(); m = read();
    p1 = read(); p2 = read();
    for(int i = 1; i <= n; ++ i)
        k[i] = read();
    getLR();
    for(int i = 1; i <= n; ++ i) {
        if(i + 1 <= n)
            que[++ quecnt] = {i, i + 1, i + 1, p1};
        if(lb[i] >= 1 && rb[i] <= n)
            que[++ quecnt] = {lb[i], rb[i], rb[i], p1};
        if(rb[i] <= n && i - lb[i] - 1)
            que[++ quecnt] = {rb[i], lb[i] + 1, i - 1, p2};
        if(lb[i] >= 1 && rb[i] - i - 1)
            que[++ quecnt] = {lb[i], i + 1, rb[i] - 1, p2};
    }
    sort(que + 1, que + quecnt + 1);
    int head = 1;
    for(int i = 1; i <= n; ++ i) {
        rt[i] = rt[i - 1];
        while(head <= quecnt && que[head].x == i) {
            insert(rt[i], 1, n, que[head].l, que[head].r, que[head].key);
            ++ head;
        }
    }
    
    for(int i = 1; i <= m; ++ i) {
        int l = read(), r = read();
        long long res = query(rt[r], 1, n, l, r, 0) - query(rt[l - 1], 1, n, l, r, 0);
        printf("%lld\n", res);
    }
    return 0;
}
Last modification:February 2nd, 2019 at 05:33 pm

Leave a Comment