UOJ228 基础数据结构练习题题解

题意：

cxy 是一个热爱学习的女孩子，今天她想要学习数据结构技巧。

在看了一些博客学了一些姿势后，她想要找一些数据结构题来练练手。于是她的好朋友 q779 给她出了一道题。

给出一个长度为 $n$ 的数列 $A$，接下来有 $m$ 次操作，操作有三种:

对于所有的 $i \in[l,r]$，将 $A_i$ 变成 $A_i+x$ 。

对于所有的 $i \in[l,r]$，将 $A_i$ 变成 $\left\lfloor\sqrt{A_i}\right\rfloor$ 。

对于所有的 $i \in[l,r]$，询问 $A_i$ 的和。

作为一个不怎么熟练的初学者，cxy 想了好久都没做出来。而可怜酱又外出旅游去了，一时间联系不上。

于是她决定向你寻求帮助：你能帮她解决这个问题吗？

输入格式：

第一行两个数： $n, m$ 。

接下来一行 $n$ 个数 $A_i$ 。

接下来 $m$ 行中, 第 $i$ 行第一个数 $t_i$ 表示操作类型：

若 $t_i=1$, 则接下来三个整数 $l_i, r_i, x_i$ 表示操作一。

若 $t_i=2$, 则接下来三个整数 $l_i, r_i$ 表示操作二。

若 $t_i=3$, 则接下来三个整数 $l_i, r_i$ 表示操作三。

输出格式：

对于每个询问操作，输出一行表示答案。

有了区间加的操作，传统的区间开平方做法就会出现一些问题。如果是维护最大值的，那么很容易就被卡满。

不过区间开平方还有一种维护方式，即通过判断区间满足 $\min = \max$ 从而整个区间都相等。

对于一个全是相等的数的区间，我们可以很容易的通过区间加 $\left\lfloor\sqrt{x}\right\rfloor - x$ 解决

但是有一个特殊的情况，考虑区间 $\{k^2,~k^2-1,~k^2,~\cdots\}$ ，此时 $\max - \min = 1$ 。

而一次操作后得到了 $\{k,~k-1,~k,~\cdots\}$ ，此时仍满足 $\max - \min = 1$ ，只需加上 $k^2 - k$ 即可卡满。

原因在于我们的复杂度是由 $\max - \min$ 单调下降保证的，而这种情况是唯一的特殊情况。特判下就好了。

时间复杂度 $\mathcal{O}(n \log 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 sum,mn,mx,tag; } tr[N * 4];
bool check(int x) { int t = sqrt(x + 0.5); return t * t == x; }
void push_up(int at)
{
    tr[at].sum = tr[ls(at)].sum + tr[rs(at)].sum;
    up(tr[at].mx = tr[ls(at)].mx, tr[rs(at)].mx);
    down(tr[at].mn = tr[ls(at)].mn, tr[rs(at)].mn);
}
void push_down(int l,int r,int at)
{
    if(tr[at].tag)
    {
        int mid = (l + r) >> 1, k = tr[at].tag; tr[at].tag = 0;
        tr[ls(at)].sum += k * (mid - l + 1);
        tr[rs(at)].sum += k * (r - mid);
        tr[ls(at)].mx += k; tr[rs(at)].mx += k;
        tr[ls(at)].mn += k; tr[rs(at)].mn += k;
        tr[ls(at)].tag += k; tr[rs(at)].tag += k;
    }
}
void build(int l = 1,int r = n,int at = 1)
{
    if(l == r) { tr[at] = {a[l], a[l], a[l], 0}; return; }
    int mid = (l + r) >> 1; build(l,mid,ls(at)); build(mid+1,r,rs(at)); push_up(at);
}
void add(int nl,int nr,int k,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr) 
    {
        tr[at].sum += k * (r - l + 1);
        tr[at].mn += k; tr[at].mx += k; tr[at].tag += k; return;
    }
    push_down(l,r,at); int mid = (l + r) >> 1;
    if(nl <= mid) add(nl,nr,k,l,mid,ls(at));
    if(nr > mid) add(nl,nr,k,mid+1,r,rs(at));
    push_up(at);
}
void update(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr)
    {
        if(tr[at].mn == tr[at].mx || (tr[at].mn + 1 == tr[at].mx && check(tr[at].mx)))
            return add(nl,nr,(int)sqrt(tr[at].mn) - tr[at].mn);
    }
    push_down(l,r,at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, min(mid, nr), l, mid, ls(at));
    if(nr > mid) update(max(nl, mid + 1), 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;
    push_down(l,r,at); int mid = (l + r) >> 1, res = 0;
    if(nl <= mid) res += query(nl,nr,l,mid,ls(at));
    if(nr > mid) res += query(nl,nr,mid+1,r,rs(at));
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build();
    for(int op,l,r,x; Q--; )
    {
        cin >> op >> l >> r;
        if(op == 1) {
            cin >> x; add(l,r,x);
        }else if(op == 2) {
            update(l,r);
        }else cout << query(l,r) << '\n';
    }
    return 0;
}