【BZOJ】【3211】花神游历各国
2024-10-18 00:45:44
线段树/暴力
线段树区间开方
唉,我傻逼了一下,TLE了一发,因为没考虑到0的情况……
好吧简单来说一下,线段树动态查询区间和大家都会做……比较麻烦的是这次的修改变成开方了,然而这并没有什么好虚的,注意到权值的范围是$10^9$,我们随手打个表可以发现,对$10^9$不断开根的结果是:1000000000,31622,177,13,3,1。也就是说,每个数,它开根的次数并没有多少(联想一下CF 250的那道区间取模的题!)所以我们维护一个区间最大值,每次暴力对每个数开根就可以了(如果区间最大值为0或1就可以跳过咯)
/**************************************************************
Problem: 3211
User: Tunix
Language: C++
Result: Accepted
Time:1276 ms
Memory:6364 kb
****************************************************************/ //BZOJ 3211
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e5+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/ int n,m,a[N],mx[N<<];
LL sm[N<<];
#define L (o<<1)
#define R (o<<1|1)
#define mid (l+r>>1)
void maintain(int o){
mx[o]=max(mx[L],mx[R]);
sm[o]=sm[L]+sm[R];
}
void build(int o,int l,int r){
if (l==r){mx[o]=sm[o]=a[l];}
else{
build(L,l,mid);
build(R,mid+,r);
maintain(o);
}
}
void update(int o,int l,int r,int ql,int qr){
if (mx[o]== || mx[o]==) return;
if (l==r){mx[o]=sm[o]=sqrt(mx[o]);}
else{
if (ql<=mid) update(L,l,mid,ql,qr);
if (qr>mid) update(R,mid+,r,ql,qr);
maintain(o);
}
}
LL ans;
void query(int o,int l,int r,int ql,int qr){
if (ql<=l && qr>=r) ans+=sm[o];
else{
if (ql<=mid) query(L,l,mid,ql,qr);
if (qr>mid) query(R,mid+,r,ql,qr);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("3211.in","r",stdin);
freopen("3211.out","w",stdout);
#endif
n=getint();
F(i,,n) a[i]=getint();
build(,,n);
m=getint();
F(i,,m){
int cmd=getint(),l=getint(),r=getint();
if (cmd==){
ans=;
query(,,n,l,r);
printf("%lld\n",ans);
}else update(,,n,l,r);
}
return ;
}
3211: 花神游历各国
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 1327 Solved: 511
[Submit][Status][Discuss]
Description
Input
Output
每次x=1时,每行一个整数,表示这次旅行的开心度
Sample Input
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output
101
11
11
11
11
HINT
对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9
Source
最新文章
- MongoDB-基础-limit-skip-sort
- activiti 里面各个方法理解
- Xamarin开发Android笔记:背景操作
- Spring 之autowired
- Xcode6与Xcode5中沙盒的变动以及偏好设置目录的变动
- hdu 4035 Maze 概率DP
- Mosquitto安装_Ubuntu/Debian上安装消息队列Mosquitto
- CodeForces 22C System Administrator
- maven构建这么慢,怎么改变?
- 通过VMware安装Linux操作系统
- python DNS域名轮询业务监控
- 稍微记录下Django2.2使用MariaDB和MySQL遇到的坑
- mybatis LIKE动态参数 sql语句
- visualization of filters keras 基于Keras的卷积神经网络(CNN)可视化
- css--父元素塌陷
- FI-盘盈盘亏借贷科目
- CodeForces - 939A,解题报告
- 第五篇: 路由网关(zuul)
- c3p0死锁
- Atcoder 水题选做
热门文章
- IntellijIDEA快速入门(Windows版)
- csdn 音乐 怎么拦截 提交后的程序 csdn 栏目 音乐 csdn 添加 音乐
- BZOJ.2668.[CQOI2012]交换棋子(费用流zkw)
- markdown编辑器使用指南
- 20172308《Java软件结构与数据结构》第一周学习总结
- 如何利用JS判断当前来路域名并跳转到指定页面
- NAS系统收集
- Mac 10.12使用free命令(fish)
- 用SWD调试接口测量代码运行时间 ( SWO )
- Maven编译时跳过Test