SP2713 GSS4 - Can you answer these queries IV 题解

题目链接：SP2713 GSS4 - Can you answer these queries IV

题意：

维护一个数据结构，支持：

1. 0 x y 把区间 \([x,y]\) 内的每个数开方，下取整
2. 1 x y 询问区间 \([x,y]\) 的每个数的和

有多组数据，数据以EOF结束，对于每组数据，输出数据的序号，每组数据之后输出一个空行。

不保证给出的区间\([x, y]\) 有 \(x \le y\) ，如果 \(x>y\) 请交换 \(x,y\) 。

数据范围：

\(1 \le n,m \le 10^5, \sum a_i \le 10^{18}\)

区间开平方还是比较经典的。因为 \(\sqrt{a + b} \not\Leftrightarrow \sqrt{a} + \sqrt{b}\) ，即开方不具有传递性，

所以我们只能暴力修改。但是因为 \(\sqrt{1} = 1\) ，且 \(\left\lfloor\sqrt[T]{10^{18}}\right\rfloor = 1\) ，其中 \(T \le 20\)

因此一些修改是没有意义的。怎么维护一个区间没有必要再次开方呢？显然是区间最大值为 \(1\) 。

时间复杂度 \(\mathcal{O}(\sum n \log \sum n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n,Q,a[N];
struct node { int mx,sum; } tr[N * 4];
void push_up(int at)
{
    up(tr[at].mx = tr[ls(at)].mx, tr[rs(at)].mx);
    tr[at].sum = tr[ls(at)].sum + tr[rs(at)].sum;
}
void build(int l = 1,int r = n,int at = 1)
{
    if(l == r) { return tr[at] = {a[l], a[l]}, void(0); }
    int mid = (l + r) >> 1; build(l,mid,ls(at)); build(mid+1,r,rs(at)); push_up(at);
}
void update(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(l == r)
    { 
        tr[at].mx = sqrt(tr[at].mx);
        tr[at].sum = sqrt(tr[at].sum); return;
    }
    int mid = (l + r) >> 1;
    if(nl <= mid && tr[ls(at)].mx > 1) update(nl, nr, l, mid, ls(at));
    if(nr > mid && tr[rs(at)].mx > 1) update(nl, nr, mid + 1, r, rs(at));
    push_up(at);
}
int query(int nl,int nr,int l = 1, int r = n,int at = 1)
{
    if(nl <= l && r <= nr) { return tr[at].sum; }
    int mid = (l + r) >> 1;
    if(nl > mid) return query(nl, nr, mid + 1, r, rs(at));
    if(nr <= mid) return query(nl, nr, l, mid, ls(at));
    return query(nl, nr, l, mid, ls(at)) + query(nl, nr, mid + 1, r, rs(at));
}
void clear() {}
void check(int &x,int &y) { (x > y) ? swap(x,y) : void(0); }
void solve(int Case)
{
    clear(); cout << "Case #" << Case << ":\n";
    for(int i = 1; i <= n; i++) cin >> a[i];
    cin >> Q; build();
    for(int op,x,y; Q--; )
    {
        if(cin >> op, op == 0) {
            cin >> x >> y; check(x,y); update(x,y);
        }else {
            cin >> x >> y; check(x,y); cout << query(x,y) << '\n';
        }
    } cout << "\n\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    for(int i = 1; cin >> n; i++) solve(i);
    return 0;
}