完结四代目,我来吃屏幕了
查看原帖
完结四代目,我来吃屏幕了
20522
ccviolett楼主2020/6/15 11:32

终于搞出来了,三代目的时候说再重构就吃屏幕,但是不调出来真的害怕(不知道自己哪里错了,万一考试的时候被搞了就完了)

不能发题解,就发个讨论,提醒一下各位做这道题目的。

这道题目可以在 Tarjan 的时候同时算出答案来,Tarjan 找到一个环时,更新环上的所有答案,其余情况正常转移。

其他地方都 A 了,但是 luogu 的数据真的强,有一个地方是出锅了的,可以去看看我前面的代码。

重点:Tarjan 的同时计算答案,需要考虑兄弟边的影响。

平时写 Tarjan 写惯了,只考虑出边和反祖边,兄弟边都是直接忽略的,而这里兄弟边也会对答案产生影响。

就这样了,我来吃屏幕了。

/* Header {{{ */
#include <bits/stdc++.h>
using namespace std;

typedef long long readtype;
typedef long long var;

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c)) s |= c == '-', c = getchar();
  while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}
/* }}} */

const int N = 5e5 + 1;
const int M = 2e7 + 1;
const int MOD = 1e9 + 7;

inline int add(int a, int b) { return (a + b >= MOD) ? (a + b - MOD) : (a + b); }
inline int mul(var a, int b) { return (a * b) % MOD; }

int n, id[N];
var x[N], r[N];

int lpos[M], rpos[M];
int top, fi[M], ne[M << 1], to[M << 1];
int T, dfn[M], low[M];
int cnt, sta[M];
bool insta[M];

void Add(int u, int v);
void Build(int t, int l, int r);
void Modify(int x, int y, int v, int t, int l, int r);
void Tarjan(int t);

int main() {
  n = read();
  for (int i = 1; i <= n; ++i)
    x[i] = read(), r[i] = read();
  Build(1, 1, n);
  for (int i = 1; i <= n; ++i) {
    int lx = lower_bound(x + 1, x + n + 1, x[i] - r[i]) - x;
    int rx = upper_bound(x + 1, x + n + 1, x[i] + r[i]) - x - 1;
    Modify(lx, rx, id[i], 1, 1, n);
  }

  Tarjan(1);

  int res = 0;
  for (int i = 1; i <= n; ++i)
    res = add(res, mul(i, rpos[id[i]] - lpos[id[i]] + 1));
  printf("%d\n", res);
  return 0;
}

void Add(int u, int v) {
  ne[++top] = fi[u], fi[u] = top, to[top] = v;
}

void Build(int t, int l, int r) {
  lpos[t] = l, rpos[t] = r;
  int mid = (l + r) >> 1;
  if (l == r) {
    id[mid] = t;
    return ;
  }
  Build(t << 1, l, mid), Build(t << 1 | 1, mid + 1, r);
  Add(t, t << 1), Add(t, t << 1 | 1);
}

void Modify(int x, int y, int v, int t, int l, int r) {
  if (x <= l && r <= y) {
    if (v != t) Add(v, t);
    return ;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) Modify(x, y, v, t << 1, l, mid);
  if (y > mid) Modify(x, y, v, t << 1 | 1, mid + 1, r);
}

void Tarjan(int t) {
  dfn[t] = low[t] = ++T;
  sta[++cnt] = t, insta[t] = true;
  for (int i = fi[t]; i; i = ne[i]) {
    if (!dfn[to[i]]) {
      Tarjan(to[i]), low[t] = min(low[t], low[to[i]]);
      lpos[t] = min(lpos[t], lpos[to[i]]);
      rpos[t] = max(rpos[t], rpos[to[i]]);
    }
    else if (insta[to[i]]) low[t] = min(low[t], dfn[to[i]]);
    else {
      lpos[t] = min(lpos[t], lpos[to[i]]);
      rpos[t] = max(rpos[t], rpos[to[i]]);
    }
  }
  if (dfn[t] == low[t]) {
    int tlpos = lpos[t], trpos = rpos[t];
    for (int i = cnt; sta[i + 1] != t; --i) {
      tlpos = min(tlpos, lpos[sta[i]]);
      trpos = max(trpos, rpos[sta[i]]);
    }
    for (int i = cnt; sta[i + 1] != t; --i)
      lpos[sta[i]] = tlpos, rpos[sta[i]] = trpos;
    while (sta[cnt + 1] != t) {
      int x = sta[cnt--];
      insta[x] = false;
    }
  }
}
2020/6/15 11:32
加载中...