Bzoj 3155
coc youyl
posted @ 2015年7月02日 20:57
in bzoj
, 1171 阅读
题目分类:树状数组
题意:
修改原数列,要求维护他前缀和的前缀和。
题解:
使用线段树会超时真是差评。
这个问题转化为,给数列上的从i到n位依次添加1,2,3……n-i+1倍的某个值。
使用差分的方法,修改一段区间,询问的时候询问前缀和。
利用贡献法就可以在树状数组上实现。
程序:
#include<cstdio> using namespace std; struct fenwick { long long val[1520000]; inline void edit(long long x,long long y) { if(x==0)return; while (x<=100000) { val[x]+=y; x+=(x&(-x)); } } inline long long query(int x) { long long ss=0; while (x>0) { ss+=val[x]; x-=(x&(-x)); }return ss; } inline void edit2(long long x,long long y) { while (x>0) { val[x]+=y; x-=(x&(-x)); } } inline long long query2(int x) { if(x==0)return 0; long long ss=0; while (x<=100000) { ss+=val[x]; x+=(x&(-x)); }return ss; } }sgt1,sgt2,sgt3; long long n,m,x1,x2; long long a[1520000]; char str[1200]; inline void edit(long long x,long long y) { sgt1.edit(x,(x-1)*y); sgt2.edit2(n,y); sgt2.edit2(x-1,-y); sgt3.edit(n,n*y); sgt3.edit(x-1,-y*(x-1)); } inline long long query(long long x) { return (sgt2.query2(x))*x+sgt3.query(x-1);//-sgt1.query(x); } int main() { scanf("%lld %lld",&n,&m); for (long long i=1;i<=n;i++) { scanf("%lld",&a[i]); edit(i,a[i]); } for (long long i=1;i<=m;i++) { scanf("%s",str+1); if(str[1]=='Q') { scanf("%lld",&x1); printf("%lld\n",query(x1)); } else { scanf("%lld %lld",&x1,&x2); edit(x1,x2-a[x1]); a[x1]=x2; } } return 0; }
2022年8月16日 18:18
Uttarakhand Board Model Paper 2023 Class 3 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer,
2022年9月03日 18:29
Haryana Board Model Paper 2023 Class 7 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Haryana Board 7th Class Model Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.