【SP2713 GSS4 - Can you answer these queries IV】 题解
2024-08-31 03:17:24
题目链接:https://www.luogu.org/problemnew/show/SP2713
真暴力啊。
开方你开就是了,开上6次就都没了。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 100100;
inline ll read(){
ll k = 0 ; char c = getchar() ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) k = k * 10 + c - 48, c = getchar() ;
return k ;
}
ll n, m, a[maxn], t=0;
class Segment_Tree{
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
public:
ll tree[maxn<<2];
void build(ll l, ll r, ll rt)
{
if(l == r)
{
tree[rt] = a[l];
return;
}
ll mid = (l + r) >> 1;
build(lson);
build(rson);
PushUP(rt);
}
void update(ll left, ll right, ll l, ll r, ll rt)
{
if(left <= l && r <= right)
{
if(tree[rt] <= r - l + 1) return;
else
{
if(l == r)
{
tree[rt] = (ll)sqrt((double)tree[rt]);
return;
}
}
}
ll mid = (l + r) >> 1;
PushUP(rt);
if(left <= mid) update(left, right, lson);
PushUP(rt);
if(right > mid) update(left, right, rson);
PushUP(rt);
}
ll query(ll left, ll right, ll l, ll r, ll rt)
{
ll res = 0;
if(left <= l && right >= r)
{
return tree[rt];
}
ll mid = (l + r) >> 1;
if(left <= mid) res += query(left, right, lson);
if(right > mid) res += query(left, right, rson);
return res;
}
private:
void PushUP(ll rt)
{
tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
}T;
int main()
{
while(~scanf("%lld",&n))
{
t++;
printf("Case #%d:\n",t);
memset(a, 0, sizeof(a));
for(ll i = 1; i <= n; i++)
a[i] = read();
T.build(1,n,1);
m = read();
for(ll i = 1; i <= m; i++)
{
ll opt, x, y;
opt = read();
x = read();
y = read();
if(y < x) swap(x, y);
if(opt == 0)
T.update(x,y,1,n,1);
else
printf("%lld\n",T.query(x,y,1,n,1));
}
}
return 0;
}
最新文章
- bzoj3110
- 书旗小说app点评
- javascript 自调用函数 闭包
- Ubuntu 安装 “宋体,微软雅黑,WPS Office的symbol、wingdings、wingdings 2、wingdings 3、webding字体,Consolas雅黑混合版编程字体” 等 Windows 7 下的字体(转)
- ZK framework on Java
- Mac 安装maven3.3.9
- 如果让莎士比亚、海明威编写JavaScript代码
- VPN各种方案
- Ubuntu 12.04下PHP环境的搭建(LAMP)
- nano使用介绍
- Thinkphp模板简单入门
- shibie
- linux ln 命令使用参数详解(ln -s 软链接)
- DJango 基础 (5)
- javascript promises powered by BlueBird
- 重识linux-linux系统服务相关
- [C#]RichTextBox实现拖放
- 在UTF-8中,一个汉字为什么需要三个字节?(转)
- poj 2185
- Linux下patch的制作和应用