BZOJ 3211: 花神游历各国

一个数n<=10^9 在被sqrt 7次左右就会变成1 所以这题可以用一个并查集维护一段连续为1的数 修改的时候暴力修改 遇到一个为1就直接跳到这段的末尾 查询用一个线段树维护就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

ll a[maxn], t[maxn * 4], n, m, fa[maxn], b[maxn];

ll getfa(ll now)
{
  return (!fa[now]) ? now : (fa[now] = getfa(fa[now]));
}

void build(ll l, ll r, ll now)
{
  if (l == r)
  {
    t[now] = a[l];
    return;
  }
  ll mid = (l + r) / 2;
  build(l, mid, now * 2);
  build(mid + 1, r, now * 2 + 1);
  t[now] = t[now * 2] + t[now * 2 + 1];
}

void modify(ll l, ll r, ll now, ll lr, ll v)
{
  if (l == r)
  {
    t[now] = v;
    return;
  }
  ll mid = (l + r) / 2;
  if (lr <= mid) modify(l, mid, now * 2, lr, v);
  else modify(mid + 1, r, now * 2 + 1, lr, v);
  t[now] = t[now * 2] + t[now * 2 + 1];
}

ll query(ll l, ll r, ll now, ll lf, ll rt)
{
  if (l >= lf && r <= rt) return t[now];
  ll mid = (l + r) / 2, ans = 0;
  if (lf <= mid) ans += query(l, mid, now * 2, lf, rt);
  if (rt >= mid + 1) ans += query(mid + 1, r, now * 2 + 1, lf, rt);
  return ans;
}

ll sq(ll a)
{
  return (ll)floor(sqrt((double)a));
}

void modi(ll l, ll r)
{
  for (ll i = l; i <= r; i = (!b[i]) ? (i + 1) : (getfa(i) + 1))
  {
    if (b[i]) continue;
    a[i] = sq(a[i]);
    modify(1, n, 1, i, a[i]);
    if (a[i] <= 1)
    {
      b[i] = 1;
      if (b[i - 1]) fa[getfa(i - 1)] = i;
      if (b[i + 1]) fa[i] = getfa(i + 1);
    }
  }
}

int main()
{
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
  scanf("%lld", &n);
  for (ll i = 1; i <= n; ++i)
    scanf("%lld", &a[i]);
  build(1, n, 1);
  scanf("%lld", &m);
  for (ll i = 0; i < m; ++i)
  {
    ll x, l, r;
    scanf("%lld%lld%lld", &x, &l, &r);
    if (x == 1) printf("%lld\n", query(1, n, 1, l, r));
    else modi(l, r);
  }
  fclose(stdin);fclose(stdout);
}

发表评论