1. 题目

传送门= ̄ω ̄=

2. 题解

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

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

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

那么:

  1. 点对$(L[i], R[i])$可以提供$P1$的战斗力(显然符合第一种条件)
  2. 点对$(i, i + 1)$可以提供$P1$的战斗力(题目描述有讲)
  3. 点对(们)$(L[i], i + 1 \sim R[i] – 1)$可以提供$P2$的战斗力($K[L[i]] > K[i] > K[i + 1 \sim R[i] – 1]$)
  4. 点对(们)$(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;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *