题目大意：
维护一个长度为n的序列，支持一下两个操作：
1、区间开根号（向下取整）；
2、区间求和。
n<=100000,m<=200000,序列中的数<=10^9且为非负整数。
题目分析：
都这个逼样了还来刷水，我是心大还是脑子进屎呢T_T
区间开根号这个没有什么数据结构维护的了，但是10^9这么大的数开根号5次也就到1了。
所以说线段树维护一下区间和，然后修改就暴力在线段树上改就可以了，对于已经不需要修改的区间打个标记，修改的时候不动就可以了。
时间复杂度O（nlogn），对于所有数修改次数最多不超过5n次，每次修改时间复杂度不超过logn，单次查询logn，所以就是nlogn啦。
没注意非负还T了两发，我真是……
脑子进屎了……
【bzoj|bzoj3211 花神游历各国 线段树】代码如下：
#include
#include
#include
#define N 120000
#define ls(c) (c<<1)
#define rs(c) (c<<1|1)
using namespace std;
typedef long long LL;
int n,m;
int a[N];
struct segment{
int l,r,mark;
LL sum;
}seg[N<<2];
void build_tree(int c,int l,int r)
{
seg[c].l=l,seg[c].r=r;
if(l==r)
{
seg[c].sum=a[l];
seg[c].mark=a[l]<=1;
return;
}
int mid=l+r>>1;
build_tree(ls(c),l,mid);
build_tree(rs(c),mid+1,r);
seg[c].sum=seg[ls(c)].sum+seg[rs(c)].sum;
seg[c].mark=seg[ls(c)].mark&seg[rs(c)].mark;
}
void update(int c,int l,int r)
{
if(seg[c].mark) return;
if(seg[c].l==seg[c].r)
{
seg[c].sum=int(sqrt(seg[c].sum));
seg[c].mark=seg[c].sum<=1;
return;
}
int mid=seg[c].l+seg[c].r>>1;
if(l<=mid) update(ls(c),l,r);
if(r>mid) update(rs(c),l,r);
seg[c].sum=seg[ls(c)].sum+seg[rs(c)].sum;
seg[c].mark=seg[ls(c)].mark&seg[rs(c)].mark;
}
LL query(int c,int l,int r)
{
if(l<=seg[c].l && r>=seg[c].r) return seg[c].sum;
int mid=seg[c].l+seg[c].r>>1;
if(r<=mid) return query(ls(c),l,r);
if(l>mid) return query(rs(c),l,r);
return query(ls(c),l,r)+query(rs(c),l,r);
}
int main()
{
scanf("%d",&n);
for(int i=1;
i<=n;
i++)
scanf("%d",&a[i]);
scanf("%d",&m);
build_tree(1,1,n);
for(int i=1,opt,l,r;
i<=m;
i++)
{
scanf("%d%d%d",&opt,&l,&r);
if(l>r) swap(l,r);
if(opt==1) printf("%lld\n",query(1,l,r));
else update(1,l,r);
}
return 0;
}
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔