1. 题目

传送门=￣ω￣=

2. 题解

我太蒻了，唉。。。写好久

我们首先设 $L[i]$ 表示在位置 $i$ 左边的第一个比 $K[i]$ 大的数字的位置

$R[i]$ 表示在位置 $i$ 右边的第一个比 $K[i]$ 大的数字的位置

那么：

点对 $(L[i], R[i])$ 可以提供 $P1$ 的战斗力（显然符合第一种条件）
点对 $(i, i + 1)$ 可以提供 $P1$ 的战斗力（题目描述有讲）
点对（们） $(L[i], i + 1 \sim R[i] – 1)$ 可以提供 $P2$ 的战斗力（ $K[L[i]] > K[i] > K[i + 1 \sim R[i] – 1]$ ）
点对（们） $(L[i] + 1 \sim i – 1, R[i])$ 可以提供 $P2$ 的战斗力（ $K[L[i] + 1 \sim i – 1] < K[i] < K[R[i]]$ ）

而且因为 $K[i]$ 互不相同，所以 $L[i],R[i]$ 互不相同，点对也互不相同，不用担心重复计算。

那么我们等于是每次询问一个区间 $[l,r]$ 内包含的点对权值之和。

不难发现上面四种点对中，全都至少含有一个定点。

其中情况 1 包含定点 $L[i], R[i]$ ，情况 2 包含定点 $i, i + 1$ ，情况 3 包含定点 $L[i]$ ，情况 4 包含定点 $R[i]$ 。

对于情况 $1, 2$ ，我们都把它们看做左端点为定点（也就是和情况 $3$ 一样）。而情况 $4$ 为右端点为定点。

那我们搞两棵主席树，第一棵对应情况 $1, 2, 3$ ，第二棵对应情况 $4$ 。

主席树的时间维为定点的坐标，内部线段树维护定点对应的区间权值和。

比如第二棵主席树的第 $i$ 个版本的区间 $[l,r]$ 表示当定点是右端点，右端点为 $i$ 的时候，左端点在 $[l,r]$ 的点对的权值之和。

打个比方，如果我们有这样一些点对：

$(1\sim 5, 8)$ （点对定点为右端点，右端点为 $8$ ，左端点 $\in [1,5]$ ）

那么我们就在第二棵主席树的第 $8$ 个版本中，将区间 $[1,5]$ 的权值加上 $P2$

第一棵主席树也这么搞。

对于单点修改我们也看做区间修改（好吧也许这是一句废话）

然后对于查询 $[l,r]$ ：

我们先查询第一棵主席树的第 $r$ 个版本的 $[l,r]$ 的区间和，再减去第 $l-1$ 个版本的 $[l,r]$ 的区间和，就得到了情况 $1,2,3$ 在区间 $[l,r]$ 内的和。

然后对于情况 $4$ ，也是一样的。第二棵主席树的第 $r$ 个版本的 $[l,r]$ 的区间和减去第 $l-1$ 个版本的 $[l,r]$ 的区间和就是情况 $4$ 在 $[l,r]$ 内的和了。

因为我们先查第 $r$ 个版本，就限定了点对的那一个定点的位置小于等于 $r$ ，然后又减去了第 $l-1$ 个版本，就限制了定点位置大于等于 $l$ 。

至于主席树的区间操作，用标记永久化就行了，不做过多赘述。

还有一个小优化，就是情况 $2$ 可以不加到主席树中，情况 $2$ 在 $[l,r]$ 内的和就是 $P1\times (r – l)$ 。

至于主席树空间开多大的话：

对于主席树，最坏情况下每一层会有 $4$ 个节点被修改，然后主席树最坏情况有 $\left \lceil log_2N + 1 \right \rceil$ 层，操作数是与 $N$ 同级的，所以节点数至少开： $4N\left \lceil log_2N + 1 \right \rceil$ ，大约是 $11400000$ ，再稍微加个 $5$ 就行啦！

具体看代码吧 QwQ

代码：

/*
 * 影魔.cpp
 * This file is part of 影魔
 *
 * Copyright (C) 2018 - xzy
 *
 * 影魔 is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 影魔 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more detops.
 *
 * You should have received a copy of the GNU General Public License
 * along with 影魔. If not, see <http://www.gnu.org/licenses/>.
 */

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"

#include <bits/stdc++.h>

#define NS (200005)
#define PS (11400005)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct TII{int x, y, z;};

struct N {LL d, tag; int l, r;} e[PS];

int size;

struct CMT
{
    #define LEN (min(R, r) - max(L, l) + 1)
    int root[NS];
    void update(int l, int r, LL d, int L, int R, int& x, int y)
    {
        x = ++size, e[x] = e[y], e[x].d += LEN * d;
        if (l <= L && R <= r) {e[x].tag += d; return;}
        int Mid = (L + R) >> 1;
        if (l <= Mid) update(l, r, d, L, Mid, e[x].l, e[y].l);
        if (r > Mid) update(l, r, d, Mid + 1, R, e[x].r, e[y].r);
    }
    LL query(int l, int r, int L, int R, int a)
    {
        if (!a) return 0;
        if (l <= L && R <= r) return e[a].d;
        int Mid = (L + R) >> 1; LL res = e[a].tag * LEN;
        if (l <= Mid) res += query(l, r, L, Mid, e[a].l);
        if (r > Mid) res += query(l, r, Mid + 1, R, e[a].r);
        return res;
    }
    #undef LEN
}tl, tr;

int n, m, p1, p2, k[NS], lt[NS], rt[NS];

int top, que[NS], qid[NS];

vector<TII> ch1[NS], ch2[NS];

void Init()
{
    top = 1;
    for (int i = 1; i <= n; i += 1) rt[i] = n + 1;
    for (int i = 1; i <= n; i += 1)
    {
        while (1 < top && que[top - 1] < k[i])
            rt[qid[top - 1]] = i, top--;
        lt[i] = qid[top - 1], qid[top] = i, que[top++] = k[i];
    }
    for (int i = 1; i <= n; i += 1)
    {
        if (lt[i] && rt[i] <= n)
            ch1[lt[i]].push_back((TII){rt[i], rt[i], p1});
        if (lt[i] && i + 1 <= rt[i] - 1)
            ch1[lt[i]].push_back((TII){i + 1, rt[i] - 1, p2});
        if (rt[i] <= n && lt[i] + 1 <= i - 1)
            ch2[rt[i]].push_back((TII){lt[i] + 1, i - 1, p2});
    }
}

void Build()
{
    for (int i = 1; i <= n; i += 1)
    {
        tl.root[i] = tl.root[i - 1];
        for (vector<TII>::iterator j = ch1[i].begin(); j != ch1[i].end(); j++)
            tl.update(j->x, j->y, j->z, 1, n, tl.root[i], tl.root[i]);
        tr.root[i] = tr.root[i - 1];
        for (vector<TII>::iterator j = ch2[i].begin(); j != ch2[i].end(); j++)
            tr.update(j->x, j->y, j->z, 1, n, tr.root[i], tr.root[i]);
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(p1), IN(p2);
    for (int i = 1; i <= n; i += 1) IN(k[i]);
    Init(), Build();
    while (m--)
    {
        int a, b; LL ans = 0;
        IN(a), IN(b);
        ans += tl.query(a, b, 1, n, tl.root[b]);
        ans -= tl.query(a, b, 1, n, tl.root[a - 1]);
        ans += tr.query(a, b, 1, n, tr.root[b]);
        ans -= tr.query(a, b, 1, n, tr.root[a - 1]);
        ans += 1ll * p1 * (b - a);
        printf("%lld\n", ans);
    }
    return 0;
}

【题解】影魔主席树 BZOJ – 4826

于2018年3月21日2018年3月21日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复取消回复

【题解】影魔 主席树 BZOJ – 4826

于2018年3月21日2018年3月21日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复 取消回复

【题解】影魔主席树 BZOJ – 4826

发表回复取消回复