V - Can you answer these queries? HDU - 4027 线段树 暴力
2024-09-07 10:59:01
V - Can you answer these queries?
这个题目开始没什么思路,因为不知道要怎么去区间更新这个开根号。
然后稍微看了一下题解,因为每一个数开根号最多开十几次就变成1了,所以就直接单点更新,但是这个可以剪枝。
如果碰到区间长度和区间大小相同就可以不用更新了。
我也是无语了,想到刚刚的做法之后很好写了,
不过要注意以下x,y 大小可能x>y, 这个bug如果不是之前看题解的时候瞄到了,我可能找不出来了。
因为我写对拍我肯定会保证x<y 的,还是就是注意看清楚题目要求输出一行空行。
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 1e5 + ;
typedef long long ll;
struct node
{
ll len, sum;
}tree[maxn*];
ll a[maxn]; void push_up(int id)
{
tree[id].sum = tree[id << ].sum + tree[id << | ].sum;
} void build(int id,int l,int r)
{
tree[id].len = r - l + ;
if(l==r)
{
tree[id].sum = a[l];
return;
}
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
push_up(id);
} void update(int id,int l,int r,int x,int y)
{
if (x <= l && y >= r && tree[id].len == tree[id].sum) return;
if(l==r)
{
tree[id].sum = sqrt(tree[id].sum);
return;
}
int mid = (l + r) >> ;
if (x <= mid) update(id << , l, mid, x, y);
if (y > mid) update(id << | , mid + , r, x, y);
push_up(id);
} ll query(int id,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return tree[id].sum;
int mid = (l + r) >> ;
ll ans = ;
if (x <= mid) ans += query(id << , l, mid, x, y);
if (y > mid) ans += query(id << | , mid + , r, x, y);
return ans;
} int main()
{
int n, m, cas = ;
while(scanf("%d", &n)!=EOF)
{
for (int i = ; i <= n; i++) scanf("%lld", &a[i]);
build(, , n);
scanf("%d", &m);
cout << "Case #" << cas++ << ":" << endl;
while(m--)
{
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if (x > y) swap(x, y);
if(opt==) update(, , n, x, y);
else
{
ll ans = query(, , n, x, y);
printf("%lld\n", ans);
}
}
printf("\n");
}
return ;
}
线段树
最新文章
- vs默认VS Development Sever和用IIS Web Server的一点差别
- How to configure a static IP address on CentOS 7(CentOS7静态IP地址设置)
- Hadoop日记Day12---MapReduce学习
- Eclipse RCP实用小技巧
- filter,map,reduce,lambda(python3)
- 统计map上的read数量
- QWebView下载文件,QUrl中解析文件名
- Manacher算法 , 实例 详解 . NYOJ 最长回文
- 去除express.js 3.5中报connect.multipart() will be removed in connect 3.0的警告
- paping使用来测试联通&;网站由于tcp协议导致的无法通信问题超时问题
- break退出循环分析
- [Swift]LeetCode926. 将字符串翻转到单调递增 | Flip String to Monotone Increasing
- 每10秒执行定时任务-crontab
- oracle之 反向键索引
- 远程算数程序——版本v1.0
- spring配置文件引入properties文件:<;context:property-placeholder>;标签使用总结
- C#中HttpWebRequest的用法详解
- Codeforces 923 A. Primal Sport
- cocos2d-x 3.0 WIN7+VS2012 安卓平台搭建
- NoSQLUnit