hdu4288 线段树之点更新

建5颗树分别存和，每个节点记录区间点数。

ACcode：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using std::sort;
typedef long long LL;
const int nsize=111111;
char op[nsize];
LL sum[nsize<<2][5];
int X[nsize],num[nsize<<2],a[nsize];
int Fin(int key,int len)
{
int m,l=1,r=len;
while (l<=r)
{
m=(l+r)>>1;
if (X[m]==key) return m;
else if (X[m]>key) r=m-1;
else l=m+1;
}
return -1;
}
void build(int rt,int l,int r)
{
num[rt]=0;
for (int i=0;i<5;i++) sum[rt][i]=0;
if (l==r) return ;
int m=(l+r)>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
}
void PushUp(int rt)
{
for (int i=0;i<5;i++)
sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][(i-num[rt<<1]%5+5)%5];
}
void update(int rt,int l,int r,int p,int v)
{
num[rt]+=v>0?1:-1;
if (l==r)
{
sum[rt][1]=v;
return ;
}
int m=(l+r)>>1;
if (p<=m) update(rt<<1,l,m,p,v);
else
update(rt<<1|1,m+1,r,p,v);
PushUp(rt);
}
int main()
{
char str[11];
int n,i,j,k,top;
while (~scanf("%d",&n))
{
for (top=i=0;i<n;i++)
{
scanf("%s",str);
op[i]=str[0];
if (op[i]!='s')
{
scanf("%d",&a[i]);
if (op[i]=='a') X[top++]=a[i];
}
}
std::sort(X,X+top);
for (i=j=1;i<top;i++)
if (X[i]!=X[i-1]) X[j++]=X[i];
build(1,0,j);
for (i=0;i<n;i++)
{
if (op[i]=='s') printf("%I64dn",sum[1][3]);
else update(1,0,j,Fin(a[i],j-1),op[i]=='a'?a[i]:0);
}
}
return 0;
}

最后

以上就是心灵美羊为你收集整理的hdu4288 线段树之点更新的全部内容，希望文章能够帮你解决hdu4288 线段树之点更新所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。