本文共 1252 字，大约阅读时间需要 4 分钟。
题意：一共有三种操作，add添加一个元素，del删除一个元素，sum查询下标%5==3的所有元素的和。
思路：有整个区间的一个查询，自然想到线段树，只不过这次的要%5==3的一个条件，在更新父亲信息的时候做了改变。
离散化无非就是将所有数去重，然后一个一个处理。至于更新时的变化下面给了解释。
#include#include #include #include #include #include using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=100010; ll num[maxn*4][5]; int a[maxn],n,m,cnt[maxn*4]; struct edge{ char c; int x; }q[maxn]; void pushup(int node){ cnt[node]=cnt[node<<1]+cnt[node<<1|1]; //cnt记录区间内有多少个数。 for(int i=0;i<5;i++){ num[node][i]=num[node<<1][i]+num[node<<1|1][(i-cnt[node<<1]%5+5)%5]; //可以知道左儿子自然为num[node][i]，例如num[1][3]=num[2][3]+num[3][3-cnt]， //左儿子那边共有cnt个数，这样的话，右儿子就不能再%5==3的直接相加了，应该先减去这个数在取余的相加； //如果cnt等于4的话，右儿子的和就应该为num[3][4]的和。 } } void add(int pos,int val,int le,int ri,int node){ if(le==ri){ cnt[node]=1; num[node][1]=val; return ; } int t=(le+ri)>>1; if(pos<=t) add(pos,val,le,t,node<<1); else add(pos,val,t+1,ri,node<<1|1); pushup(node); } void del(int pos,int le,int ri,int node){ if(le==ri){ num[node][1]=cnt[node]=0; return ; } int t=(le+ri)>>1; if(pos<=t) del(pos,le,t,node<<1); else del(pos,t+1,ri,node<<1|1); pushup(node); } int main(){ char str[10]; while(scanf("%d",&n)!=-1){ m=0; for(int i=0;i
转载地址：http://znali.baihongyu.com/