查看网站外链代码,wordpress修改站点地址,wordpress 修改主题名,互联网广告行业分析正题
题目链接#xff1a;我是链接 其实洛谷线段树模板也是一样的#xff1a;三种方法AC评测链接 题目大意
要求支持区间修改#xff0c;区间求和。 线段树
直接用一个lazy标记#xff0c;在之前的博客里有说 code1
#includecstdio
#includealgorithm…正题
题目链接我是链接 其实洛谷线段树模板也是一样的三种方法AC评测链接 题目大意
要求支持区间修改区间求和。 线段树
直接用一个lazy标记在之前的博客里有说 code1
#includecstdio
#includealgorithm
#define N 100010
#define ll long long
using namespace std;
struct treenode{int l,r;ll val,lazy;
}t[N*4];
int n,m,l,r;
ll x;
char c[2];
void build(int x,int l,int r)//建树
{t[x].ll;t[x].rr;if(lr){scanf(%lld,t[x].val);return;}int mid(lr)1;build(x*2,l,mid);build(x*21,mid1,r);t[x].valt[x*2].valt[x*21].val;
}
void downdata(int x)//下传标记
{if(t[x].lazy){t[x*2].lazyt[x].lazy;t[x*2].valt[x].lazy*(t[x*2].r-t[x*2].l1);t[x*21].lazyt[x].lazy;t[x*21].valt[x].lazy*(t[x*21].r-t[x*21].l1);t[x].lazy0;}
}
void change(int x,int l,int r,ll num)//区间修改
{if(t[x].llt[x].rr){t[x].valnum*(t[x].r-t[x].l1);t[x].lazynum;return;}downdata(x);int mid(t[x].lt[x].r)1;if(rmid) change(x*2,l,r,num);else if(lmid) change(x*21,l,r,num);else change(x*2,l,mid,num),change(x*21,mid1,r,num);t[x].valt[x*2].valt[x*21].val;
}
ll find(int x,int l,int r)//区间查询
{if(t[x].llt[x].rr)return t[x].val;downdata(x);int mid(t[x].lt[x].r)1;if(rmid) return find(x*2,l,r);else if(lmid) return find(x*21,l,r);else return find(x*2,l,mid)find(x*21,mid1,r);
}
int main()
{scanf(%d%d,n,m);build(1,1,n);for(int i1;im;i){scanf(%s %d %d,c,l,r);if(c[0]Q) printf(%lld\n,find(1,l,r));else{scanf(%lld,x);change(1,l,r,x);}}
} 树状数组
我们可以用树状数组维护一个查分数组bbb和一个bi#x00D7;i" role="presentation" style="position: relative;">bi×ibi×ib_i\times i的前缀和然后再记录原来的a数组的前缀和sumsumsum对于改写我们就将两个数组改变然后查询就
(sumr(r1)∗ask(c0,r)−ask(c1,r))−(suml−1l∗ask(c1,l−1)−ask(c1,l−1)(sumr(r1)∗ask(c0,r)−ask(c1,r))−(suml−1l∗ask(c1,l−1)−ask(c1,l−1)
(sum_r+(r+1)*ask(c_0,r)-ask(c_1,r))-(sum_{l-1}+l*ask(c_1,l-1)-ask(c_1,l-1)code2
#includecstdio
#includealgorithm
#includeiostream
#define lobit(x) x-x
using namespace std;
long long t[2][100010],x,a[100010],sum[100010];
int n,m,l,r;
void add(int k,int x,int num)//修改
{while(xn){t[k][x]num;xlobit(x);}
}
long long ask(int k,int x)//查询
{long long sum0;while(x0){sumt[k][x];x-lobit(x);}return sum;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){scanf(%lld,a[i]);sum[i]sum[i-1]a[i];}for(int i1;im;i){char c[2];scanf(%s %d %d,c,l,r);if(c[0]Q){long long anssum[r](r1)*ask(0,r)-ask(1,r);ans-sum[l-1]l*ask(0,l-1)-ask(1,l-1);//查询printf(%lld\n,ans);}else{scanf(%d,x);add(0,l,x);add(0,r1,-x);add(1,l,l*x);add(1,r1,-(r1)*x);//修改}}
} 分块
将整段分成多块然后修改如果到达一块就直接修改像线段树一样标记如果不到达一块就暴力修改。 就是 “大段维护局部朴素”——算法竞赛 code3
#includecstdio
#includealgorithm
#includecmath
#define ll long long
#define N 100010
using namespace std;
ll a[N],sum[N],add[N];
int L[N],R[N],d;
int pos[N];
int n,m,t,l,r;
char op[3];
void change(int l,int r,long long d)
{int ppos[l],qpos[r];if(pq){for(int il;ir;i) a[i]d;sum[p]d*(r-l1);}//全都在一块中else{for(int ip1;iq-1;i) add[i]d;//维护中间段落for(int il;iR[p];i) a[i]d;sum[p]d*(R[p]-l1);for(int iL[q];ir;i) a[i]d;sum[q]d*(r-L[q]1);//暴力局部修改}
}
ll ask(int l,int r)
{int ppos[l],qpos[r];ll ans0;if(pq){for(int il;ir;i) ansa[i];ansadd[p]*(r-l1);}//全部都在一块中else{for(int ip1;iq-1;i)anssum[i]add[i]*(R[i]-L[i]1);//累加中间段落for(int il;iR[p];i) ansa[i];ansadd[p]*(R[p]-l1);for(int iL[q];ir;i) ansa[i];ansadd[q]*(r-L[q]1);//暴力局部累加}return ans;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%lld,a[i]);tsqrt(n);for(int i1;it;i){L[i](i-1)*t1;R[i]i*t;}//标记每块左右if(R[t]n) t,L[t]R[t-1]1,R[t]n;//补足尾部for(int i1;it;i)for(int jL[i];jR[i];j){pos[j]i;//表示属于哪个块sum[i]a[j];//计算段落和}for(int i1;im;i){scanf(%s %d %d,op,l,r);if(op[0]C){scanf(%d,d);change(l,r,d);}else printf(%lld\n,ask(l,r));}
}
