【The 13th Chinese Northeast Collegiate Programming Contest H 题】

Northeast Collegiate Programming Contest H 题】"/>

【The 13th Chinese Northeast Collegiate Programming Contest H 题】

题目大意：NOIP2018d1t1 支持 M 次区间查询答案和区间修改操作。

题解：
首先考虑不带区间修改的情况。从左到右进行考虑，发现对于第 i 个数来说，对答案的贡献仅仅取决于第 i-1 个数的大小：若 \(a_i \le a_{i-1}\)，则第 i 个数对答案的贡献为 0，否则对答案的贡献为两者的差值。贡献可以这样算是因为每个点至少增加 \(a_i\) 次，且当前点增加多少仅对后面一个数有直接影响。因此，考虑维护差分数组即可，区间修改变成两次单点修改，区间查询转变成查询区间大于 0 的数字之和。则每次询问 [l,r] 的答案为：sum[l+1,r] + a[l]，a[l] 利用树状数组维护差分序列即可单点回答了。时间复杂度为 \(O(MlogN)\)。

代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
typedef long long LL;int n,m,a[maxn],d[maxn];
LL bit[maxn];
void update(int pos,LL val){for(int i=pos;i<=n;i+=i&-i)bit[i]+=val;
}
LL get(int pos){LL ret=0;for(int i=pos;i;i-=i&-i)ret+=bit[i];return ret;
}
struct node{#define ls(o) t[o].lc#define rs(o) t[o].rcint lc,rc;LL sum;
}t[maxn<<1];
int tot,rt;
void up(int o){LL suml=t[ls(o)].sum>=0?t[ls(o)].sum:0;LL sumr=t[rs(o)].sum>=0?t[rs(o)].sum:0;t[o].sum=suml+sumr;
}
void build(int &o,int l,int r){o=++tot;if(l==r){t[o].sum=d[l];return;}int mid=l+r>>1;build(ls(o),l,mid),build(rs(o),mid+1,r);up(o);
}
void modify(int o,int l,int r,int pos,int val){if(l==r){t[o].sum+=val;return;}int mid=l+r>>1;if(pos<=mid)modify(ls(o),l,mid,pos,val);else modify(rs(o),mid+1,r,pos,val);up(o);
}
LL query(int o,int l,int r,int x,int y){if(l==x&&r==y)return max(t[o].sum,0LL);int mid=l+r>>1;if(y<=mid)return query(ls(o),l,mid,x,y);else if(x>mid)return query(rs(o),mid+1,r,x,y);else return query(ls(o),l,mid,x,mid)+query(rs(o),mid+1,r,mid+1,y);
}void read_and_parse(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=2;i<=n;i++)d[i]=a[i]-a[i-1];build(rt,1,n);
}
void solve(){int opt,l,r,val;while(m--){scanf("%d",&opt);if(opt==1){scanf("%d%d%d",&l,&r,&val);modify(rt,1,n,l,val),update(l,val);if(r!=n)modify(rt,1,n,r+1,-val),update(r+1,-val);}else{scanf("%d%d",&l,&r);LL ret=l==r?0:query(rt,1,n,l+1,r);printf("%lld\n",ret+get(l)+a[l]);}}
}
void init(){tot=rt=0;for(int i=1;i<=n;i++)bit[i]=0;
}
int main(){int T;scanf("%d",&T);while(T--){init();read_and_parse();solve();}return 0;
}

转载于:.html