题目大意:hdu 4027 Can you answer these queries?
题目大意:给定一个长度为N的序列,Q次操作,0 l r:将区间l r之间的数开根;1 l r:查询l r之间数的和。
解题思路:这题看上去是一道线段树,其实它就是一道线段树,只不过不用想的太复杂,因为开根的趋近1的速度非常快,所以每个节点只要标记区间内元素是否相同即可。复杂度妥妥的。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100000;
int N, Q;
ll P[maxn + 5];
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2];
ll s[maxn << 2], v[maxn << 2];
inline void maintain(int u, ll d) {
v[u] = d;
s[u] = d * (rc[u] - lc[u] + 1);
}
inline void pushup(int u) {
s[u] = s[lson(u)] + s[rson(u)];
v[u] = (v[lson(u)] == v[rson(u)] ? v[lson(u)] : 0);
}
inline void pushdown(int u) {
if (v[u]) {
maintain(lson(u), v[u]);
maintain(rson(u), v[u]);
v[u] = 0;
}
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
if (l == r) {
v[u] = s[u] = P[l];
return;
}
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r) {
if (l <= lc[u] && rc[u] <= r && v[u]) {
maintain(u, (ll)sqrt((double)v[u]));
return;
}
pushdown(u);
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
modify(lson(u), l, r);
if (r > mid)
modify(rson(u), l, r);
pushup(u);
}
ll query(int u, int l, int r) {
if (l <= lc[u] && rc[u] <= r)
return s[u];
pushdown(u);
ll ret = 0;
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
ret += query(lson(u), l, r);
if (r > mid)
ret += query(rson(u), l, r);
pushup(u);
return ret;
}
int main () {
int kcas = 1;
while (scanf("%d", &N) == 1) {
for (int i = 1; i <= N; i++)
scanf("%I64d", &P[i]);
build(1, 1, N);
printf("Case #%d:\n", kcas++);
int t, l, r;
scanf("%d", &Q);
while (Q--) {
scanf("%d%d%d", &t, &l, &r);
if (l > r)
swap(l, r);
if (t)
printf("%I64d\n", query(1, l, r));
else
modify(1, l, r);
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
NULL 博文链接:https://128kj.iteye.com/blog/1738772
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。