QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386249#7453. rplexqalpha1022TL 807ms39952kbC++143.2kb2024-04-11 14:32:542024-04-11 14:32:55

Judging History

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

  • [2024-04-11 14:32:55]
  • 评测
  • 测评结果:TL
  • 用时:807ms
  • 内存:39952kb
  • [2024-04-11 14:32:54]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e5;
const int B = 500;
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];
bool heavy[N + 5];
void dfs1(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), dfs1(v), siz[u] += siz[v];
  sort(ch[u].begin(), ch[u].end(), [](int x, int y) { return siz[x] > siz[y]; });
  for (int i = 0; i < B && i < ch[u].size(); ++i) heavy[ch[u][i]] = 1;
}
struct SqrtDecomposition {
  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, int, int>> qry[N + 5];

void dfs2(int u) {
  for (auto &[l, r, id, pre0, pre1] : qry[u]) pre0 = sd.query(l, r);
  if (heavy[u])
    for (auto &[l, r, id, pre0, pre1] : qry[fa[u]]) pre1 = sd.query(l, r);
  sd.update(u, 1);
  for (int v : ch[u]) dfs2(v);
  for (auto &[l, r, id, pre0, pre1] : qry[u]) {
    int tmp = sd.query(l, r) - pre0;
    ans[id] += (ll)tmp * (tmp - 1) / 2;
  }
  if (heavy[u])
    for (auto &[l, r, id, pre0, pre1] : qry[fa[u]]) {
      int tmp = sd.query(l, r) - pre1;
      ans[id] -= (ll)tmp * (tmp - 1) / 2;
    }
}

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);
  }
  dfs1(rt);
  for (int i = 1; i <= m; ++i) {
    int l, r, u; scanf("%d%d%d", &l, &r, &u), qry[u].emplace_back(l, r, i, 0, 0);
  }
  sd.init(n), dfs2(rt);
  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(), [&](const tuple<int, int, int, int, int> &a, const tuple<int, int, 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]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 17876kb

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: 4ms
memory: 17952kb

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: 0
Accepted
time: 276ms
memory: 39952kb

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:

ok 200000 numbers

Test #4:

score: 0
Accepted
time: 807ms
memory: 39304kb

input:

200000 200000 30609
170171 175523
175437 175523
38764 170171
151317 175523
120732 175437
170236 38764
192246 170236
148014 175523
170214 175523
174149 120732
177275 175523
172858 170171
192655 38764
156503 175523
180293 170214
162551 175523
144233 170171
150893 174149
107574 170171
177524 151317
161...

output:

19739
252249
253552
198701
316493
39544
273230
838431
126153
11216
35898
958434407
13123
14420
1
287730
438527
8116
3647487
671435
13122
5937
300
90
11833
114824
39321
7304
50301
175918
602062
97772162
12682
249
380315
510366
496238
3913170
4540
175512
571292
249060
3994808431
52833
7258777324
44901...

result:

ok 200000 numbers

Test #5:

score: -100
Time Limit Exceeded

input:

200000 200000 180733
188782 186482
190313 186482
122261 186482
177117 190313
182123 122261
190242 186482
130129 122261
198934 186482
194104 190242
184586 177117
193228 182123
158179 186482
186306 190313
152183 158179
192614 194104
197754 198934
119863 193228
189652 190313
189229 177117
192940 197754...

output:


result: