[BZOJ3211] 꽃신이 여러 나라의 세력 라인 나무를 거닐다
5713 단어 세그먼트 트리
/**************************************************************
Problem: 3211
User: di4CoveRy
Language: C++
Result: Accepted
Time:2164 ms
Memory:7928 kb
****************************************************************/
#include
#include
#include
#define N 100050
#define COUT "%lld
"
using namespace std;
long long ans;
struct Tree{long long sum,b;}tree[N*4];
int d[N],n,m;
Tree merge(Tree p1,Tree p2)
{
Tree tmp;
tmp.sum = p1.sum + p2.sum;
tmp.b = p1.b + p2.b;
return tmp;
}
void build(int l,int r,int t)
{
if (l == r)
{
tree[t].sum = 1LL * d[l];
tree[t].b = 1;
return ;
}
int mid = (l + r) / 2;
build(l,mid,2*t);
build(mid+1,r,2*t+1);
tree[t] = merge(tree[2*t],tree[2*t+1]);
}
int ll,rr;
void update(int l,int r,int t)
{
if (l > rr || r < ll) return ;
if (l >= ll && r <= rr && tree[t].b == 0) return ;
if (l >= ll && r <= rr && l == r)
{
tree[t].sum = 1LL * sqrt(tree[t].sum);
if (tree[t].sum <= 1) tree[t].b = 0;else tree[t].b = 1;
return ;
}
int mid = (l + r) / 2;
update(l,mid,2*t);
update(mid+1,r,2*t+1);
tree[t] = merge(tree[2*t],tree[2*t+1]);
}
void query(int l,int r,int t)
{
if (l > rr || r < ll) return ;
if (l >= ll && r <= rr) {ans += tree[t].sum; return ;}
int mid = (l+r) / 2;
query(l,mid,2*t);
query(mid+1,r,2*t+1);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&d[i]);
build(1,n,1);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int cmd = 0;
scanf("%d%d%d",&cmd,&ll,&rr);
if (cmd == 2) update(1,n,1);
if (cmd == 1)
{
ans = 0LL;
query(1,n,1);
printf(COUT,ans);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 알고리즘 14427번 : 수열과 쿼리 15길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.