正文
【BZOJ3211&3038】花神游历各国&上帝造题的七分钟2(CodeVS)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Description Input Output每次x=1时,每行一个整数,表示这次旅行的开心度
Sample Input41 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output10111
11
HINT对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9
SourceSPOJ2713 gss4 数据已加强
思路:线段树并不能区间开方,但直接暴力修改是会超时的,只要加入一点点优化:若是该区间值为0||1那么就不必再修改了,注意也需要左右子树得出父节点。
上帝造题的七分钟2:不保证l<r,然后再加上读入和输出优化,还有开!long!long!少开long long 弄得我百思不得其解。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define MAXN 100000
using namespace std;
long long lazy[MAXN*],a[MAXN],b[MAXN*];
long long segtree[MAXN*];
int n,m;
long long getin()
{
char ch = getchar();
long long data = ;
while (ch < '' || ch > '')
ch = getchar();
do
{
data = data* + ch-'';
ch = getchar();
} while (ch >= '' && ch <= '');
return data;
}
void putout(long long t){
long long ans[]={},i=;
for(;t;t/=) ans[++i]=t%;
for(;i;i--) putchar(''+ans[i]);
putchar('\n');
}
void adddata(int now)
{
segtree[now]=segtree[(now<<)]+segtree[(now<<)+];
}
void buildtree(int now,int l,int r)
{
if (l==r) {segtree[now]=a[l]; if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
buildtree((now<<),l,mid);
buildtree((now<<)+,mid+,r);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
long long query(int now,int l,int r,int begin,int end)
{
if (begin<=l && end>=r) return segtree[now];
long long mid=(l+r)>>,ans=;
if (begin<=mid) ans+=query((now<<),l,mid,begin,end);
if (end>mid) ans+=query((now<<)+,mid+,r,begin,end);
return ans;
}
void intchange(int now,int l,int r,int begin,int end)
{
if (b[now]==) return;
if (l==r) {segtree[now]=floor(sqrt(segtree[now])); if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
if (begin<=mid) intchange((now<<),l,mid,begin,end);
if (end>mid) intchange((now<<)+,mid+,r,begin,end);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
int main()
{
int i;
long long x,y,z;
n=getin();
for (i=;i<=n;i++) a[i]=getin();
buildtree(,,n);
m=getin();
for (i=;i<=m;i++)
{
x=getin();
y=getin();
z=getin();
if (y>z) swap(y,z);
if (x==) putout(query(,,n,y,z));
else intchange(,,n,y,z);
}
return ;
}
【BZOJ3211&3038】花神游历各国&上帝造题的七分钟2(CodeVS)的更多相关文章- 【BZOJ 3211&;3038】 花神游历各国 &; 上帝造题的七分钟2
[题目链接] [BZOJ 3211] 点击打开链接 [BZOJ 3038] 点击打开链接 [算法] 线段树 开根操作直接开到叶子节点,注意当区间中所有数都是0或1时,不需要开根 [代码] #inclu ...
- bzoj3211花神游历各国&;&;bzoj3038上帝造题的七分钟2*
bzoj3211花神游历各国 题意: n个数的序列,m个操作,操作两种:区间开根(向下取整)和区间求和.n≤100000,m≤200000,序列中的数非负且≤109. 题解: 一个≤109的数开6次根 ...
- BZOJ 3038: 上帝造题的七分钟2 / BZOJ 3211: 花神游历各国 (线段树区间开平方)
题意 给出一些数,有两种操作.(1)将区间内每一个数开方(2)查询每一段区间的和 分析 普通的线段树保留修改+开方优化.可以知道当一个数为0或1时,无论开方几次,答案仍然相同.所以设置flag=1变表 ...
- 【bzoj3211】花神游历各国&;&;【bzoj3038】上帝造题的七分钟2
bzoj3038]上帝造题的七分钟2 Description XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. “第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟, ...
- GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 (线段树)
GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 GSS4 - Can you answer these qu ...
- 题解 洛谷 P4145 【上帝造题的七分钟2 / 花神游历各国】
题目 上帝造题的七分钟2 / 花神游历各国 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. ...
- [bzoj3038/3211]上帝造题的七分钟2/花神游历各国_线段树
上帝造题的七分钟2 bzoj-3038 题目大意:给定一个序列,支持:区间开方:查询区间和. 注释:$1\le n\le 10^5$,$1\le val[i] \le 10^{12}$. 想法:这题还 ...
- 洛谷P4145 上帝造题的七分钟2/花神游历各国 [树状数组,并查集]
题目传送门 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是 ...
- 洛谷P4145——上帝造题的七分钟2 / 花神游历各国
题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是便有了对一段 ...
随机推荐- 安装Visual Studio的插件AnkhSvn
安装Visual Studio的插件AnkhSvn 安装AnkhSvn(VS插件).下载地址:http://download.csdn.net/detail/luqingfei/4538807 Ank ...
- String高效编程优化(Java)
1, substring截取超大字符串可能造成的“内存泄漏” 2,+ 操作符的优化和局限 3,StringBuilder和StringBuffer 4,split和StringTokenizer做简单 ...
- lunux下查看文件文件夹大小的命令
使用ls -lht命令显示当前目录下的所有文件,其中有一列就是显示这个文件的大小.如果要看一个文件夹的大小,可以用du -sh *
- 简单的网页采集程序(ASP.NET MVC4)
因为懒人太多,造成现在网页数据采集非常的流行,我也来写个简单的记录一下. 之前写了MVC的基本框架的搭建随笔,后面因为公司太忙,个人感情问题:(,导致不想写了,就写了两篇给删除了,现在就搁浅了, 本人 ...
- TreeView绑定无限层级关系类
protected void Page_Load(object sender, EventArgs e) { if (!IsPostBack) { Bind_TV(TreeView1.Nodes); ...
- Django+Xadmin+Echarts动态获取数据legend颜色显示灰色问题已解决
前段时间做的使用Django的Xadmin后台和百度Echarts进行后台数据可视化,功能虽然实现,展示出来的legend图例,都是灰色的,只有鼠标放上去才会显示彩色的.百度都快被我刨穿了,看到有类似 ...
- java面试笔试题收集
转载过来看看.... J2SE基础 1. 九种基本数据类型的大小,以及他们的封装类. 2. Switch能否用string做参数? 可以 3. equals与==的区别. 4. Object有哪些公用 ...
- SQL---->;数据库表设计思想
数据,一对多: 多的表中加外健约束 数据,多对多: 创建中间表,中间表中有关系对应的外健约束 数据一对一: 主从关系,从表中加外健约束,加唯一约束,加非空约束!!!!! 一张表中-自连接:(理论可以, ...
- scrollHieght、offsetHeight、clientHeight、width、height
1.scroll滚动(scrollTop.Left.Height.Width) scroll()当用户滚动指定的元素时,会发生 scroll 滚动事件: scrollWidth.scrollHeigh ...
- WSDL协议简单介绍
WSDL – WebService Description Language – Web服务描述语言 通过XML形式说明服务在什么地方-地址. 通过XML形式说明服务提供什么样的方法 – 如何调用. ...
Output每次x=1时,每行一个整数,表示这次旅行的开心度
Sample Input41 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output10111
11
HINT对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9
SourceSPOJ2713 gss4 数据已加强
思路:线段树并不能区间开方,但直接暴力修改是会超时的,只要加入一点点优化:若是该区间值为0||1那么就不必再修改了,注意也需要左右子树得出父节点。
上帝造题的七分钟2:不保证l<r,然后再加上读入和输出优化,还有开!long!long!少开long long 弄得我百思不得其解。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define MAXN 100000
using namespace std;
long long lazy[MAXN*],a[MAXN],b[MAXN*];
long long segtree[MAXN*];
int n,m;
long long getin()
{
char ch = getchar();
long long data = ;
while (ch < '' || ch > '')
ch = getchar();
do
{
data = data* + ch-'';
ch = getchar();
} while (ch >= '' && ch <= '');
return data;
}
void putout(long long t){
long long ans[]={},i=;
for(;t;t/=) ans[++i]=t%;
for(;i;i--) putchar(''+ans[i]);
putchar('\n');
}
void adddata(int now)
{
segtree[now]=segtree[(now<<)]+segtree[(now<<)+];
}
void buildtree(int now,int l,int r)
{
if (l==r) {segtree[now]=a[l]; if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
buildtree((now<<),l,mid);
buildtree((now<<)+,mid+,r);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
long long query(int now,int l,int r,int begin,int end)
{
if (begin<=l && end>=r) return segtree[now];
long long mid=(l+r)>>,ans=;
if (begin<=mid) ans+=query((now<<),l,mid,begin,end);
if (end>mid) ans+=query((now<<)+,mid+,r,begin,end);
return ans;
}
void intchange(int now,int l,int r,int begin,int end)
{
if (b[now]==) return;
if (l==r) {segtree[now]=floor(sqrt(segtree[now])); if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
if (begin<=mid) intchange((now<<),l,mid,begin,end);
if (end>mid) intchange((now<<)+,mid+,r,begin,end);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
int main()
{
int i;
long long x,y,z;
n=getin();
for (i=;i<=n;i++) a[i]=getin();
buildtree(,,n);
m=getin();
for (i=;i<=m;i++)
{
x=getin();
y=getin();
z=getin();
if (y>z) swap(y,z);
if (x==) putout(query(,,n,y,z));
else intchange(,,n,y,z);
}
return ;
}
【BZOJ3211&3038】花神游历各国&上帝造题的七分钟2(CodeVS)的更多相关文章- 【BZOJ 3211&;3038】 花神游历各国 &; 上帝造题的七分钟2
[题目链接] [BZOJ 3211] 点击打开链接 [BZOJ 3038] 点击打开链接 [算法] 线段树 开根操作直接开到叶子节点,注意当区间中所有数都是0或1时,不需要开根 [代码] #inclu ...
- bzoj3211花神游历各国&;&;bzoj3038上帝造题的七分钟2*
bzoj3211花神游历各国 题意: n个数的序列,m个操作,操作两种:区间开根(向下取整)和区间求和.n≤100000,m≤200000,序列中的数非负且≤109. 题解: 一个≤109的数开6次根 ...
- BZOJ 3038: 上帝造题的七分钟2 / BZOJ 3211: 花神游历各国 (线段树区间开平方)
题意 给出一些数,有两种操作.(1)将区间内每一个数开方(2)查询每一段区间的和 分析 普通的线段树保留修改+开方优化.可以知道当一个数为0或1时,无论开方几次,答案仍然相同.所以设置flag=1变表 ...
- 【bzoj3211】花神游历各国&;&;【bzoj3038】上帝造题的七分钟2
bzoj3038]上帝造题的七分钟2 Description XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. “第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟, ...
- GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 (线段树)
GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 GSS4 - Can you answer these qu ...
- 题解 洛谷 P4145 【上帝造题的七分钟2 / 花神游历各国】
题目 上帝造题的七分钟2 / 花神游历各国 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. ...
- [bzoj3038/3211]上帝造题的七分钟2/花神游历各国_线段树
上帝造题的七分钟2 bzoj-3038 题目大意:给定一个序列,支持:区间开方:查询区间和. 注释:$1\le n\le 10^5$,$1\le val[i] \le 10^{12}$. 想法:这题还 ...
- 洛谷P4145 上帝造题的七分钟2/花神游历各国 [树状数组,并查集]
题目传送门 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是 ...
- 洛谷P4145——上帝造题的七分钟2 / 花神游历各国
题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是便有了对一段 ...
随机推荐- 安装Visual Studio的插件AnkhSvn
安装Visual Studio的插件AnkhSvn 安装AnkhSvn(VS插件).下载地址:http://download.csdn.net/detail/luqingfei/4538807 Ank ...
- String高效编程优化(Java)
1, substring截取超大字符串可能造成的“内存泄漏” 2,+ 操作符的优化和局限 3,StringBuilder和StringBuffer 4,split和StringTokenizer做简单 ...
- lunux下查看文件文件夹大小的命令
使用ls -lht命令显示当前目录下的所有文件,其中有一列就是显示这个文件的大小.如果要看一个文件夹的大小,可以用du -sh *
- 简单的网页采集程序(ASP.NET MVC4)
因为懒人太多,造成现在网页数据采集非常的流行,我也来写个简单的记录一下. 之前写了MVC的基本框架的搭建随笔,后面因为公司太忙,个人感情问题:(,导致不想写了,就写了两篇给删除了,现在就搁浅了, 本人 ...
- TreeView绑定无限层级关系类
protected void Page_Load(object sender, EventArgs e) { if (!IsPostBack) { Bind_TV(TreeView1.Nodes); ...
- Django+Xadmin+Echarts动态获取数据legend颜色显示灰色问题已解决
前段时间做的使用Django的Xadmin后台和百度Echarts进行后台数据可视化,功能虽然实现,展示出来的legend图例,都是灰色的,只有鼠标放上去才会显示彩色的.百度都快被我刨穿了,看到有类似 ...
- java面试笔试题收集
转载过来看看.... J2SE基础 1. 九种基本数据类型的大小,以及他们的封装类. 2. Switch能否用string做参数? 可以 3. equals与==的区别. 4. Object有哪些公用 ...
- SQL---->;数据库表设计思想
数据,一对多: 多的表中加外健约束 数据,多对多: 创建中间表,中间表中有关系对应的外健约束 数据一对一: 主从关系,从表中加外健约束,加唯一约束,加非空约束!!!!! 一张表中-自连接:(理论可以, ...
- scrollHieght、offsetHeight、clientHeight、width、height
1.scroll滚动(scrollTop.Left.Height.Width) scroll()当用户滚动指定的元素时,会发生 scroll 滚动事件: scrollWidth.scrollHeigh ...
- WSDL协议简单介绍
WSDL – WebService Description Language – Web服务描述语言 通过XML形式说明服务在什么地方-地址. 通过XML形式说明服务提供什么样的方法 – 如何调用. ...
每次x=1时,每行一个整数,表示这次旅行的开心度
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output10111
11
HINT对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9
SourceSPOJ2713 gss4 数据已加强
思路:线段树并不能区间开方,但直接暴力修改是会超时的,只要加入一点点优化:若是该区间值为0||1那么就不必再修改了,注意也需要左右子树得出父节点。
上帝造题的七分钟2:不保证l<r,然后再加上读入和输出优化,还有开!long!long!少开long long 弄得我百思不得其解。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define MAXN 100000
using namespace std;
long long lazy[MAXN*],a[MAXN],b[MAXN*];
long long segtree[MAXN*];
int n,m;
long long getin()
{
char ch = getchar();
long long data = ;
while (ch < '' || ch > '')
ch = getchar();
do
{
data = data* + ch-'';
ch = getchar();
} while (ch >= '' && ch <= '');
return data;
}
void putout(long long t){
long long ans[]={},i=;
for(;t;t/=) ans[++i]=t%;
for(;i;i--) putchar(''+ans[i]);
putchar('\n');
}
void adddata(int now)
{
segtree[now]=segtree[(now<<)]+segtree[(now<<)+];
}
void buildtree(int now,int l,int r)
{
if (l==r) {segtree[now]=a[l]; if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
buildtree((now<<),l,mid);
buildtree((now<<)+,mid+,r);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
long long query(int now,int l,int r,int begin,int end)
{
if (begin<=l && end>=r) return segtree[now];
long long mid=(l+r)>>,ans=;
if (begin<=mid) ans+=query((now<<),l,mid,begin,end);
if (end>mid) ans+=query((now<<)+,mid+,r,begin,end);
return ans;
}
void intchange(int now,int l,int r,int begin,int end)
{
if (b[now]==) return;
if (l==r) {segtree[now]=floor(sqrt(segtree[now])); if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
if (begin<=mid) intchange((now<<),l,mid,begin,end);
if (end>mid) intchange((now<<)+,mid+,r,begin,end);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
int main()
{
int i;
long long x,y,z;
n=getin();
for (i=;i<=n;i++) a[i]=getin();
buildtree(,,n);
m=getin();
for (i=;i<=m;i++)
{
x=getin();
y=getin();
z=getin();
if (y>z) swap(y,z);
if (x==) putout(query(,,n,y,z));
else intchange(,,n,y,z);
}
return ;
}
【BZOJ3211&3038】花神游历各国&上帝造题的七分钟2(CodeVS)的更多相关文章- 【BZOJ 3211&;3038】 花神游历各国 &; 上帝造题的七分钟2
[题目链接] [BZOJ 3211] 点击打开链接 [BZOJ 3038] 点击打开链接 [算法] 线段树 开根操作直接开到叶子节点,注意当区间中所有数都是0或1时,不需要开根 [代码] #inclu ...
- bzoj3211花神游历各国&;&;bzoj3038上帝造题的七分钟2*
bzoj3211花神游历各国 题意: n个数的序列,m个操作,操作两种:区间开根(向下取整)和区间求和.n≤100000,m≤200000,序列中的数非负且≤109. 题解: 一个≤109的数开6次根 ...
- BZOJ 3038: 上帝造题的七分钟2 / BZOJ 3211: 花神游历各国 (线段树区间开平方)
题意 给出一些数,有两种操作.(1)将区间内每一个数开方(2)查询每一段区间的和 分析 普通的线段树保留修改+开方优化.可以知道当一个数为0或1时,无论开方几次,答案仍然相同.所以设置flag=1变表 ...
- 【bzoj3211】花神游历各国&;&;【bzoj3038】上帝造题的七分钟2
bzoj3038]上帝造题的七分钟2 Description XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. “第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟, ...
- GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 (线段树)
GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 GSS4 - Can you answer these qu ...
- 题解 洛谷 P4145 【上帝造题的七分钟2 / 花神游历各国】
题目 上帝造题的七分钟2 / 花神游历各国 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. ...
- [bzoj3038/3211]上帝造题的七分钟2/花神游历各国_线段树
上帝造题的七分钟2 bzoj-3038 题目大意:给定一个序列,支持:区间开方:查询区间和. 注释:$1\le n\le 10^5$,$1\le val[i] \le 10^{12}$. 想法:这题还 ...
- 洛谷P4145 上帝造题的七分钟2/花神游历各国 [树状数组,并查集]
题目传送门 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是 ...
- 洛谷P4145——上帝造题的七分钟2 / 花神游历各国
题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是便有了对一段 ...
随机推荐- 安装Visual Studio的插件AnkhSvn
安装Visual Studio的插件AnkhSvn 安装AnkhSvn(VS插件).下载地址:http://download.csdn.net/detail/luqingfei/4538807 Ank ...
- String高效编程优化(Java)
1, substring截取超大字符串可能造成的“内存泄漏” 2,+ 操作符的优化和局限 3,StringBuilder和StringBuffer 4,split和StringTokenizer做简单 ...
- lunux下查看文件文件夹大小的命令
使用ls -lht命令显示当前目录下的所有文件,其中有一列就是显示这个文件的大小.如果要看一个文件夹的大小,可以用du -sh *
- 简单的网页采集程序(ASP.NET MVC4)
因为懒人太多,造成现在网页数据采集非常的流行,我也来写个简单的记录一下. 之前写了MVC的基本框架的搭建随笔,后面因为公司太忙,个人感情问题:(,导致不想写了,就写了两篇给删除了,现在就搁浅了, 本人 ...
- TreeView绑定无限层级关系类
protected void Page_Load(object sender, EventArgs e) { if (!IsPostBack) { Bind_TV(TreeView1.Nodes); ...
- Django+Xadmin+Echarts动态获取数据legend颜色显示灰色问题已解决
前段时间做的使用Django的Xadmin后台和百度Echarts进行后台数据可视化,功能虽然实现,展示出来的legend图例,都是灰色的,只有鼠标放上去才会显示彩色的.百度都快被我刨穿了,看到有类似 ...
- java面试笔试题收集
转载过来看看.... J2SE基础 1. 九种基本数据类型的大小,以及他们的封装类. 2. Switch能否用string做参数? 可以 3. equals与==的区别. 4. Object有哪些公用 ...
- SQL---->;数据库表设计思想
数据,一对多: 多的表中加外健约束 数据,多对多: 创建中间表,中间表中有关系对应的外健约束 数据一对一: 主从关系,从表中加外健约束,加唯一约束,加非空约束!!!!! 一张表中-自连接:(理论可以, ...
- scrollHieght、offsetHeight、clientHeight、width、height
1.scroll滚动(scrollTop.Left.Height.Width) scroll()当用户滚动指定的元素时,会发生 scroll 滚动事件: scrollWidth.scrollHeigh ...
- WSDL协议简单介绍
WSDL – WebService Description Language – Web服务描述语言 通过XML形式说明服务在什么地方-地址. 通过XML形式说明服务提供什么样的方法 – 如何调用. ...
11
11
对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9
SourceSPOJ2713 gss4 数据已加强
思路:线段树并不能区间开方,但直接暴力修改是会超时的,只要加入一点点优化:若是该区间值为0||1那么就不必再修改了,注意也需要左右子树得出父节点。
上帝造题的七分钟2:不保证l<r,然后再加上读入和输出优化,还有开!long!long!少开long long 弄得我百思不得其解。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define MAXN 100000
using namespace std;
long long lazy[MAXN*],a[MAXN],b[MAXN*];
long long segtree[MAXN*];
int n,m;
long long getin()
{
char ch = getchar();
long long data = ;
while (ch < '' || ch > '')
ch = getchar();
do
{
data = data* + ch-'';
ch = getchar();
} while (ch >= '' && ch <= '');
return data;
}
void putout(long long t){
long long ans[]={},i=;
for(;t;t/=) ans[++i]=t%;
for(;i;i--) putchar(''+ans[i]);
putchar('\n');
}
void adddata(int now)
{
segtree[now]=segtree[(now<<)]+segtree[(now<<)+];
}
void buildtree(int now,int l,int r)
{
if (l==r) {segtree[now]=a[l]; if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
buildtree((now<<),l,mid);
buildtree((now<<)+,mid+,r);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
long long query(int now,int l,int r,int begin,int end)
{
if (begin<=l && end>=r) return segtree[now];
long long mid=(l+r)>>,ans=;
if (begin<=mid) ans+=query((now<<),l,mid,begin,end);
if (end>mid) ans+=query((now<<)+,mid+,r,begin,end);
return ans;
}
void intchange(int now,int l,int r,int begin,int end)
{
if (b[now]==) return;
if (l==r) {segtree[now]=floor(sqrt(segtree[now])); if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
if (begin<=mid) intchange((now<<),l,mid,begin,end);
if (end>mid) intchange((now<<)+,mid+,r,begin,end);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
int main()
{
int i;
long long x,y,z;
n=getin();
for (i=;i<=n;i++) a[i]=getin();
buildtree(,,n);
m=getin();
for (i=;i<=m;i++)
{
x=getin();
y=getin();
z=getin();
if (y>z) swap(y,z);
if (x==) putout(query(,,n,y,z));
else intchange(,,n,y,z);
}
return ;
}
【BZOJ3211&3038】花神游历各国&上帝造题的七分钟2(CodeVS)的更多相关文章- 【BZOJ 3211&;3038】 花神游历各国 &; 上帝造题的七分钟2
[题目链接] [BZOJ 3211] 点击打开链接 [BZOJ 3038] 点击打开链接 [算法] 线段树 开根操作直接开到叶子节点,注意当区间中所有数都是0或1时,不需要开根 [代码] #inclu ...
- bzoj3211花神游历各国&;&;bzoj3038上帝造题的七分钟2*
bzoj3211花神游历各国 题意: n个数的序列,m个操作,操作两种:区间开根(向下取整)和区间求和.n≤100000,m≤200000,序列中的数非负且≤109. 题解: 一个≤109的数开6次根 ...
- BZOJ 3038: 上帝造题的七分钟2 / BZOJ 3211: 花神游历各国 (线段树区间开平方)
题意 给出一些数,有两种操作.(1)将区间内每一个数开方(2)查询每一段区间的和 分析 普通的线段树保留修改+开方优化.可以知道当一个数为0或1时,无论开方几次,答案仍然相同.所以设置flag=1变表 ...
- 【bzoj3211】花神游历各国&;&;【bzoj3038】上帝造题的七分钟2
bzoj3038]上帝造题的七分钟2 Description XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. “第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟, ...
- GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 (线段树)
GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 GSS4 - Can you answer these qu ...
- 题解 洛谷 P4145 【上帝造题的七分钟2 / 花神游历各国】
题目 上帝造题的七分钟2 / 花神游历各国 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. ...
- [bzoj3038/3211]上帝造题的七分钟2/花神游历各国_线段树
上帝造题的七分钟2 bzoj-3038 题目大意:给定一个序列,支持:区间开方:查询区间和. 注释:$1\le n\le 10^5$,$1\le val[i] \le 10^{12}$. 想法:这题还 ...
- 洛谷P4145 上帝造题的七分钟2/花神游历各国 [树状数组,并查集]
题目传送门 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是 ...
- 洛谷P4145——上帝造题的七分钟2 / 花神游历各国
题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是便有了对一段 ...
随机推荐- 安装Visual Studio的插件AnkhSvn
安装Visual Studio的插件AnkhSvn 安装AnkhSvn(VS插件).下载地址:http://download.csdn.net/detail/luqingfei/4538807 Ank ...
- String高效编程优化(Java)
1, substring截取超大字符串可能造成的“内存泄漏” 2,+ 操作符的优化和局限 3,StringBuilder和StringBuffer 4,split和StringTokenizer做简单 ...
- lunux下查看文件文件夹大小的命令
使用ls -lht命令显示当前目录下的所有文件,其中有一列就是显示这个文件的大小.如果要看一个文件夹的大小,可以用du -sh *
- 简单的网页采集程序(ASP.NET MVC4)
因为懒人太多,造成现在网页数据采集非常的流行,我也来写个简单的记录一下. 之前写了MVC的基本框架的搭建随笔,后面因为公司太忙,个人感情问题:(,导致不想写了,就写了两篇给删除了,现在就搁浅了, 本人 ...
- TreeView绑定无限层级关系类
protected void Page_Load(object sender, EventArgs e) { if (!IsPostBack) { Bind_TV(TreeView1.Nodes); ...
- Django+Xadmin+Echarts动态获取数据legend颜色显示灰色问题已解决
前段时间做的使用Django的Xadmin后台和百度Echarts进行后台数据可视化,功能虽然实现,展示出来的legend图例,都是灰色的,只有鼠标放上去才会显示彩色的.百度都快被我刨穿了,看到有类似 ...
- java面试笔试题收集
转载过来看看.... J2SE基础 1. 九种基本数据类型的大小,以及他们的封装类. 2. Switch能否用string做参数? 可以 3. equals与==的区别. 4. Object有哪些公用 ...
- SQL---->;数据库表设计思想
数据,一对多: 多的表中加外健约束 数据,多对多: 创建中间表,中间表中有关系对应的外健约束 数据一对一: 主从关系,从表中加外健约束,加唯一约束,加非空约束!!!!! 一张表中-自连接:(理论可以, ...
- scrollHieght、offsetHeight、clientHeight、width、height
1.scroll滚动(scrollTop.Left.Height.Width) scroll()当用户滚动指定的元素时,会发生 scroll 滚动事件: scrollWidth.scrollHeigh ...
- WSDL协议简单介绍
WSDL – WebService Description Language – Web服务描述语言 通过XML形式说明服务在什么地方-地址. 通过XML形式说明服务提供什么样的方法 – 如何调用. ...
SPOJ2713 gss4 数据已加强
思路:线段树并不能区间开方,但直接暴力修改是会超时的,只要加入一点点优化:若是该区间值为0||1那么就不必再修改了,注意也需要左右子树得出父节点。
上帝造题的七分钟2:不保证l<r,然后再加上读入和输出优化,还有开!long!long!少开long long 弄得我百思不得其解。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define MAXN 100000
using namespace std;
long long lazy[MAXN*],a[MAXN],b[MAXN*];
long long segtree[MAXN*];
int n,m;
long long getin()
{
char ch = getchar();
long long data = ;
while (ch < '' || ch > '')
ch = getchar();
do
{
data = data* + ch-'';
ch = getchar();
} while (ch >= '' && ch <= '');
return data;
}
void putout(long long t){
long long ans[]={},i=;
for(;t;t/=) ans[++i]=t%;
for(;i;i--) putchar(''+ans[i]);
putchar('\n');
}
void adddata(int now)
{
segtree[now]=segtree[(now<<)]+segtree[(now<<)+];
}
void buildtree(int now,int l,int r)
{
if (l==r) {segtree[now]=a[l]; if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
buildtree((now<<),l,mid);
buildtree((now<<)+,mid+,r);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
long long query(int now,int l,int r,int begin,int end)
{
if (begin<=l && end>=r) return segtree[now];
long long mid=(l+r)>>,ans=;
if (begin<=mid) ans+=query((now<<),l,mid,begin,end);
if (end>mid) ans+=query((now<<)+,mid+,r,begin,end);
return ans;
}
void intchange(int now,int l,int r,int begin,int end)
{
if (b[now]==) return;
if (l==r) {segtree[now]=floor(sqrt(segtree[now])); if (segtree[now]== || segtree[now]==) b[now]=; return;}
int mid=(l+r)>>;
if (begin<=mid) intchange((now<<),l,mid,begin,end);
if (end>mid) intchange((now<<)+,mid+,r,begin,end);
adddata(now);
b[now]=b[(now<<)]&b[(now<<)+];
}
int main()
{
int i;
long long x,y,z;
n=getin();
for (i=;i<=n;i++) a[i]=getin();
buildtree(,,n);
m=getin();
for (i=;i<=m;i++)
{
x=getin();
y=getin();
z=getin();
if (y>z) swap(y,z);
if (x==) putout(query(,,n,y,z));
else intchange(,,n,y,z);
}
return ;
}
- 【BZOJ 3211&;3038】 花神游历各国 &; 上帝造题的七分钟2
[题目链接] [BZOJ 3211] 点击打开链接 [BZOJ 3038] 点击打开链接 [算法] 线段树 开根操作直接开到叶子节点,注意当区间中所有数都是0或1时,不需要开根 [代码] #inclu ...
- bzoj3211花神游历各国&;&;bzoj3038上帝造题的七分钟2*
bzoj3211花神游历各国 题意: n个数的序列,m个操作,操作两种:区间开根(向下取整)和区间求和.n≤100000,m≤200000,序列中的数非负且≤109. 题解: 一个≤109的数开6次根 ...
- BZOJ 3038: 上帝造题的七分钟2 / BZOJ 3211: 花神游历各国 (线段树区间开平方)
题意 给出一些数,有两种操作.(1)将区间内每一个数开方(2)查询每一段区间的和 分析 普通的线段树保留修改+开方优化.可以知道当一个数为0或1时,无论开方几次,答案仍然相同.所以设置flag=1变表 ...
- 【bzoj3211】花神游历各国&;&;【bzoj3038】上帝造题的七分钟2
bzoj3038]上帝造题的七分钟2 Description XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. “第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟, ...
- GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 (线段树)
GSS4 - Can you answer these queries IV || luogu4145上帝造题的七分钟2 / 花神游历各国 GSS4 - Can you answer these qu ...
- 题解 洛谷 P4145 【上帝造题的七分钟2 / 花神游历各国】
题目 上帝造题的七分钟2 / 花神游历各国 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. ...
- [bzoj3038/3211]上帝造题的七分钟2/花神游历各国_线段树
上帝造题的七分钟2 bzoj-3038 题目大意:给定一个序列,支持:区间开方:查询区间和. 注释:$1\le n\le 10^5$,$1\le val[i] \le 10^{12}$. 想法:这题还 ...
- 洛谷P4145 上帝造题的七分钟2/花神游历各国 [树状数组,并查集]
题目传送门 题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是 ...
- 洛谷P4145——上帝造题的七分钟2 / 花神游历各国
题目背景 XLk觉得<上帝造题的七分钟>不太过瘾,于是有了第二部. 题目描述 "第一分钟,X说,要有数列,于是便给定了一个正整数数列. 第二分钟,L说,要能修改,于是便有了对一段 ...
随机推荐- 安装Visual Studio的插件AnkhSvn
安装Visual Studio的插件AnkhSvn 安装AnkhSvn(VS插件).下载地址:http://download.csdn.net/detail/luqingfei/4538807 Ank ...
- String高效编程优化(Java)
1, substring截取超大字符串可能造成的“内存泄漏” 2,+ 操作符的优化和局限 3,StringBuilder和StringBuffer 4,split和StringTokenizer做简单 ...
- lunux下查看文件文件夹大小的命令
使用ls -lht命令显示当前目录下的所有文件,其中有一列就是显示这个文件的大小.如果要看一个文件夹的大小,可以用du -sh *
- 简单的网页采集程序(ASP.NET MVC4)
因为懒人太多,造成现在网页数据采集非常的流行,我也来写个简单的记录一下. 之前写了MVC的基本框架的搭建随笔,后面因为公司太忙,个人感情问题:(,导致不想写了,就写了两篇给删除了,现在就搁浅了, 本人 ...
- TreeView绑定无限层级关系类
protected void Page_Load(object sender, EventArgs e) { if (!IsPostBack) { Bind_TV(TreeView1.Nodes); ...
- Django+Xadmin+Echarts动态获取数据legend颜色显示灰色问题已解决
前段时间做的使用Django的Xadmin后台和百度Echarts进行后台数据可视化,功能虽然实现,展示出来的legend图例,都是灰色的,只有鼠标放上去才会显示彩色的.百度都快被我刨穿了,看到有类似 ...
- java面试笔试题收集
转载过来看看.... J2SE基础 1. 九种基本数据类型的大小,以及他们的封装类. 2. Switch能否用string做参数? 可以 3. equals与==的区别. 4. Object有哪些公用 ...
- SQL---->;数据库表设计思想
数据,一对多: 多的表中加外健约束 数据,多对多: 创建中间表,中间表中有关系对应的外健约束 数据一对一: 主从关系,从表中加外健约束,加唯一约束,加非空约束!!!!! 一张表中-自连接:(理论可以, ...
- scrollHieght、offsetHeight、clientHeight、width、height
1.scroll滚动(scrollTop.Left.Height.Width) scroll()当用户滚动指定的元素时,会发生 scroll 滚动事件: scrollWidth.scrollHeigh ...
- WSDL协议简单介绍
WSDL – WebService Description Language – Web服务描述语言 通过XML形式说明服务在什么地方-地址. 通过XML形式说明服务提供什么样的方法 – 如何调用. ...
安装Visual Studio的插件AnkhSvn 安装AnkhSvn(VS插件).下载地址:http://download.csdn.net/detail/luqingfei/4538807 Ank ...
1, substring截取超大字符串可能造成的“内存泄漏” 2,+ 操作符的优化和局限 3,StringBuilder和StringBuffer 4,split和StringTokenizer做简单 ...
使用ls -lht命令显示当前目录下的所有文件,其中有一列就是显示这个文件的大小.如果要看一个文件夹的大小,可以用du -sh *
因为懒人太多,造成现在网页数据采集非常的流行,我也来写个简单的记录一下. 之前写了MVC的基本框架的搭建随笔,后面因为公司太忙,个人感情问题:(,导致不想写了,就写了两篇给删除了,现在就搁浅了, 本人 ...
protected void Page_Load(object sender, EventArgs e) { if (!IsPostBack) { Bind_TV(TreeView1.Nodes); ...
前段时间做的使用Django的Xadmin后台和百度Echarts进行后台数据可视化,功能虽然实现,展示出来的legend图例,都是灰色的,只有鼠标放上去才会显示彩色的.百度都快被我刨穿了,看到有类似 ...
转载过来看看.... J2SE基础 1. 九种基本数据类型的大小,以及他们的封装类. 2. Switch能否用string做参数? 可以 3. equals与==的区别. 4. Object有哪些公用 ...
数据,一对多: 多的表中加外健约束 数据,多对多: 创建中间表,中间表中有关系对应的外健约束 数据一对一: 主从关系,从表中加外健约束,加唯一约束,加非空约束!!!!! 一张表中-自连接:(理论可以, ...
1.scroll滚动(scrollTop.Left.Height.Width) scroll()当用户滚动指定的元素时,会发生 scroll 滚动事件: scrollWidth.scrollHeigh ...
WSDL – WebService Description Language – Web服务描述语言 通过XML形式说明服务在什么地方-地址. 通过XML形式说明服务提供什么样的方法 – 如何调用. ...