首页 > 代码库 > 51nod1394 差和问题
51nod1394 差和问题
我只会用线段树写。。。不喜欢树状数组。。其实跑的也不算慢?然后各种*的时候忘了longlong一直WA。。。药丸!
而且我不怎么会用map离散化。。。那么就sort+unique
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long long#define lson l,mid,x<<1#define rson mid+1,r,x<<1|1int read(){ int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x;}const int nmax=1e5+5;const int inf=0x7f7f7f7f;ll sm[nmax<<3],col[nmax<<3];int a[nmax<<1],b[nmax<<1],ct[nmax<<1];struct node{ int u,v;};node ns[nmax];void update(int p,int ad,int bd,int l,int r,int x){ if(l==r) { col[x]+=ad,sm[x]+=bd;return ; } int mid=(l+r)>>1; p<=mid?update(p,ad,bd,lson):update(p,ad,bd,rson); sm[x]=sm[x<<1]+sm[x<<1|1];col[x]=col[x<<1]+col[x<<1|1];}struct nd{ int u;ll v; nd(int u,ll v):u(u),v(v){}; nd(){};};nd query(int tl,int tr,int l,int r,int x){ if(tl<=l&&tr>=r) return nd(col[x],sm[x]); ll tm=0;int tc=0,mid=(l+r)>>1;nd o; if(tl<=mid) o=query(tl,tr,lson),tc+=o.u,tm+=o.v; if(tr>mid) o=query(tl,tr,rson),tc+=o.u,tm+=o.v; return nd(tc,tm);}void print(int l,int r,int x){ printf("%d %d %d\n",l,r,sm[x]); if(l==r) return ; int mid=(l+r)>>1; print(lson);print(rson);}int main(){ int n=read(),m=read(),u,v,d,cnt=n; rep(i,1,n) a[i]=b[i]=read(); rep(i,1,m){ ns[i].u=read();if(ns[i].u!=3) ns[i].v=read(),a[++cnt]=b[cnt]=ns[i].v; } sort(b+1,b+cnt+1); cnt=unique(b+1,b+cnt+1)-b-1; rep(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b; rep(i,1,n) update(a[i],1,b[a[i]],1,cnt,1),ct[a[i]]++; ll tm;nd o; tm=0; rep(j,2,cnt) { o=query(1,j-1,1,cnt,1); tm+=(ll)ct[j]*((ll)b[j]*o.u-o.v); } rep(i,1,m){ u=ns[i].u; if(u==3) printf("%lld\n",tm); else if(u==1){ v=lower_bound(b+1,b+cnt+1,ns[i].v)-b; ct[v]++;update(v,1,ns[i].v,1,cnt,1); if(v==1) o=nd(0,0);else o=query(1,v-1,1,cnt,1); tm+=(ll)b[v]*o.u-o.v+(sm[1]-o.v-(ll)b[v]*ct[v])-(ll)(col[1]-o.u-ct[v])*b[v]; }else{ v=lower_bound(b+1,b+cnt+1,ns[i].v)-b; if(!ct[v]) puts("-1"); else{ ct[v]--,update(v,-1,-ns[i].v,1,cnt,1); if(v==1) o=nd(0,0);else o=query(1,v-1,1,cnt,1); tm-=(ll)b[v]*o.u-o.v+(sm[1]-o.v-(ll)b[v]*ct[v])-(ll)(col[1]-o.u-ct[v])*b[v]; } } //printf("->_->\n");print(1,cnt,1); } return 0;}
1394 差和问题
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
收藏
关注
有一个多重集合S(即里面元素可以有重复),初始状态下有n个元素,对他进行如下操作:
1、向S里面添加一个值为v的元素。输入格式为1 v
2、向S里面删除一个值为v的元素。输入格式为2 v
3、询问S里面的元素两两之差绝对值之和。输入格式为3
对于样例,
操作3,|1-2|+|1-3|+|2-3|=4
操作1 4之后,集合中的数字为1 2 3 4
操作3,|1-2|+|1-3|+|2-3|+|1-4|+|2-4|+|3-4|=10
操作2 2之后,集合中的数字为1 3 4
操作3,|1-3|+|1-4|+|3-4|=6
Input
第一行输入两个整数n,Q表示集合中初始元素个数和操作次数。(1<=n,Q<=100,000)第二行给出n个整数a[0],a[1],a[2],…,a[n-1],表示初始集合中的元素。(0<=a[i]<=1,000,000,000) 接下来Q行,每行一个操作。(0<=v<=1,000,000,000)
Output
对于第2类操作,如果集合中不存在值为v的元素可供删除,输出-1。对于第3类操作,输出答案。
Input示例
3 51 2 331 432 23
Output示例
4106
51nod1394 差和问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。