首页 > 代码库 > 1394 差和问题
1394 差和问题
1394 差和问题
基准时间限制：1 秒 空间限制：131072 KB
有一个多重集合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
思路：离散化+数状数组；
维护两个树状数组，一个为区间的和，另一个为区间个数，然后离线查询。插入和删除一个数字的时候要统计一下这个对答案的影响。当前数字为x,比当前数字小的有cnt个，总和为sum,那么这一部分对答案的影响是x*cnt-sum.对于求比当前数字大的数字类似的道理。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<stdlib.h> 5 #include<queue> 6 #include<string.h> 7 #include<math.h> 8 #include<map> 9 using namespace std; 10 typedef long long LL; 11 LL num[100005]; 12 typedef struct node 13 { 14 LL x; 15 int op; 16 int id; 17 } ss; 18 typedef struct pp 19 { 20 LL x; 21 LL id; 22 } ap; 23 ss ask[100005]; 24 map<LL,int>my; 25 LL ac[400000]; 26 int id[100005]; 27 LL bit_ans[200005]; 28 LL bit_sum[200005]; 29 LL sum1(int i); 30 void add1(int i,LL x,int n); 31 LL sum2(int i); 32 void add2(int i,LL x,int n); 33 LL akk[100005]; 34 int main(void) 35 { 36 int n,Q; 37 scanf("%d %d",&n,&Q); 38 int i,j; 39 my.clear(); 40 int cn = 0; 41 memset(bit_ans,0,sizeof(bit_ans)); 42 memset(bit_sum,0,sizeof(bit_sum)); 43 for(i = 0; i < n; i++) 44 { 45 scanf("%lld",&num[i]); 46 ac[cn++] = num[i]; 47 } 48 for(i = 1; i <= Q; i++) 49 { 50 int x,y; 51 scanf("%d",&ask[i].op); 52 if(ask[i].op != 3) 53 { 54 scanf("%lld",&ask[i].x); 55 ac[cn++] = ask[i].x; 56 } 57 ask[i].id = i; 58 }//printf("1\n"); 59 sort(num,num+n); 60 sort(ac,ac+cn); 61 int acc = 1; 62 LL x = ac[0]; 63 my[x] = 1; 64 for(i = 1; i < cn; i++) 65 { 66 if(x!=ac[i]) 67 { 68 acc++; 69 x= ac[i]; 70 my[x] = acc; 71 } 72 } 73 LL summ = 0; 74 for(i = 0; i < n; i ++) 75 { 76 int uv = my[num[i]]; 77 summ += sum2(uv-1)*num[i] - sum1(uv-1); 78 add1(uv,num[i],acc); 79 add2(uv,1,acc); 80 } 81 akk[0]=summ; 82 for(i = 1; i <= Q; i++) 83 { 84 if(ask[i].op==2) 85 { 86 int ic = my[ask[i].x]; 87 LL a = sum2(ic)-sum2(ic-1); 88 if(!a){printf("-1\n");akk[i] = akk[i-1];} 89 else 90 { 91 LL smal_x1 = sum2(ic-1); 92 LL smal_y1 = sum1(ic-1); 93 LL maxx_x1 = sum2(acc)-sum2(ic); 94 LL maxx_y1 = sum1(acc)-sum1(ic); 95 akk[i] = akk[i-1] - (smal_x1)*ask[i].x + smal_y1 - maxx_y1 + maxx_x1*ask[i].x; 96 add1(ic,-ask[i].x,cn); 97 add2(ic,-1,cn); 98 } 99 }100 else if(ask[i].op == 1)101 {102 int ic = my[ask[i].x];103 LL smal_x1 = sum2(ic-1);104 LL smal_y1 = sum1(ic-1);105 LL maxx_x1 = sum2(acc)-sum2(ic);106 LL maxx_y1 = sum1(acc)-sum1(ic);107 akk[i] = akk[i-1] + (smal_x1)*ask[i].x - smal_y1 + maxx_y1 - maxx_x1*ask[i].x;108 add1(ic,ask[i].x,cn);109 add2(ic,1,cn);110 }111 else112 {113 akk[i] = akk[i-1];114 printf("%lld\n",akk[i]);115 }116 }117 return 0;118 }119 LL sum1(int i)120 {121 LL s = 0;122 while(i>0)123 {124 s+=bit_sum[i];125 i -= i & -i;126 }127 return s;128 }129 void add1(int i,LL x,int n)130 {131 while(i <= n)132 {133 bit_sum[i] += x;134 i += i&(-i);135 }136 }137 LL sum2(int i)138 {139 LL s = 0;140 while(i>0)141 {142 s+=bit_ans[i];143 i -= i & -i;144 }145 return s;146 }147 void add2(int i,LL x,int n)148 {149 while(i <= n)150 {151 bit_ans[i] += x;152 i += i&(-i);153 }154 }
1394 差和问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。