标签：怪兽 le lef int mid cc ans
- 问题之所以看上去很棘手，是因为各种意义上的起始能量值未知
- 但能量值的上限最多仅为100，因此我们可以通过枚举消去这一维度的信息，于是需要统计的信息就可以用线段树维护了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int n,m,k,q,le,ans;
int a[50005];
struct t1
{
int l,r,va,lef;
}t[105][200005];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
cc=getchar();
}
int s=cc-48;
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
return s;
}
void build(int p,int l,int r)
{
if(l==r)
{
for(int i=0;i<=m;i++)
{
t[i][p].l=l;
t[i][p].r=r;
t[i][p].va=min(m,i+a[l])/k;
t[i][p].lef=min(m,i+a[l])%k;
}
}
else
{
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
for(int i=0;i<=m;i++)
{
t[i][p].l=l;
t[i][p].r=r;
t[i][p].va=t[i][p*2].va+t[t[i][p*2].lef][p*2+1].va;
t[i][p].lef=t[t[i][p*2].lef][p*2+1].lef;
}
}
}
void change(int p,int c,int va)
{
if(t[0][p].l==t[0][p].r)
{
a[c]+=va;
for(int i=0;i<=m;i++)
{
t[i][p].va=min(m,i+a[c])/k;
t[i][p].lef=min(m,i+a[c])%k;
}
}
else
{
int mid=(t[0][p].l+t[0][p].r)>>1;
if(c<=mid)
{
change(p*2,c,va);
}
else
{
change(p*2+1,c,va);
}
for(int i=0;i<=m;i++)
{
t[i][p].va=t[i][p*2].va+t[t[i][p*2].lef][p*2+1].va;
t[i][p].lef=t[t[i][p*2].lef][p*2+1].lef;
}
}
}
void ask(int p,int l,int r)
{
if(l<=t[0][p].l&&r>=t[0][p].r)
{
ans=ans+t[le][p].va;
le=t[le][p].lef;
}
else
{
int mid=(t[0][p].l+t[0][p].r)>>1;
if(l<=mid)
{
ask(p*2,l,r);
}
if(r>mid)
{
ask(p*2+1,l,r);
}
}
}
int main()
{
cin>>n>>m>>k>>q;
for(int i=1;i<=n;i++)
{
a[i]=read1();
}
build(1,1,n);
for(int i=1;i<=q;i++)
{
int opt,u,v;
opt=read1();
u=read1();
v=read1();
if(opt==1)
{
change(1,u,v);
}
else
{
le=0;
ans=0;
ask(1,u,v);
printf("%d\n",ans);
}
}
return 0;
}
标签：怪兽,
le,
lef,
int,
mid,
cc,
ans
From： https://www.cnblogs.com/watersail/p/18290627