首页 > 代码库 > SPOJ DCEPC11I
SPOJ DCEPC11I
题目大意:
就是给定一段区间令其中的数增加一个递增序列(也就是说第一个+1,第二个+2.。。。。)
询问操作是区间的和
这里的查询很简单,但是对于添加递增序列入区间就比较搞脑子了
我们需要一个add[]作为区间的首个数字增加的值,del[]表示等差数列的公差,因为你每次添加进入一个等差数列,是可以叠加的但公差变为了del[ls]+=del[o]
这里主要是pushdown函数的写法
我们要用到等差公式的求和:S =a*n+n(n-1)*d/2
void push_down(int o,int x,int y)
{
int mid=(x+y)/2,ls=o<<1,rs=o<<1|1;
if(add[o]||del[o]){
int t1=mid-x+1,t2=y-mid;
LL a2=add[o]+t1*del[o];
sum[ls]+=add[o]*t1+t1*(t1-1)*del[o]/2;
sum[rs]+=a2*t2+t2*(t2-1)*del[o]/2;
add[ls]+=add[o],add[rs]+=a2;
del[ls]+=del[o],del[rs]+=del[o];
add[o]=del[o]=0;
}
}
总代码如下所示:
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define L ls,x,mid 5 #define R rs,mid+1,y 6 #define LL long long 7 #define N 100010 8 LL sum[N<<2],add[N<<2]; 9 int del[N<<2];10 void push_up(int o)11 {12 sum[o]=sum[o<<1]+sum[o<<1|1];13 }14 void push_down(int o,int x,int y)15 {16 int mid=(x+y)/2,ls=o<<1,rs=o<<1|1;17 if(add[o]||del[o]){18 int t1=mid-x+1,t2=y-mid;19 LL a2=add[o]+t1*del[o];20 sum[ls]+=add[o]*t1+t1*(t1-1)*del[o]/2;21 sum[rs]+=a2*t2+t2*(t2-1)*del[o]/2;22 add[ls]+=add[o],add[rs]+=a2;23 del[ls]+=del[o],del[rs]+=del[o];24 add[o]=del[o]=0;25 }26 }27 void build(int o,int x,int y)28 {29 int mid=(x+y)/2,ls=o<<1,rs=o<<1|1;30 sum[o]=del[o]=add[o]=0;31 if(x==y) return;32 build(L);33 build(R);34 }35 void update(int o,int x,int y,int s,int t)36 {37 int mid=(x+y)/2,ls=o<<1,rs=o<<1|1;38 if(x>=s&&y<=t){39 add[o]+=x-s+1;40 sum[o]+=(x-s+1)*(y-x+1)+(y-x+1)*(y-x)/2;41 del[o]++;42 return;43 }44 push_down(o,x,y);45 if(mid>=s) update(L,s,t);46 if(mid<t) update(R,s,t);47 push_up(o);48 }49 void query(int o,int x,int y,int s,int t,LL &ans)50 {51 int mid=(x+y)/2,ls=o<<1,rs=o<<1|1;52 if(x>=s&&y<=t){53 ans+=sum[o];54 return;55 }56 push_down(o,x,y);57 if(mid>=s) query(L,s,t,ans);58 if(mid<t) query(R,s,t,ans);59 }60 int main()61 {62 int n,q,op,a,b;63 scanf("%d%d",&n,&q);64 build(1,1,n);65 for(int i=0;i<q;i++){66 scanf("%d%d%d",&op,&a,&b);67 if(op){68 LL ans=0;69 query(1,1,n,a,b,ans);70 printf("%lld\n",ans);71 }72 else update(1,1,n,a,b);73 }74 return 0;75 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。