SPOJ2713GSS4 - Can you answer these queries I…
2018-09-05 07:43:08来源:博客园 阅读 ()
题意
Sol
讲过无数次了。。很显然,一个$10^12$的数开方不超过$8$次后就会变为$1$
因此直接暴力更改即可,维护一下这段区间是否被全改为了$1$
双倍经验:https://www.luogu.org/problemnew/show/P4145
#include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<cmath> #define int long long #define Pair pair<int, int> #define fi first #define se second #define MP(x, y) make_pair(x, y) using namespace std; const int MAXN = 1e6 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; int a[MAXN]; #define ls k << 1 #define rs k << 1 | 1 struct Node { int l, r, w, f; }T[MAXN]; void update(int k) { if(T[ls].f && T[rs].f) T[k].f = 1; T[k].w = T[ls].w + T[rs].w; } void Build(int k, int ll, int rr) { T[k] = (Node) {ll, rr}; if(ll == rr) { T[k].w = a[ll]; return ; } int mid = ll + rr >> 1; Build(ls, ll, mid); Build(rs, mid + 1, rr); update(k); } void push(int k) { if(T[k].f) return ; if(T[k].l == T[k].r) { T[k].w = sqrt(T[k].w); if(T[k].w == 1) T[k].f = 1; return ; } push(ls); push(rs); update(k); } void IntSqrt(int k, int ll, int rr) { if(ll <= T[k].l && T[k].r <= rr) { if(T[k].f) return ; push(k); return ; } int mid = T[k].l + T[k].r >> 1; if(ll <= mid) IntSqrt(ls, ll, rr); if(rr > mid) IntSqrt(rs, ll, rr); update(k); } int IntSum(int k, int ll, int rr) { if(ll <= T[k].l && T[k].r <= rr) return T[k].w; int mid = T[k].l + T[k].r >> 1; if(ll > mid) return IntSum(rs, ll, rr); else if(rr <= mid) return IntSum(ls, ll, rr); else return IntSum(ls, ll, rr) + IntSum(rs, ll, rr); } main() { int tot = 0; while(scanf("%d", &N) != EOF) { printf("Case #%d:\n", ++tot); for(int i = 1; i <= N; i++) a[i] = read(); Build(1, 1, N); M = read(); while(M--) { int k = read(), l = read(), r = read(); if(l > r) swap(l, r); if(k == 0) IntSqrt(1, l, r); else printf("%lld\n", IntSum(1, l, r)); } puts(""); } return 0; } /* */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C++ 学习笔记 (八)重载 重写 重定义以及名字覆盖
下一篇:采药---背包动规
- C++ non-const lvalue reference cannot bind to a temporar 2020-03-09
- 洛谷P1014 Cantor表 2020-02-06
- Can you answer these queries III 2019-08-16
- C/C++的几个输入流 2019-08-16
- Linux下QT、cannot find -lGL、 2019-01-21
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash