LOJ 2019 [HNOI 2017] 影魔

题意：https://loj.ac/problem/2019

solution1：

首先要看清楚题意，两种情况不是互补的。

\(1:\forall s\in[i+1,j-1],A_s<Ai,A_s<A_j\)时产生\(p_1\)的贡献

\(2:A_i<\max\{A[i+1...j-1]\}<A_j\)或者\(A_j<\max\{A[i+1...j-1]\}<A_i\)时产生\(p_2\)的贡献

\(3:A_i<\max\{A[i+1...j-1]\},A_j<\max\{A[i+1...j-1]\}\)不产生贡献

\(4:A_i\)形成排列，不存在相等关系。

每个产生贡献的点对\((i,j)\)依赖\(\max_{k=i+1}^{j-1}A_k\)，因此考虑算每个\(A_k\)的贡献。

考虑固定每个\(A_i\)为最大值，设在\(i\)之前离\(i\)最近的大于\(A_i\)的为\(A_j\)，\(i\)之后离\(i\)最近的大于\(A_i\)的为\(A_k\)

注意，考虑前后相邻的大于\(A_i\)的点的原因是如果左右端点越过\(j\)或者\(k\)，明显\(A_i\)不再会作为最大值

因此不应该越界，又由前面的整理，可以得到\(A[j+1...i-1]<A_i\),\(A[i+1...k-1]<A_i\)

产生\(p_1\)贡献的点对：有且仅有\((j,k)\)。

产生\(p_2\)贡献的点对：固定\(j\)为左端点，且右端点在\([i+1,k-1]\)内；固定\(k\)为右端点，且左端点在\([j+1,i-1]\)内

然后考虑怎么维护。

首先可以把询问拆成两个前缀相减，然后把贡献和询问都离线掉

扫到一个询问先把pos\(\leq\)当前询问位置的贡献加上，然后根据是询问的左端点还是右端点维护答案。

这样对于一个询问来说如果贡献越界，那么就会出现在两次询问里消掉

#include<cstdio>
#include<cstring>
#define R register
#include<algorithm>
const int N = 2e5+7;
typedef long long LL;
#define debug printf("GG\n")
LL ans[N], A[N];
struct QS {
  int x, id;
} q[N*2];
struct Point {
  int pos, l, r, w;
} p[N*2];
int st[N], top, tot, vis[N];
struct BIT {
  LL c[N*2][2];int n;
  #define lbt(x) (x & (-x))
  inline void update(int x, int type, LL k) {
    while (x <= n) c[x][type] += k, x += lbt(x);
  }
  inline LL ask(int x, int type) {
    LL res = 0;
    while (x) res += c[x][type], x -= lbt(x);
    return res;
  }
  inline void Modify(int l, int r, int w) {
    update(l, 0, 1LL * w), update(r + 1, 0, (LL)-w), 
    update(l, 1, 1LL * l * w), update(r + 1, 1, 1LL * (r + 1) * -w);
  }
  inline LL query(int l, int r) {
    return (LL)(((LL)r + 1LL) * ask(r, 0) - ask(r, 1))
      - (LL)((LL)l * ask(l - 1, 0) - ask(l - 1, 1));
  }
}t;
inline int cmp1(QS a, QS b) {
  return a.x < b.x;
}
inline int cmp2(Point a, Point b) {
  return a.pos < b.pos;
}
int n, m, p1, p2, nxt[N], pre[N], L[N], RR[N];
void findpn() {
  for (R int i = 1; i <= n; i++) {
    while (top && A[st[top]] < A[i]) nxt[st[top--]] = i;
    pre[i] = st[top], st[++top] = i;
  }
  for (R int i = 1; i <= n; i++)
    if (!nxt[i]) nxt[i] = n + 1;
  for (R int i = 1; i <= n; i++) {
    int pr = pre[i], nx = nxt[i];
    if (pr > 0 && nx <= n) p[++tot] = (Point){pr, nx, nx, p1};
    if (pr > 0 && i + 1 <= nx - 1) p[++tot] = (Point){pr, i + 1, nx - 1, p2};
    if (nx <= n && i - 1 >= pr + 1) p[++tot] = (Point){nx, pr + 1, i - 1, p2};
  }
  //debug;
  std :: sort(p + 1, p + tot + 1, cmp2);
}
int main() {
  scanf("%d%d%d%d", &n, &m, &p1, &p2);
  t.n = n;
  for (R int i = 1; i <= n; i++)
    scanf("%d", &A[i]);
  for (R int i = 1; i <= m; i++) {
    scanf("%d%d", &L[i], &RR[i]);
    if (L[i] == RR[i]) continue;
    q[(i - 1) * 2 + 1] = (QS){L[i] - 1, i}, q[i * 2] = (QS){RR[i], i};
  } 
  std :: sort(q + 1, q + m * 2 + 1, cmp1);
  findpn();
  int pos = 1, cnt = 1, up = 2 * m;
  for (R int i = 1; i <= up; i++) {
    while (cnt <= q[i].x) 
      t.Modify(cnt + 1, cnt + 1, (LL)p1), cnt++;
    while (pos <= tot && p[pos].pos <= q[i].x) 
      t.Modify(p[pos].l, p[pos].r, (LL)p[pos].w), pos++;
    if (!vis[q[i].id]) 
      ans[q[i].id] = -t.query(L[q[i].id], RR[q[i].id]), vis[q[i].id] = 1;
    else ans[q[i].id] += t.query(L[q[i].id], RR[q[i].id]);
  }
  for (R int i = 1; i <= m; i++)
    printf("%lld\n", ans[i]);
return 0;
}

LOJ 2019 [HNOI 2017] 影魔

原文：https://www.cnblogs.com/cjc030205/p/11638111.html