很模板的题
在建树的时候输入
求和后更新
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
using namespace std;
///线段树 成段更新
struct node
{
int l;
int r;
int total;
int mark;
};
node a[100050*4];
int c[100050];
int build(int rt,int l,int r)
{
a[rt].l=l;
a[rt].r=r;
a[rt].mark=0;
if(l==r)
{
scanf("%d",&c[l]);
return a[rt].total=c[l];
}
int mid=(l+r)>>1;
return a[rt].total=build(rt<<1,l,mid)+build(rt<<1|1,mid+1,r);
}
void update_mark(int rt)
{
if(a[rt].mark!=0)
{
a[rt].total+=(a[rt].r-a[rt].l+1)*a[rt].mark;
if(a[rt].l!=a[rt].r)
{
a[rt<<1].mark+=a[rt].mark;
a[rt<<1|1].mark+=a[rt].mark;
}
a[rt].mark=0;
}
}
int cal(int rt,int l,int r)
{
update_mark(rt);
if(l>a[rt].r||r<a[rt].l)
return 0;
if(l<=a[rt].l&&a[rt].r<=r)
{
return a[rt].total;
}
return cal(rt<<1,l,r)+cal(rt<<1|1,l,r);
}
int update(int rt,int l,int r,int va)
{
update_mark(rt);
if(l>a[rt].r||r<a[rt].l)
return a[rt].total;
if(l<=a[rt].l&&a[rt].r<=r)
{
a[rt].mark+=va;
update_mark(rt);
return a[rt].total;
}
return a[rt].total=update(rt<<1,l,r,va)+update(rt<<1|1,l,r,va);
}
int main(){
int n,m,q;
while(~scanf("%d%d%d",&n,&m,&q))
{
build(1,1,n);
for(int i=0;i<q;i++)
{
int x;
scanf("%d",&x);
int ans=cal(1,x,x+m-1);
printf("%d\n",ans);
update(1,x,x+m-1,-1);
}
}
}