QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386220#7453. rplexqalpha1022ML 0ms29360kbC++143.2kb2024-04-11 14:13:282024-04-11 14:13:28

Judging History

你现在查看的是最新测评结果

  • [2024-04-11 14:13:28]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:29360kb
  • [2024-04-11 14:13:28]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e5;
const int B = 300;
const int C = (N - 1) / B + 1;

int n, m, rt;
vector<int> e[N + 5], ch[N + 5];
int fa[N + 5], siz[N + 5], id[N + 5], rk[N + 5];
void dfs(int u) {
  static int tot = 0;
  rk[id[u] = ++tot] = u, siz[u] = 1;
  for (int v : e[u])
    if (v != fa[u])
      fa[v] = u, ch[u].push_back(v), dfs(v), siz[u] += siz[v];
  sort(ch[u].begin(), ch[u].end(), [](int x, int y) { return siz[x] > siz[y]; });
}
struct SqrtDecomposition {
  static const int B = 447;
  static const int C = (N - 1) / B + 1;
  int pos[N + 5], val[N + 5], sum[C + 5];
  void init(int n) { for (int i = 1; i <= n; ++i) pos[i] = (i - 1) / B + 1; }
  void update(int x, int k) {
    for (int i = x; i <= min(pos[x] * B, n); ++i) val[i] += k;
    for (int p = pos[x] + 1; p <= pos[n]; ++p) sum[p] += k;
  }
  int query(int x) { return val[x] + sum[pos[x]]; }
  int query(int l, int r) { return query(r) - query(l - 1); }
} sd;

ll ans[N + 5];
vector<tuple<int, int, int>> tqry;
vector<tuple<int, int, int, int>> opt[N + 5];
vector<tuple<int, int, int>> qry[N + 5];

int cnt[N + 5];

int main() {
  scanf("%d%d%d", &n, &m, &rt);
  for (int i = 2; i <= n; ++i) {
    int u, v; scanf("%d%d", &u, &v), e[u].push_back(v), e[v].push_back(u);
  }
  dfs(rt);
  auto insertQuery = [&](int l, int r, int u, int w, int qid) {
    opt[id[u]].emplace_back(l, r, 1, tqry.size()), opt[id[u] + siz[u]].emplace_back(l, r, -1, tqry.size()),
    tqry.emplace_back(w, qid, 0);
  };
  for (int i = 1; i <= m; ++i) {
    int l, r, u; scanf("%d%d%d", &l, &r, &u), insertQuery(l, r, u, 1, i);
    for (int j = 0; j < B && j < ch[u].size(); ++j) insertQuery(l, r, ch[u][j], -1, i);
    qry[u].emplace_back(l, r, i);
  }
  sd.init(n);
  for (int i = n; i; --i) {
    sd.update(rk[i], 1);
    for (auto [l, r, w, id] : opt[i]) get<2>(tqry[id]) += sd.query(l, r) * w;
  }
  for (auto [w, id, cur] : tqry) ans[id] += (ll)cur * (cur - 1) / 2 * w;
  for (int u = 1; u <= n; ++u) {
    if (B >= ch[u].size()) continue;
    vector<pair<int, int>> vec;
    for (int j = B; j < ch[u].size(); ++j) {
      int v = ch[u][j];
      for (int k = id[v]; k < id[v] + siz[v]; ++k) vec.emplace_back(rk[k], v);
    }
    sort(vec.begin(), vec.end());
    int block = sqrt(vec.size());
    for (auto &[l, r, id] : qry[u])
      l = lower_bound(vec.begin(), vec.end(), make_pair(l, 0)) - vec.begin(),
      r = upper_bound(vec.begin(), vec.end(), make_pair(r, n)) - vec.begin() - 1;
    sort(qry[u].begin(), qry[u].end(), [&](tuple<int, int, int> a, tuple<int, int, int> b) {
      return get<0>(a) / block != get<0>(b) / block ? get<0>(a) < get<0>(b) : ~(get<0>(a) / block) & 1 ? get<1>(a) < get<1>(b) : get<1>(a) > get<1>(b);
    });
    fill_n(cnt + 1, n, 0);
    int tl = 0, tr = -1; ll cur = 0;
    for (auto [l, r, id] : qry[u]) {
      while (tr < r) cur += cnt[vec[++tr].second]++;
      while (tl > l) cur += cnt[vec[--tl].second]++;
      while (tr > r) cur -= --cnt[vec[tr--].second];
      while (tl < l) cur -= --cnt[vec[tl++].second];
      ans[id] -= cur;
    }
  }
  for (int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 29360kb

input:

10 10 10
5 9
7 5
1 5
3 9
2 5
8 7
10 8
6 8
4 10
3 10 2
2 3 9
2 5 4
5 10 9
2 6 5
2 6 5
2 8 8
2 10 2
8 10 9
5 8 7

output:

0
0
0
0
3
3
9
0
0
1

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 29060kb

input:

10 10 7
4 2
10 4
3 2
6 10
9 2
7 3
1 4
8 2
5 3
8 10 10
2 6 2
3 6 2
4 6 4
3 10 2
8 8 10
3 10 4
2 3 2
2 6 4
1 7 10

output:

0
2
0
1
7
0
2
0
1
0

result:

ok 10 numbers

Test #3:

score: -100
Memory Limit Exceeded

input:

200000 200000 90409
124478 160846
171209 124478
192187 171209
180973 171209
189328 160846
184111 124478
199344 189328
172039 124478
159104 160846
197860 172039
180695 172039
147726 184111
176666 192187
156513 180695
53186 159104
109596 199344
173759 147726
155003 160846
186531 172039
147629 172039
1...

output:

1208
507
9154
54
45
27
67
1321
1910
176574
3
168
5
449
4773
9
19
368
5415
2882
388297
12452
563
0
6
4088
0
2585
660
30
15
30
25
13
87363
26
168
554
729
33
0
454
118
98
17546
169
27
1709
1386
36
14
1178
2110
0
1
0
486
0
891
84975
1091
586
52
138
857
46562
91193
167
21890
31156
33
1575
9024
242
728
22...

result: