论Dota中影魔的攻击力（二维数点问题）

ACM算法日常

发布于 2020-05-18 20:17:43

6300

文章被收录于专栏：ACM算法日常ACM算法日常

缘起

影魔是Dota中极为受欢迎的英雄. 所以我们很有必要讨论一下影魔的攻击力. 题目来自 AHOI2019 影魔

此题的典型性是因为它其实是一类很广泛的问题——二维数点问题.

分析

首先声明一下，本文的前置技能是单调栈+主席树.

先简化一下题意~

首先，对于ki，令l[i]和r[i]分别是向左第一个大于ki的数在k中的索引（如果不存在的话, li=0）和向右第一个大于 ki 的数在k中的索引（如果不存在，则 ri=n+1），利用单调栈可以预处理出 l数组和r数组.

那么不难注意到如下事实

(li, ri) 是能贡献p1的点对
(li, t) 是能贡献p2的点对, 其中i < t < ri, 这样的点对有ri - i - 1个
(t, ri) 是能贡献p2的点对, 其中li < t < i, 这样的点对有i - li - 1个

如果我们将询问的区间 a, b 映射到二维平面上去，就是 , 然后将上面三个事实也映射到二维平面上去，则得到下图

这里说明一下，图1中的黄线和蓝线上每个点都贡献 , 黑点贡献

所以我们每次查询l, r其实就是询问矩形内的点权和. 这是一类典型问题——二维数点问题，确切讲是静态二维数点问题（但是下文简称二维数点问题），因为本题不带修嘛. 这种问题可以使用主席树在线做，也可以使用树状数组+扫描线来离线做.

ps: 至于带修的二维数点问题，可以使用树状数组套主席树在线做，也可以使用 CDQ分治套树状数组离线做.

二维数点问题的定义

给定平面上的n个点, , 每个点的权值是 , m次询问

二维数点问题的主席树解法

首先我们回顾一下主席树能处理的典型问题

给定数列 , 每次回答询问 , 即中权值在中的元素的个数.

而对于本题, (1) 不就是要求纵坐标（视作的数组下标）在 c, d 内的并且横坐标（视作权值）属于权值范围 a, b 内的贡献和么? 我们称这种主席树为Y方向的主席树.

当然，你也可以视作是求横坐标（视作的数组下标）在 a, b 内的并且纵坐标（视作权值）属于权值范围 c, d 内的贡献和. 我们称这种主席树为X方向的主席树.

这是二维数点问题能使用主席树切的核心观察~

我们先来考虑一下如何用主席树计算图1中的黄线对答案的贡献.

注意到黄线上的点Y坐标都相同，只是X坐标不同，而且X坐标是一段连续的区间. 而且这些点的权值贡献都是

所以我们只需要维护一棵Y方向的主席树，对这棵主席树做区间更新. 所以懒标记势在必行.

类似的，我们也维护一棵X方向的主席树来计算图1中蓝线的贡献.

还剩下的黑点是单点，你既可以单独再搞一棵Y方向或者X方向的主席树来维护黑点的贡献也可以将黑点并入前述的两棵主席树中的任何一棵进行考虑.

甚至有大佬是使用一棵主席树来处理黄线、蓝线、黑点.

主席树的棵树越少，代码可读性越差，但是性能越好.

为了可读性，这里使用了三棵主席树，也就是下面代码中的 hjt1、hjt2、hjt3, 分别维护了黄线的贡献、蓝线的贡献、黑点的贡献.

本文主席树的数据结构设计为

struct HJTTreeNode
{
    int l, r, lc, rc, num, lz;
}; // lz 表示当前线段树节点表示的权值区间[l, r]的每一个权值出现的次数+lz, num 是每个权值出现的次数.lc、rc分别是当前节点的左右孩子节点.

于是就可以用带懒标记的主席树切掉二维数点问题了~

//#include "stdafx.h"
//#define LOCAL
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <string>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <map>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define re register int
typedef pair<int, int> P;
#define FE(cur) for(re h = head[cur], to, len; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define ilp inline P
#define LEN(cur) (hjt[cur].r - hjt[cur].l)
#define MID(cur) (hjt[cur].l + hjt[cur].r >> 1)
#define SQUARE(x) ((x) * (x))
typedef vector<int>::iterator vit;
typedef vector<int>::reverse_iterator rvit;
typedef vector<char>::iterator cit;
typedef vector<char>::reverse_iterator rcit;
namespace fastio
{
    const int BUF = 1 << 21;
    char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
    ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
    ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
    ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
    ilv read(int &x)
    {
        x = 0; int f = 1; char c = gc();
        while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
        while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
        x *= f;
    }
    ilv write(long long x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
    ilv writeln(long long x) { write(x);pc(10); }
    ilv read(char *x)
    {
        char c = gc();
        while(!isalpha(c)) c = gc();
        while (isalpha(c)) *x++ = c, c = gc();
        *x = 0;
    }
    ilv readln(char *x)
    {
        char c = gc();
        while(c == 10) c = gc();
        while(c >= 32 && c <= 126) *x++ = c, c = gc();
        *x = 0;
    }
    ilv write(char *x) { while(*x) pc(*x++); }
    ilv writeln(char *x) { write(x); pc(10); }
    ilv write(char c) { pc(c); }
    ilv writeln(char c) { write(c); pc(10); }
} using namespace fastio;
const int maxn = 2e5+5;
int n, m, p1, p2, k[maxn], tot1, tot2, tot3, ver1[maxn], ver2[maxn], ver3[maxn], li[maxn], ri[maxn];
struct HJTTreeNode
{
    int l, r, lc, rc, num, lz;
} hjt1[maxn * 30], hjt2[maxn * 30],hjt3[maxn * 30];
vector<P> ps1[maxn], ps2[maxn], ps3[maxn]; // ps1[i]收集的是纵坐标为i的黄线, ps2[i]收集的是横坐标为i的蓝线, ps3[i]收集的是纵坐标为i的黑点

ilv kkl()
{
    stack<int> s;
    for (re i = 1; i <= n; i++)
    {
        while(!s.empty() && k[s.top()] < k[i])
        {
            s.pop();
        }
        li[i] = s.empty() ? 0 : s.top();
        s.push(i);
    }
}

ilv kkr()
{
    stack<int> s;
    for (re i = n; i; i--)
    {
        while(!s.empty() && k[s.top()] < k[i])
        {
            s.pop();
        }
        ri[i] = s.empty() ? n + 1 : s.top();
        s.push(i);
    }
}

ili newnode(int l, int r, HJTTreeNode *hjt, int &tot)
{
    ++tot;
    hjt[tot].l = l, hjt[tot].r = r;
    return tot;
}

ili copynode(int i, HJTTreeNode *hjt, int &tot)
{
    ++tot;
    hjt[tot] = hjt[i];
    return tot;
}


int build(int l, int r, HJTTreeNode *hjt, int &tot)
{
    int rt = newnode(l, r, hjt, tot);
    if (l == r)
    {
        return rt;
    }
    int mid = l + r >> 1;
    hjt[rt].lc = build(l, mid, hjt, tot);
    hjt[rt].rc = build(mid + 1, r, hjt, tot);
    return rt;
}

ilv pushdown(int cur, HJTTreeNode *hjt, int &tot)
{
    if (hjt[cur].lz)
    {
        int &lc = hjt[cur].lc, &rc = hjt[cur].rc;
        if (lc)
        {
            lc = copynode(lc, hjt, tot);
            hjt[lc].lz += hjt[cur].lz;
        }
        if (rc)
        {
            rc = copynode(rc, hjt, tot);
            hjt[rc].lz += hjt[cur].lz;
        }
        hjt[cur].lz = 0;
    }
}

ili getnum(int cur, HJTTreeNode *hjt)
{
    return hjt[cur].num + hjt[cur].lz * (LEN(cur) + 1);
}

ilv pushup(int cur, HJTTreeNode *hjt)
{
    hjt[cur].num = getnum(hjt[cur].lc, hjt) + getnum(hjt[cur].rc, hjt);
}

int ins(int cur, int l, int r, HJTTreeNode *hjt, int &tot)
{
    if (hjt[cur].l == l && hjt[cur].r == r)
    {
        int rt = copynode(cur, hjt, tot);
        hjt[rt].lz = hjt[cur].lz + 1;
        return rt;
    }
    int rt = copynode(cur, hjt, tot);
    pushdown(rt, hjt, tot);
    int mid = MID(cur), lc = hjt[rt].lc, rc = hjt[rt].rc;
    if (r <= mid)
    {
        lc = ins(lc, l, r, hjt, tot);
    }
    else if (l > mid)
    {
        rc = ins(rc, l, r, hjt, tot);
    }
    else
    {
        lc = ins(lc, l, mid, hjt, tot);
        rc = ins(rc, mid + 1, r, hjt, tot);
    }
    hjt[rt].lc = lc, hjt[rt].rc = rc;
    pushup(rt, hjt);
    return rt;
}

int que(int cur1, int cur2, int l, int r, HJTTreeNode *hjt, int &tot)
{
    if (hjt[cur1].l == l && hjt[cur1].r == r || cur1 == cur2)
    {
        return getnum(cur2, hjt) - getnum(cur1, hjt);
    }
    pushdown(cur1, hjt, tot), pushdown(cur2, hjt, tot);
    int mid = MID(cur1), ans;
    int lc1 = hjt[cur1].lc, lc2 = hjt[cur2].lc;
    int rc1 = hjt[cur1].rc, rc2 = hjt[cur2].rc;
    if (r <= mid)
    {
        ans = que(lc1, lc2, l, r, hjt, tot);
    }
    else if (l > mid)
    {
        ans = que(rc1, rc2, l, r, hjt, tot);
    }
    else
    {
        ans = que(lc1, lc2, l, mid, hjt, tot) + que(rc1, rc2, mid + 1, r, hjt, tot);
    }
    pushup(cur1, hjt), pushup(cur2, hjt);
    return ans;
}

signed main()
{
#ifdef LOCAL
    freopen("d:\\data.in", "r", stdin);
    freopen("d:\\my.out", "w", stdout);
#endif
    read(n), read(m), read(p1), read(p2);
    for (re i = 1; i <= n; i++) read(k[i]);
    kkl(), kkr();
    for (re i = 1; i <= n; i++)
    {
        if (li[i] + 1 < i)
        {
            ps1[ri[i]].push_back(P(li[i] + 1, i - 1)); // 黄线
        }
        if (i + 1 < ri[i])
        {
            ps2[li[i]].push_back(P(i + 1, ri[i] - 1)); // 蓝线
        }
        ps3[ri[i]].push_back(P(li[i], li[i])); // 黑点
    }
    ver1[0] = build(0, n + 1, hjt1, tot1);
    for (re i = 1; i <= n; i++) // 建立黄线主席树 hjt1
    {
        ver1[i] = ver1[i - 1];
        for (re j = 0, len = ps1[i].size(); j < len; j++)
        {
            ver1[i] = ins(ver1[i], ps1[i][j].first, ps1[i][j].second, hjt1, tot1);
        }
    }
    ver2[0] = build(0, n + 1, hjt2, tot2);
    for (re i = 1; i <= n; i++) // 建立蓝线主席树 hjt2
    {
        ver2[i] = ver2[i - 1];
        for (re j = 0, len = ps2[i].size(); j < len; j++)
        {
            ver2[i] = ins(ver2[i], ps2[i][j].first, ps2[i][j].second, hjt2, tot2);
        }
    }
    ver3[0] = build(0, n + 1, hjt3, tot3);
    for (re i = 1; i <= n; i++) // 建立黑点主席树 hjt3
    {
        ver3[i] = ver3[i - 1];
        for (re j = 0, len = ps3[i].size(); j < len; j++)
        {
            ver3[i] = ins(ver3[i], ps3[i][j].first, ps3[i][j].second, hjt3, tot3);
        }
    }
    int l, r;
    while(m--)
    {
        read(l), read(r);
        writeln(1ll * que(ver1[l - 1], ver1[r], l, r, hjt1, tot1) * p2 + 1ll * que(ver2[l - 1], ver2[r], l, r, hjt2, tot2) * p2 + 1ll * que(ver3[l - 1], ver3[r], l, r, hjt3, tot3) * p1 + 1ll * (r - l) * p1);
    }
    flush();
    return 0;
}

ac情况:Accepted | 6265 ms | 308436 K

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-05-12，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度