BZOJ 3211 花神游历各国

Description

Input

Output

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

Sample Input

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

Sample Output

101
11
11

题解

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

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

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

用一个flag标记是否不变

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#ifndef LL
#define LL long long
#endif
#define lch l, m, rt << 1
#define rch m + 1, r, rt << 1 | 1
const int N = 100005;
LL Sum[N << 2];
bool flag[N << 2];
void PushUp(int rt)
{
    Sum[rt] = Sum[rt << 1] + Sum[rt << 1 | 1];
    flag[rt] = flag[rt << 1] & flag[rt << 1 | 1];
}
void buildtree(int l, int r, int rt)
{
    if(l == r)
    {
        scanf("%lld", &Sum[rt]);
        if(Sum[rt] <= 1)
            flag[rt] = 1;
        return;
    }
    int m = l + r >> 1;
    buildtree(lch);
    buildtree(rch);
    PushUp(rt);
}
void Update(int L, int R, int l, int r, int rt)
{
    if(flag[rt])
        return;
    if(l == r)
    {
        Sum[rt] = sqrt(Sum[rt]);
        if(Sum[rt] <= 1)
            flag[rt] = 1;
        return;
    }
    int m = l + r >> 1;
    if (L <= m) Update(L, R, lch);
    if (R > m) Update(L, R, rch);
    PushUp(rt);
}
LL Query(int L, int R, int l, int r, int rt)
{
    if(L <= l && R >= r)
        return Sum[rt];
    int m = l + r >> 1;
    LL ans = 0;
    if (L <= m) ans += Query(L, R, lch);
    if (R > m) ans += Query(L, R, rch);
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
    buildtree(1, n, 1);
    int m;
    scanf("%d", &m);
    while (m--)
    {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if(l > r)
            swap(l, r);
        if (op == 1)
        {
            printf("%lld\n", Query(l, r, 1, n, 1));
        }
        else
            Update(l, r, 1, n, 1);
    }
}