#228. 基础数据结构练习题
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，表示操作三。
输出格式
对于每个询问操作，输出一行表示答案。
样例一
input
5 5
1 2 3 4 5
1 3 5 2
2 1 4
3 2 4
2 3 5
3 1 5
output
5
6
inline大法好；
读入优化大法好。
判断区间最小值跟最大值相差1或者0即可；
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-7
#define bug(x) cout<<"bug"<<x<<endl;
const int N=1e5+,M=1e6+,inf=;
const ll INF=1e18+,mod=;
inline ll scan()
{
ll res = , ch ;
while( !( ( ch = getchar() ) >= '' && ch <= '' ) )
{
if( ch == EOF ) return 1LL << ;
}
res = ch - '' ;
while( ( ch = getchar() ) >= '' && ch <= '' )
res = res * + ( ch - '' ) ;
return res ;
}
/// 数组大小
int n;
ll sum[N<<],minn[N<<],maxx[N<<],lazy[N<<],cov[N<<];
inline void pushup(int pos)
{
minn[pos]=min(minn[pos<<],minn[pos<<|]);
maxx[pos]=max(maxx[pos<<|],maxx[pos<<]);
sum[pos]=sum[pos<<]+sum[pos<<|];
}
inline void pushdown(int pos,int l,int r)
{
if(cov[pos])
{
int mid=(l+r)>>;
cov[pos<<]=cov[pos];
cov[pos<<|]=cov[pos];
maxx[pos<<]=cov[pos];
maxx[pos<<|]=cov[pos];
minn[pos<<]=cov[pos];
minn[pos<<|]=cov[pos];
sum[pos<<]=cov[pos]*(mid-l+);
sum[pos<<|]=cov[pos]*(r-mid);
lazy[pos<<]=;
lazy[pos<<|]=;
cov[pos]=;
}
if(lazy[pos])
{
int mid=(l+r)>>;
lazy[pos<<]+=lazy[pos];
lazy[pos<<|]+=lazy[pos];
maxx[pos<<]+=lazy[pos];
maxx[pos<<|]+=lazy[pos];
minn[pos<<]+=lazy[pos];
minn[pos<<|]+=lazy[pos];
sum[pos<<]+=lazy[pos]*(mid-l+);
sum[pos<<|]+=lazy[pos]*(r-mid);
lazy[pos]=;
}
}
inline void build(int l,int r,int pos)
{
lazy[pos]=;
cov[pos]=;
if(l==r)
{
sum[pos]=scan();
minn[pos]=maxx[pos]=sum[pos];
return;
}
int mid=(l+r)>>;
build(l,mid,pos<<);
build(mid+,r,pos<<|);
pushup(pos);
}
inline void update(int L,int R,ll c,int l,int r,int pos)
{
if(L<=l&&r<=R)
{
lazy[pos]+=c;
minn[pos]+=c;
maxx[pos]+=c;
sum[pos]+=c*(r-l+);
return;
}
pushdown(pos,l,r);
int mid=(l+r)>>;
if(L<=mid)update(L,R,c,l,mid,pos<<);
if(R>mid)update(L,R,c,mid+,r,pos<<|);
pushup(pos);
}
inline void update1(int L,int R,ll c,int l,int r,int pos)
{
if(L<=l&&r<=R)
{
cov[pos]=c;
minn[pos]=c;
maxx[pos]=c;
sum[pos]=c*(r-l+);
lazy[pos]=;
return;
}
pushdown(pos,l,r);
int mid=(l+r)>>;
if(L<=mid)update1(L,R,c,l,mid,pos<<);
if(R>mid)update1(L,R,c,mid+,r,pos<<|);
pushup(pos);
}
inline void update2(int L,int R,int l,int r,int pos)
{
if(l==L&&R==r&&maxx[pos]==minn[pos])
{
ll x=(ll)floor(sqrt(maxx[pos]));
update1(L,R,x,,n,);
return;
}
if(l==L&&R==r&&maxx[pos]==minn[pos]+)
{
ll x=(ll)floor(sqrt(maxx[pos]));
ll y=(ll)floor(sqrt(minn[pos]));
if(x==y)update1(L,R,x,,n,);
else update(L,R,x-maxx[pos],,n,);
return;
}
pushdown(pos,l,r);
int mid=(l+r)>>;
if(R<=mid)update2(L,R,l,mid,pos<<);
else if(L>mid)update2(L,R,mid+,r,pos<<|);
else
{
update2(L,mid,l,mid,pos<<);
update2(mid+,R,mid+,r,pos<<|);
}
pushup(pos);
}
inline ll query(int L,int R,int l,int r,int pos)
{
if(L<=l&&r<=R)return sum[pos];
pushdown(pos,l,r);
int mid=(l+r)>>;
ll ans=;
if(L<=mid)ans+=query(L,R,l,mid,pos<<);
if(R>mid)ans+=query(L,R,mid+,r,pos<<|);
return ans;
}
int main()
{
int m;
n=scan();
m=scan();
build(,n,);
while(m--)
{
int t,l,r;
t=scan();
l=scan();
r=scan();
if(t==)
{
ll x;
x=scan();
update(l,r,x,,n,);
}
else if(t==) update2(l,r,,n,);
else printf("%lld\n",query(l,r,,n,));
}
return ;
}