本文主要是介绍HDU 4828 Coder(线段树 + 离散化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题目和平时的有点不一样，平时的都是很普通的查询，这次查询的下标号会变，给线段树造成一定的困扰，其实可以分区间来避免这个下标变化的问题
根节点的值肯定是有子节点的值来确定了，那么我么就这样，维护5个sum值，分别是除5余数为1 2 3 4 0的和，由于所有数字都在int范围内，所以比较大，
我们显然不能直接建立线段树，我们可以等待全部输入完成之后建立离线算法对所有数字进行离散化，完了建立线段树，用num记录每个区间的元素个数
每次插入或者删除直接更新这个num值，同时根据子阶段的sum值来更新父节点的sum值，注意更新是这样更新的，左边的值不动，右边的可能会因为左边
的值不同会发生便宜，计算几后按照左边num值来确定偏移关系就可以了，总之这个线段树的思想很好，值得一做！
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 100000
using namespace std;
struct point
{int l,r;long long sum[5];int num;int init(){num=0;memset(sum,0,sizeof(sum));}
}po[maxn*4];
int hash[maxn],oper[maxn],n;
char str[maxn][10];
int build_tree(int root,int l,int r)
{po[root].init();po[root].l=l,po[root].r=r;if(l==r)return 0;int mid=(l+r)>>1;build_tree(root<<1,l,mid);build_tree((root<<1)+1,mid+1,r);return 0;
}
int find_pos(int l,int r,int num)
{int mid;while(l<=r){mid=(l+r)>>1;if(hash[mid]==num)return mid;if(hash[mid]>num)r=mid-1;elsel=mid+1;}return 0;
}
int insert(int root,int pos,int value)
{if(po[root].l==po[root].r){po[root].num=1;po[root].sum[0]=value;return 0;}po[root].num++;int mid=(po[root].l+po[root].r)>>1;if(pos <= mid)insert(root<<1,pos,value);elseinsert((root<<1)+1,pos,value);for(int i = 0 ; i< 5;i++){po[root].sum[i] = po[root*2].sum[i] + po[(root<<1)+1].sum[((i-po[root*2].num)%5 + 5)%5] ;}return 0;
}
int del_tree(int root,int pos,int value)
{if(po[root].l==po[root].r){// printf("vaindel:%d %d\n",value,hash[pos]);po[root].num=0;po[root].sum[0]=0;return 0;}po[root].num--;int mid=(po[root].l+po[root].r)>>1;if(pos <= mid)del_tree(root<<1,pos,value);elsedel_tree((root<<1)+1,pos,value);for(int i = 0 ; i< 5;i++){po[root].sum[i] = po[root*2].sum[i] + po[(root<<1)+1].sum[((i-po[root*2].num)%5 + 5)%5] ;}return 0;
}
int main()
{int i,j,k,r;int p,q;while(scanf("%d",&n)!=EOF){r=0;for(i=0;i<n;i++){scanf("%s",str[i]);if(str[i][0]=='a'){scanf("%d",&oper[i]);hash[r++]=oper[i];}else if(str[i][0]=='d')scanf("%d",&oper[i]);}sort(hash,hash+r);k=1;for(i=1;i<r;i++)if(hash[i]!=hash[i-1])hash[k++]=hash[i];build_tree(1,0,k-1);for(i=0;i<n;i++){if(str[i][0]=='a'){p=find_pos(0,k-1,oper[i]);insert(1,p,oper[i]);}else if(str[i][0]=='d'){p=find_pos(0,k-1,oper[i]);del_tree(1,p,oper[i]);}else{printf("%lld\n",po[1].sum[2]);}}}return 0;
}
这篇关于HDU 4828 Coder(线段树 + 离散化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
