【題目描述】

花神喜歡步行游歷各國，順便虐爆各地競賽。花神有一條游覽路線，它是線型的，也就是說，所有游歷國家呈一條線的形狀排列，花神對每個國家都有一個喜歡程度（當然花神并不一定喜歡所有國家）。

每一次旅行中，花神會選擇一條旅游路線，它在那一串國家中是連續的一段，這次旅行帶來的開心值是這些國家的喜歡度的總和，當然花神對這些國家的喜歡程序并不是恒定的，有時會突然對某些國家產生反感，使他對這些國家的喜歡度變為 （可能是花神虐爆了那些國家的 OI，從而感到乏味）。

現在給出花神每次的旅行路線，以及開心度的變化，請求出花神每次旅行的開心值。

【Input】

第一行是一個整數?NN，表示有?NN?個國家；

第二行有?NN?個空格隔開的整數，表示每個國家的初始喜歡度；

第三行是一個整數?MM，表示有?MM?條信息要處理；

第四行到最后，每行三個整數?x,l,rx,l,r，當?x = 1時詢問游歷國家?ll?到?rr?的開心值總和，就是 ?，當?x = 2 時國家?ll?到?rr?中每個國家的喜歡度變為 。

【Output】

每次?x=1 時，每行一個整數。表示這次旅行的開心度。

【Sample Input】

4 1 100 5 5 5 1 1 2 2 1 2 1 1 2 2 2 3 1 1 4

【Sample Output】

101 11 11

【Data range & Tips】

對于全部數據，

注：建議使用 sqrt 函數，且向下取整。

【Solution】

沒跑滿，然后過了（神奇）！

區間修改時不打懶標記，把區間內每個葉子節點都遍歷（我不知道開根號怎么打懶標記）

然后有個小優化：

維護maxn記錄當前區間最大的數，因為1,0開方和原值一樣，所以當時就return;

【Code】

#include<iostream> #include<cstdio> #include<cmath> using namespace std; struct Segment_Tree{long long sum,maxn; }tree[1000000]; int n,m,a[100100],op,ll,rr; inline void build(int k,int l,int r){if(l==r){tree[k].sum=a[l];tree[k].maxn=a[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn); } inline void modify(int k,int l,int r,int x,int y){if(l>y||r<x)return;if(tree[k].maxn<=1)return;if(l==r){tree[k].sum=floor(sqrt(tree[k].sum));tree[k].maxn=tree[k].sum;return;}int mid=(l+r)>>1;if(x<=mid)modify(k<<1,l,mid,x,y);if(y>mid)modify(k<<1|1,mid+1,r,x,y);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn); } inline long long Ask(int k,int l,int r,int x,int y){if(l>y||r<x)return 0;if(l>=x&&r<=y)return tree[k].sum;int mid=(l+r)>>1;long long res=0;if(x<=mid)res+=Ask(k<<1,l,mid,x,y);if(y>mid)res+=Ask(k<<1|1,mid+1,r,x,y);return res; } int main(){scanf("%d",&n);for(register int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);scanf("%d",&m);for(register int i=1;i<=m;i++){scanf("%d%d%d",&op,&ll,&rr);if(op==1){printf("%lld\n",Ask(1,1,n,ll,rr)); }else{modify(1,1,n,ll,rr);}}return 0; }

總結

以上是生活随笔為你收集整理的ybt.1550 花神游历各国 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。