本文主要是介绍hdu4288 线段树+离线化+离散化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目看起来很麻烦，其实不难。
题意是个坑，以为输入是有序的，结果居然不是，WA了好多遍。
维护五颗记录和的线段树，分别对应对5取余的值，这个题简单的地方就在于查询时每次都查整个区间，所以只需要输出根节点即可，目测如果进一步改成子区间会难很多。
维护时，相当于将每个点都作为一个区间，然后两个区间合并时，左孩子的记录可直接用，右孩子的记录需要参考左区间元素个数才能判断在整个区间的位置，公式很好推理。
千万注意，要排序，因为输入可能是无序的，如果不排序，新加入的节点不能保证整个序列有序，所以要排序之后才能获得元素在线段树中的位置，进而执行操作。
另外，离线化不会影响结果，因为处理到某个操作时，后续操作均未执行，故无论新加入的元素在什么位置，将空的位置去掉，不会影响结果。
代码：
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
long long sum[5][N*4];
int cnt[N*4];struct op
{string s;int v;
}q[N];void build(int l,int r,int rt)
{for (int i=0;i<5;i++)sum[i][rt]=0;cnt[rt]=0;if (l==r)return ;delf;build(lson);build(rson);
}void pushup(int rt)
{cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];for (int i=0;i<5;i++)sum[i][rt]=sum[i][rt<<1]+sum[(i-(cnt[rt<<1]%5)+5)%5][rt<<1|1];return ;
}void update(int k,long long v,int l,int r,int rt)
{if (l==r){sum[1][rt]=v;cnt[rt]=1;return ;}delf;if (k<=m)update(k,v,lson);elseupdate(k,v,rson);pushup(rt);return ;
}void del(int k,int l,int r,int rt)
{if (l==r){sum[1][rt]=0;cnt[rt]=0;return ;}delf;if (m>=k)del(k,lson);elsedel(k,rson);pushup(rt);return ;
}int main()
{int n;while (cin>>n){string s;long long v;build(1,n,1);int c=1;int a[N];for (int i=0;i<n;i++){cin>>q[i].s;if (q[i].s[0]!='s'){cin>>q[i].v;a[c++]=q[i].v;}elseq[i].v=0;}sort(a+1,a+c); //必须排序，输入居然不是有序的，尼玛WA了一晚上int m=unique(a+1,a+c)-(a+1); //第一次用，该函数将这一序列的所有值中重复的元素放在后面，并返回数组中不重复的最后一个元素的位置，减去数组开头刚好是元素个数for (int i=0;i<n;i++){if (q[i].s[0]=='s')cout<<sum[3][1]<<endl;if (q[i].s[0]=='a'){int v=q[i].v;int k=upper_bound(a+1,a+c,v)-(a+1); //第一次用，二分查找v在数组中第一个大于v的元素的位置，同样要减去初始位置update(k,v,1,n,1);}if (q[i].s[0]=='d'){int v=q[i].v;int k=upper_bound(a+1,a+c,v)-(a+1);del(k,1,n,1);}}}return 0;
}这篇关于hdu4288 线段树+离线化+离散化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
