get到了标记永久化
sylvia 是一个热爱学习的女孩子，今天她想要学习数据结构技巧。
在看了一些博客学了一些姿势后，她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。
给出一个长度为 nn 的数列 AA，接下来有 mm 次操作，操作有三种：
- 对于所有的 i∈[l,r]i∈[l,r]，将 AiAi 变成 Ai+xAi+x。
- 对于所有的 i∈[l,r]i∈[l,r]，将 AiAi 变成 ⌊Ai−−√⌋⌊Ai⌋。
- 对于所有的 i∈[l,r]i∈[l,r]，询问 AiAi 的和。
作为一个不怎么熟练的初学者，sylvia 想了好久都没做出来。而可怜酱又外出旅游去了，一时间联系不上。于是她决定向你寻求帮助：你能帮她解决这个问题吗。
输入格式
第一行两个数：n,mn,m。
接下来一行 nn 个数 AiAi。
接下来 mm 行中，第 ii 行第一个数 titi 表示操作类型：
若 ti=1ti=1，则接下来三个整数 li,ri,xili,ri,xi，表示操作一。
若 ti=2ti=2，则接下来三个整数 li,rili,ri，表示操作二。
若 ti=3ti=3，则接下来三个整数 li,rili,ri，表示操作三。
输出格式
对于每个询问操作，输出一行表示答案。
数据范围
对于所有数据，保证有 1≤li≤ri≤n,1≤Ai,xi≤1051≤li≤ri≤n,1≤Ai,xi≤105
时间限制：1s1s
空间限制：256MB
题目分析
考虑只有区间开方和区间求和的操作，那么注意到开根号几次后数就变为1了，于是可以暴力做下去（或者分块弄一弄？）。
然而问题麻烦在于还结合了区间加的操作，于是会出现形如898989->232323->898989的极端数据卡掉暴力区间下爬的方法。
注意到若区间最大值等于区间最小值时就等于区间赋值（或者区间减）操作，并且复杂度最坏的情况只会在最大值与最小值相差1的时候发生。
那么相当于只要在区间开方时特判一下就好了。
（从别人博客get到了永久化标记的写法（据说常数挺小？））
复杂度证明：UOJ 228 基础数据结构练习题
#include<bits/stdc++.h>
typedef long long ll;
const int maxn = ; struct node
{
ll sum,mx,mn,tag;
}f[maxn<<];
int n,m; int read()
{
char ch = getchar();
int num = ;
bool fl = ;
for (; !isdigit(ch); ch = getchar())
if (ch=='-') fl = ;
for (; isdigit(ch); ch = getchar())
num = (num<<)+(num<<)+ch-;
if (fl) num = -num;
return num;
}
void pushup(int rt, int lens)
{
f[rt].sum = f[rt<<].sum+f[rt<<|].sum+1ll*f[rt].tag*lens;
f[rt].mx = std::max(f[rt<<].mx, f[rt<<|].mx)+f[rt].tag;
f[rt].mn = std::min(f[rt<<].mn, f[rt<<|].mn)+f[rt].tag;
}
void tagAdd(int rt, int lens, ll c)
{
f[rt].tag += c, f[rt].mn += c, f[rt].mx += c, f[rt].sum += 1ll*lens*c;
}
void build(int rt, int l, int r)
{
if (l==r){
f[rt].sum = f[rt].mx = f[rt].mn = read();
return;
}
int mid = (l+r)>>;
build(rt<<, l, mid), build(rt<<|, mid+, r);
pushup(rt, r-l+);
}
void updateAdd(int rt, int L, int R, int l, int r, ll c)
{
if (L <= l&&r <= R){
tagAdd(rt, r-l+, c);
return;
}
int mid = (l+r)>>;
if (L <= mid) updateAdd(rt<<, L, R, l, mid, c);
if (R > mid) updateAdd(rt<<|, L, R, mid+, r, c);
pushup(rt, r-l+);
}
void updateSqrt(int rt, int L, int R, int l, int r, ll tag)
{
if (L <= l&&r <= R){
ll s = sqrt(f[rt].mn+tag)+, t = sqrt(f[rt].mx+tag);
if ((f[rt].mx==f[rt].mn)||(f[rt].mx==f[rt].mn+&&s==t)){
tagAdd(rt, r-l+, s--f[rt].mn-tag); //这一步是用来保证复杂度的
return;
}
}
int mid = (l+r)>>;
if (L <= mid) updateSqrt(rt<<, L, R, l, mid, tag+f[rt].tag);
if (R > mid) updateSqrt(rt<<|, L, R, mid+, r, tag+f[rt].tag);
pushup(rt, r-l+);
}
ll query(int rt, int L, int R, int l, int r, ll tag)
{
if (L <= l&&r <= R)
return f[rt].sum+1ll*tag*(r-l+);
int mid = (l+r)>>;
ll ret = ;
if (L <= mid) ret = query(rt<<, L, R, l, mid, tag+f[rt].tag);
if (R > mid) ret += query(rt<<|, L, R, mid+, r, tag+f[rt].tag);
return ret;
}
int main()
{
n = read(), m = read();
build(, , n);
while (m--)
{
int opt = read();
if (opt==){
int l = read(), r = read(), c = read();
updateAdd(, l, r, , n, c);
}
if (opt==){
int l = read(), r = read();
updateSqrt(, l, r, , n, );
}
if (opt==){
int l = read(), r = read();
printf("%lld\n",query(, l, r, , n, ));
}
}
return ;
}
END