#228. 基础数据结构练习题
题目链接：http://uoj.ac/problem/228
Solution
这题由于有区间+操作，所以和花神还是不一样的。 花神那道题，我们可以考虑每个数最多开根几次就会成1，而这个必须利用开根的性质
我们维护区间最大、最小、和。区间加操作可以直接做。
区间开方操作需要特殊考虑。
首先对于一个区间，如果这个区间的所有数取$x=left lfloor sqrt{x} ight floor$值一样，那么就可以直接区间覆盖。
分析上述过程，一个区间可以直接覆盖，当这个区间的差值满足一个特定的范围。 而每次开方这个差值就会减少，可以证明这样开方$lg^{2}$次就会全部为1
所以剩下的我们就可递归下去。
这样的话，区间+操作，就相当于重置了这个差值，所以复杂度还是科学的。
但是有一种情况出现问题。
上述是每次开方后，差值减小，但是有开方后差值不变的情况。 例如 3 4 3 4 3 4 3 4
即$a$,$b$当$b$为完全平方数，$a=b-1$时。这样开方完差值还是1，然后区间+2就又变回来了。 这样上述就卡成了暴力。
那么我们把这种情况特殊考虑。 这样可以转化为一个区间－的操作。剩下的暴力递归，这样就可以了。
时间复杂度是$O(NlogNlg^2{N})$
Code
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } #define MAXN 100010 int N,M,a[MAXN]; namespace SegmentTree { struct SegmentTreeNode{int l,r,cov; LL tag,sum,maxx,minx;}tree[MAXN<<2]; #define ls now<<1 #define rs now<<1|1 inline void Update(int now) { tree[now].sum=tree[ls].sum+tree[rs].sum; tree[now].maxx=max(tree[ls].maxx,tree[rs].maxx); tree[now].minx=min(tree[ls].minx,tree[rs].minx); } inline void cover(int now,int D) { tree[now].cov=D; tree[now].tag=0; tree[now].minx=tree[now].maxx=D; tree[now].sum=D*(tree[now].r-tree[now].l+1); } inline void modify(int now,LL D) { tree[now].tag+=D; tree[now].minx+=D; tree[now].maxx+=D; tree[now].sum+=(tree[now].r-tree[now].l+1)*D; } inline void PushDown(int now) { if (tree[now].l==tree[now].r) return; if (tree[now].cov!=-1) cover(ls,tree[now].cov),cover(rs,tree[now].cov),tree[now].cov=-1; if (tree[now].tag!=0) modify(ls,tree[now].tag),modify(rs,tree[now].tag),tree[now].tag=0; } inline void BuildTree(int now,int l,int r) { tree[now].l=l; tree[now].r=r; tree[now].cov=-1; if (l==r) {tree[now].sum=tree[now].maxx=tree[now].minx=a[l]; return;} int mid=(l+r)>>1; BuildTree(ls,l,mid); BuildTree(rs,mid+1,r); Update(now); } inline void Modify(int now,int L,int R,int D) { int l=tree[now].l,r=tree[now].r; PushDown(now); if (L<=l && R>=r) {modify(now,D); return;} int mid=(l+r)>>1; if (L<=mid) Modify(ls,L,R,D); if (R>mid) Modify(rs,L,R,D); Update(now); } inline void Change(int now,int L,int R) { int l=tree[now].l,r=tree[now].r; PushDown(now); if (L<=l && R>=r) { if ((int)sqrt(tree[now].maxx)==(int)sqrt(tree[now].minx)) {cover(now,(int)sqrt(tree[now].maxx)); return;} if (tree[now].maxx==tree[now].minx+1) {modify(now,(int)sqrt(tree[now].minx)-tree[now].minx); return;} if (l!=r) Change(ls,L,R),Change(rs,L,R); Update(now); return; } int mid=(l+r)>>1; if (L<=mid) Change(ls,L,R); if (R>mid) Change(rs,L,R); Update(now); } inline LL Query(int now,int L,int R) { int l=tree[now].l,r=tree[now].r; PushDown(now); if (L<=l && R>=r) return tree[now].sum; int mid=(l+r)>>1; LL re=0; if (L<=mid) re+=Query(ls,L,R); if (R>mid) re+=Query(rs,L,R); return re; } } int main() { N=read(),M=read(); for (int i=1; i<=N; i++) a[i]=read(); SegmentTree::BuildTree(1,1,N); while (M--) { int opt=read(),l=read(),r=read(),D; switch (opt) { case 1: D=read(),SegmentTree::Modify(1,l,r,D); break; case 2: SegmentTree::Change(1,l,r); break; case 3: printf("%lld ",SegmentTree::Query(1,l,r)); break; } // for (int i=1; i<=N; i++) printf("%d ",SegmentTree::Query(1,i,i)); puts("================="); } return 0; }