51 nod 1394 1394 差和问题(线段树)-白红宇

51 nod 1394 1394 差和问题(线段树)

阅读量：5949 次

发布时间：2019-06-19

本文共 3251 字，大约阅读时间需要 10 分钟。

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示例

/*51 nod 1394 1394 差和问题(线段树)problem:有一个多重集合S（即里面元素可以有重复），初始状态下有n个元素，对他进行如下操作：1、向S里面添加一个值为v的元素。输入格式为1 v2、向S里面删除一个值为v的元素。输入格式为2 v3、询问S里面的元素两两之差绝对值之和。输入格式为3solve:每次向序列中添加数x时. 会对总体贡献: a[i]-x (a[i] > x), x-a[i] (a[i] < x)就比x小的数而言, 会贡献 val - num*x (val:小于x的数的和  num:小于x的数的个数)而删除操作就等同于将添加反过来弄一下于是就成了计算序列中小于(大于)x的数的个数以及它们的总价值,线段树能实现.但是数能达到1e9,而n却只有1e6,离散化处理一下hhh-2016/09/06-17:09:25*/#pragma comment(linker,"/STACK:124000000,124000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define lson i<<1#define rson i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define scanfi(a) scanf("%d",&a)#define scanfs(a) scanf("%s",a)#define scanfl(a) scanf("%I64d",&a)#define scanfd(a) scanf("%lf",&a)#define key_val ch[ch[root][1]][0]#define eps 1e-7#define inf 0x3f3f3f3f3f3f3f3fusing namespace std;const ll mod = 1000000007;const int maxn = 200050;const double PI = acos(-1.0);const int limit = 33;ll bin[maxn];map
               
                mp;template
                
                  void read(T&num) { char CH; bool F=false; for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar()); for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar()); F && (num=-num);}int stk[70], tp;template
                 
                   inline void print(T p) { if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + '0'); putchar('\n');}struct node{ int l,r; ll num,val;} tree[maxn << 2];void push_up(int i){ tree[i].val = tree[lson].val + tree[rson].val; tree[i].num = tree[lson].num + tree[rson].num;}void build(int i,int l,int r){ tree[i].l = l,tree[i].r = r; tree[i].val= tree[i].num = 0; if(l == r) { return; } int mid = (l + r) >> 1; build(lson,l,mid); build(rson,mid+1,r);}int ed;void update(int i,int k,ll va){ if(tree[i].l == tree[i].r && tree[i].l == k) { tree[i].num += va; if(va == 1) tree[i].val += bin[k]; else tree[i].val -= bin[k]; return ; } int mid = (tree[i].l+tree[i].r )>> 1; if(k <= mid) update(lson,k,va); else update(rson,k,va); push_up(i);}ll tval,tnum;void query(int i,int l,int r){ if(l > r) { tval = tnum = 0;return; } if(tree[i].l >= l && tree[i].r <= r) { tval += tree[i].val; tnum += tree[i].num; return ; } int mid = (tree[i].l + tree[i].r ) >> 1; if(l <= mid) query(lson,l,r); if(r > mid) query(rson,l,r); push_up(i);}ll a[maxn/2];int num[maxn];struct Query{ int id; ll x;} qry[maxn/2];int main(){// freopen("in.txt","r",stdin); int n,q,op; while(scanfi(n)!=EOF) {// clr(num,0); mp.clear(); int cnt = 0; read(q); for(int i = 1; i <= n; i++) { read(a[i]); bin[cnt++] = a[i];// update(1,x,1); }// cout << q <