51 nod 1394差と問題(アルゴリズムマラソン8)

1743 ワード
51 nod プログラミング アルゴリズム acm algorithm
集合Sがあり、初期状態でn個の要素があり、彼に対して以下の操作を行う.
1、Sにvの値を持つ要素を追加します.入力形式は1 v
2、Sにvの値を持つ要素を削除します.入力フォーマットは2 v
3、Sの中の要素の2つの差の絶対値の和を尋ねる.入力形式は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 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 5
1 2 3
3
1 4
3
2 2
3

Outputの例
4
10
6

問題を解く構想.
離散化+ツリー配列、1,2操作ごとにツリー配列でそれより大きい個数とそれより小さい個数を統計します
コード:
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=200000+100;
struct node
{
    int id;
    long long v;
}q[maxn];
long long a[maxn*4];
int b[maxn*4];
long long t[maxn];
long long cur[maxn];
int cou[maxn];
long long low(int k)
{
    return k&(-k);
}
void update(int k,long long v,int v2)
{
    while(k0)
    {
        anss+=a[k];
        ansn+=b[k];
        k-=low(k);
    }
}
int main()
{
    int n,qu;
    while(~scanf("%d%d",&n,&qu))
    {
        for(int i=0; i
機械学習アルゴリズム-k-means Clustering K平均クラスタリング
pythonバイナリデータの処理方法