本文主要是介绍hdu 4288 Coder CF85-D Sum of Medians （单点更新），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有三种类型的操作，1."add x"表示往集合里添加数x。2.“del x”表示将集合中数x删除。3.“sum”求出从小到大排列的集合中下标模5为3的数的和。集合中的数都是唯一的。
线段树。在线段树中维护当前这个集合中数的个数cnt，和所有的数模5为0……4内的数的和设为mod[0...4]。在进行区间合并的时候，父区间里的mod[0...4]首先等于左子区间里的mod[0...4]，设要加入的右子区间的数为mod[i]，则它应该加到父区间的mod[左子区间的cnt+i]。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
const int N=100005;
char str[5];
vector<int> y;
map<int,int> imap;
struct OP
{int type,valu;void input(){scanf("%s",str);if(strcmp(str,"add")==0) type=0;else if(strcmp(str,"del")==0) type=1;else type=2;if(type==2) return;scanf("%d",&valu);y.push_back(valu);}
}op[N];
struct node
{int lft,rht,cnt;LL mod[5];int mid(){return lft+(rht-lft)/2;}void clear(){memset(mod,0,sizeof(mod));}void change(){if(cnt==0) mod[1]=0;else mod[1]=y[lft];}
};
struct Segtree
{node tree[N*4];void relax(int ind){int c=tree[LL(ind)].cnt;for(int i=0;i<5;i++) tree[ind].mod[i]=tree[LL(ind)].mod[i];for(int i=0;i<5;i++) tree[ind].mod[(i+c)%5]+=tree[RR(ind)].mod[i];}void build(int lft,int rht,int ind){tree[ind].lft=lft; tree[ind].rht=rht;tree[ind].cnt=0; tree[ind].clear();if(lft!=rht){int mid=tree[ind].mid();build(lft,mid,LL(ind));build(mid+1,rht,RR(ind));}}void updata(int pos,int ind,int valu){tree[ind].cnt+=valu;if(tree[ind].lft==tree[ind].rht) tree[ind].change();else {int mid=tree[ind].mid();if(pos<=mid) updata(pos,LL(ind),valu);else updata(pos,RR(ind),valu);relax(ind);}}
}seg;
int main()
{int n;while(scanf("%d",&n)!=EOF){int sc=0;y.clear(); imap.clear();for(int i=0;i<n;i++) op[i].input();sort(y.begin(),y.end());y.erase(unique(y.begin(),y.end()),y.end());for(int i=0;i<(int)y.size();i++) imap.insert(make_pair(y[i],sc++));seg.build(0,sc,1);for(int i=0;i<n;i++){if(op[i].type==0) seg.updata(imap[op[i].valu],1,1);else if(op[i].type==1) seg.updata(imap[op[i].valu],1,-1);else printf("%I64d\n",seg.tree[1].mod[3]);}}return 0;
}
这篇关于hdu 4288 Coder CF85-D Sum of Medians （单点更新）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
