首页 > 代码库 > hdu-4288-Coder-线段树
hdu-4288-Coder-线段树
感觉今天的状态有点不好。。。老是在小地方犯错。。。
简单的记录一下就好。
#include<stdio.h> #include<iostream> #include<stdlib.h> #include<string.h> #include<algorithm> #include<vector> #include<math.h> #include<map> #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define maxn 110000 #define mem(a,b) (memset(a),b,sizeof(a)) #define lmin 1 #define rmax len #define lson l,(l+r)/2,rt<<1 #define rson (l+r)/2+1,r,rt<<1|1 #define root lmin,rmax,1 #define now l,r,rt #define int_now int l,int r,int rt #define INF 99999999 #define LL __int64 #define mod 10007 #define eps 1e-6 #define zero(x) (fabs(x)<eps?0:x) LL sum[maxn*4][5]; int num[maxn*4]; int du[maxn]; map<int,int>mp; int len; struct list { int op; int val; }node[maxn]; void push_up(int_now) { num[rt]=num[rt<<1]+num[rt<<1|1]; 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 updata(int ll,int x,int_now) { if(ll<l||ll>r)return; if(l==r&&l==ll) { if(x>0)num[rt]++; else num[rt]--; sum[rt][0]+=x; return; } updata(ll,x,lson); updata(ll,x,rson); push_up(now); } int main() { int n,x; char str[110]; while(~scanf("%d",&n)) { int ls=0; for(int i=1;i<=n;i++) { scanf("%s",str); node[i].op=str[0]; if(str[0]=='s')continue; scanf("%d",&x); du[++ls]=x; node[i].val=x; } sort(du+1,du+ls+1); len=0; du[0]=-1; mp.clear(); for(int i=1;i<=ls;i++) { if(du[i]!=du[i-1]) { mp[du[i]]=++len; du[len]=du[i]; } } memset(sum,0,sizeof(sum)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) { int x=mp[node[i].val]; if(node[i].op=='a')updata(x,node[i].val,root); if(node[i].op=='d')updata(x,-node[i].val,root); if(node[i].op=='s')printf("%I64d\n",sum[1][2]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。