[BZOJ3211] 꽃신이 여러 나라의 세력 라인 나무를 거닐다

5713 단어 세그먼트 트리
세력선 트리 유지보수 구간이 1이 아닌 원소 수량은 원소가 1이 아닌 구간의 폭력에 대한 귀속 수정
/**************************************************************
    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; }

좋은 웹페이지 즐겨찾기