codeforces 1136E-Nastya Hasn't Written a Legend

传送门：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个点上调了老半天）。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=;

 const ll inf=-1e18;

 ll n,a[N],b[N],k[N],kk[N],m;

 ll sum[N<<],tag[N<<];

 void build(int x,int l,int r)

 {

     if(l==r)

     {

         sum[x]=b[l];

         return;

     }

     int mid=(l+r)>>;

     build(x+x,l,mid);

     build(x+x+,mid+,r);

     sum[x]=sum[x+x]+sum[x+x+];

 }

 void push_down(int x,int l,int r)

 {

     int mid=(l+r)>>;

     if(tag[x]==inf) return;

     tag[x+x]=tag[x]; tag[x+x+]=tag[x];

     sum[x+x]=tag[x]*(mid-l+);

     sum[x+x+]=tag[x]*(r-mid);

     tag[x]=inf;

 }

 void update(int x,int l,int r,int L,int R,ll val)

 {

     if(L<=l&&r<=R)

     {

         tag[x]=val;

         sum[x]=val*(r-l+);

         return;

     }

     int mid=(l+r)>>;

     push_down(x,l,r);

     if(mid>=R) update(x+x,l,mid,L,R,val);

     else if(mid<L) update(x+x+,mid+,r,L,R,val);

     else

     {

         update(x+x,l,mid,L,R,val);

         update(x+x+,mid+,r,L,R,val);

     }

     sum[x]=sum[x+x]+sum[x+x+];

 }

 ll query(int x,int l,int r,int L,int R)

 {

     if(L>R) return ;

     if(L<=l&&r<=R) return sum[x];

     int mid=(l+r)>>;

     push_down(x,l,r);

     if(mid>=R) return query(x+x,l,mid,L,R);

     else if(mid<L) return query(x+x+,mid+,r,L,R);

     else

     {

         return query(x+x,l,mid,L,R)+query(x+x+,mid+,r,L,R);

     }

 }

 int main()

 {

     for(int i=;i<(N<<);i++) tag[i]=inf;

     scanf("%lld",&n);

     for(int i=;i<=n;i++) scanf("%lld",&a[i]);

     for(int i=;i<n;i++) scanf("%lld",&k[i]);

     for(int i=;i<n;i++) k[i]+=k[i-];

     for(int i=;i<n;i++) kk[i]=kk[i-]+k[i];

     for(int i=;i<=n;i++) b[i]=a[i]-k[i-];//feidijian

     build(,,n);

     scanf("%lld",&m);

     while(m--)

     {

         char s[]; int x,y;

         scanf("%s%d%d",s,&x,&y);

         if(s[]=='s')

         {

             ll add=kk[y-]-(x>= ? kk[x-] : );

             printf("%lld\n",add+query(,,n,x,y));

         }

         else

         {

             ll num=query(,,n,x,x)+y;//can't write b[x] instead of query(1,1,n,x,x)

             //int pos=lower_bound(b,b+n+1,num)-b;

             //can't use array b!

             int l=x,r=n,mid,pos=x;

             while(l<=r)

             {

                 mid=(l+r)>>;

                 if(num>query(,,n,mid,mid))

                 {

                     pos=mid;

                     l=mid+;

                 }

                 else r=mid-;

             }

             update(,,n,x,pos,num);

         }

     }

     return ;

 }

巴特西

codeforces 1136E-Nastya Hasn't Written a Legend

最新文章

热门文章