BZOJ 3211 花神游历各国

Description#

1(16).jpg

Input#

2(5).jpg

Output#

每次x=1时，每行一个整数，表示这次旅行的开心度

Sample Input#

Sample Output#

题解#

本题和上帝造题的七分钟是一样的

但我的程序没有过啊
打的比较傻

其实只要维护一个值就可以了

用一个flag标记是否不变

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <cmath>
5
using namespace std;
6
#ifndef LL
7
#define LL long long
8
#endif
9
#define lch l, m, rt << 1
10
#define rch m + 1, r, rt << 1 | 1
11
const int N = 100005;
12
LL Sum[N << 2];
13
bool flag[N << 2];
14
void PushUp(int rt)
15
{
16
  Sum[rt] = Sum[rt << 1] + Sum[rt << 1 | 1];
17
  flag[rt] = flag[rt << 1] & flag[rt << 1 | 1];
18
}
19
void buildtree(int l, int r, int rt)
20
{
21
  if(l == r)
22
  {
23
    scanf("%lld", &Sum[rt]);
24
    if(Sum[rt] <= 1)
25
      flag[rt] = 1;
26
    return;
27
  }
28
  int m = l + r >> 1;
29
  buildtree(lch);
30
  buildtree(rch);
31
  PushUp(rt);
32
}
33
void Update(int L, int R, int l, int r, int rt)
34
{
35
  if(flag[rt])
36
    return;
37
  if(l == r)
38
  {
39
    Sum[rt] = sqrt(Sum[rt]);
40
    if(Sum[rt] <= 1)
41
      flag[rt] = 1;
42
    return;
43
  }
44
  int m = l + r >> 1;
45
  if (L <= m) Update(L, R, lch);
46
  if (R > m) Update(L, R, rch);
47
  PushUp(rt);
48
}
49
LL Query(int L, int R, int l, int r, int rt)
50
{
51
  if(L <= l && R >= r)
52
    return Sum[rt];
53
  int m = l + r >> 1;
54
  LL ans = 0;
55
  if (L <= m) ans += Query(L, R, lch);
56
  if (R > m) ans += Query(L, R, rch);
57
  return ans;
58
}
59
int main()
60
{
61
  int n;
62
  scanf("%d", &n);
63
  buildtree(1, n, 1);
64
  int m;
65
  scanf("%d", &m);
66
  while (m--)
67
  {
68
    int op, l, r;
69
    scanf("%d%d%d", &op, &l, &r);
70
    if(l > r)
71
      swap(l, r);
72
    if (op == 1)
73
    {
74
      printf("%lld\n", Query(l, r, 1, n, 1));
75
    }
76
    else
77
      Update(l, r, 1, n, 1);
78
  }
79
}