傳送門：QAQQAQ

?

題意：有一個數組a和一個數組k，數組a一直保持一個性質：a[i + 1] >= a[i] + k[i]。有兩種操作：1，給某個元素加上x，但是加上之后要保持數組a的性質。比如a[i]加上x之后，a[i + 1]<a[i] + k[i],那么a[i + 1]就變成a[i] + k[i]，否則不變。同理，若a[i + 2]小于了現在的a[i + 1] + k[i + 1]，那么a[i + 2]也變成a[i + 1] + k[i + 1]，一直保持這個性質。第二章操作，詢問數組a的區間[l, r]的區間和。

?

思路：用另一個b數組保存a[i]-（k[1]+k[2]+...+k[i-1]），這樣由題意的大小關系可知，b數組是非遞減的。所以更新是只需在b[x]加上y用二分找出一段連續的需要被修改的區間即可，為節省時間，k應該用前綴和形式保存。

　　查詢時，只需利用b數組建造線段樹并維護，求區間sum并加上之前每個b[i]被減掉的k即可，為節省時間，可以再前綴和k的基礎上再加一個前綴和kk。這樣查詢時只需求query(1,1,n,l,r)+kk[r-1]-kk[l-2]。

注意：b數組只在建線段樹時用到，因為后面b不再被更新，需要用query求出最新的b數組里的值； 賦值懶標記tag時一定要賦值成數據無法觸碰到的值INF，否則會出現無法pushdown的情況（之前賦值成-1，在第7個點上調了老半天）。

1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=200001; 5 const ll inf=-1e18; 6 7 ll n,a[N],b[N],k[N],kk[N],m; 8 9 ll sum[N<<2],tag[N<<2]; 10 void build(int x,int l,int r) 11 { 12 if(l==r) 13 { 14 sum[x]=b[l]; 15 return; 16 } 17 int mid=(l+r)>>1; 18 build(x+x,l,mid); 19 build(x+x+1,mid+1,r); 20 sum[x]=sum[x+x]+sum[x+x+1]; 21 } 22 23 void push_down(int x,int l,int r) 24 { 25 int mid=(l+r)>>1; 26 if(tag[x]==inf) return; 27 tag[x+x]=tag[x]; tag[x+x+1]=tag[x]; 28 sum[x+x]=tag[x]*(mid-l+1); 29 sum[x+x+1]=tag[x]*(r-mid); 30 tag[x]=inf; 31 } 32 33 void update(int x,int l,int r,int L,int R,ll val) 34 { 35 if(L<=l&&r<=R) 36 { 37 tag[x]=val; 38 sum[x]=val*(r-l+1); 39 return; 40 } 41 int mid=(l+r)>>1; 42 push_down(x,l,r); 43 if(mid>=R) update(x+x,l,mid,L,R,val); 44 else if(mid<L) update(x+x+1,mid+1,r,L,R,val); 45 else 46 { 47 update(x+x,l,mid,L,R,val); 48 update(x+x+1,mid+1,r,L,R,val); 49 } 50 sum[x]=sum[x+x]+sum[x+x+1]; 51 } 52 53 ll query(int x,int l,int r,int L,int R) 54 { 55 if(L>R) return 0; 56 if(L<=l&&r<=R) return sum[x]; 57 int mid=(l+r)>>1; 58 push_down(x,l,r); 59 if(mid>=R) return query(x+x,l,mid,L,R); 60 else if(mid<L) return query(x+x+1,mid+1,r,L,R); 61 else 62 { 63 return query(x+x,l,mid,L,R)+query(x+x+1,mid+1,r,L,R); 64 } 65 } 66 67 int main() 68 { 69 for(int i=0;i<(N<<2);i++) tag[i]=inf; 70 scanf("%lld",&n); 71 for(int i=1;i<=n;i++) scanf("%lld",&a[i]); 72 for(int i=1;i<n;i++) scanf("%lld",&k[i]); 73 for(int i=2;i<n;i++) k[i]+=k[i-1]; 74 for(int i=1;i<n;i++) kk[i]=kk[i-1]+k[i]; 75 for(int i=1;i<=n;i++) b[i]=a[i]-k[i-1];//feidijian 76 build(1,1,n); 77 scanf("%lld",&m); 78 while(m--) 79 { 80 char s[2]; int x,y; 81 scanf("%s%d%d",s,&x,&y); 82 if(s[0]=='s') 83 { 84 ll add=kk[y-1]-(x>=2 ? kk[x-2] : 0); 85 printf("%lld\n",add+query(1,1,n,x,y)); 86 } 87 else 88 { 89 ll num=query(1,1,n,x,x)+y;//can't write b[x] instead of query(1,1,n,x,x) 90 //int pos=lower_bound(b,b+n+1,num)-b; 91 //can't use array b! 92 int l=x,r=n,mid,pos=x; 93 while(l<=r) 94 { 95 mid=(l+r)>>1; 96 if(num>query(1,1,n,mid,mid)) 97 { 98 pos=mid; 99 l=mid+1; 100 } 101 else r=mid-1; 102 } 103 update(1,1,n,x,pos,num); 104 } 105 } 106 return 0; 107 } View Code

?

轉載于:https://www.cnblogs.com/Forever-666/p/10740814.html

總結

以上是生活随笔為你收集整理的codeforces 1136E-Nastya Hasn't Written a Legend的全部內容，希望文章能夠幫你解決所遇到的問題。

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