类型

如何设计一门语言（九）——类型

类型是了解编程语言的重要一环。就算是你喜欢动态类型语言，为了想实现一个靠谱的东西，那也必须了解类型。举个简单的例子，我们都知道+和-是对称的——当然这只是我们的愿望了，在javascript里面，"1"+2和"1"-2就不是一回事。这就是由于不了解类型的操作而犯下的一些滑稽的错误。什么，你觉得因为"1"的类型是string所以"1"+2就应该是"12"？啐！"1"的类型是(string | number)，这才是正确的做法。

了解编程语言的基本原理并不意味着你一定要成为一名编译器的前端，正如同学习Haskell可以让你的C++写得更好一样，如果你知道怎么设计一门语言，那遇到语言里面的坑，你十有八九可以当场看到，不会跳进去。当然了，了解编程语言的前提是你是一个优秀的程序员，至少要写程序，对吧。于是我这里推荐几门语言是在此之前要熟悉的。编程语言有好多种，每一种都有其代表作，为了开开眼界，知道编程语言可以设计成什么样子，你至少应该学会：

C++
C#
F#
Haskell
Ruby
Prolog

其实这一点也不多，因为只是学会而已，知道那些概念就好了，并不需要你成为一个精通xx语言的人。那为了了解类型你应该学会什么呢？没错——就是C++了！很多人可能不明白，为什么长得这么难看的C++竟然有这么重要的作用呢？其实如果详细了解了程序设计语言的基本原理之后，你会发现，C++在除了兼容那个可怜的C语言之外的那些东西，是设计的非常科学的。当然现在讲这些还太早，今天的重点是类型。

如果你们去看相关的书籍或者论文的话，你们会发现类型这个领域里面有相当多的莫名其妙的类型系统，或者说名词。对于第一次了解这个方面的人来说，熟练掌握Haskell和C++是很有用的，因为Haskell可以让你真正明白类型在程序里面的重要做哟的同时。几乎所有流行的东西都可以在C++里面找到，譬如说：

面向对象→class
polymorphic type→template
intersection type→union / 函数重载
dependent type→带数字的模板类型
System F→在泛型的lambda表达式里面使用decltype（看下面的例子）
sub typing的规则→泛型lambda表达式到函数指针的隐式类型转换

等等等等，因有尽有，取之不尽，用之不竭。你先别批判C++，觉得他东西多所以糟糕。事实是，只要编译器不用你写，那一门语言是不可能通过拿掉feature来使它对你来说变得更牛逼的。不知道为什么有那么多人不了解这件事情，需要重新去念一念《形式逻辑》，早日争取做一个靠谱的人。

泛型lambda表达式是C++14（没错，是14，已经基本敲定了）的内容，应该会有很多人不知道，我在这里简单地讲一下。譬如说要写一个lambda表达式来计算一个容器里所有东西的和，但是你却不知道容器和容器里面装的东西是什么。当然这种情况也不多，但是有可能你需要把这个lambda表达使用在很多地方，对吧，特别是你#include <algorithm>用了里面超好用的函数之后，这种情况就变得常见了。于是这个东西可以这么写：

auto lambda = [](const auto& xs)
{
    decltype(*xs.begin()) sum = 0;
    for(auto x : xs)
    {
        sum += x;
    }
    return sum;
};

于是你就可以这么用了：

vector<int> a = { ... };
list<float> b = { ... };
deque<double> c = { ... };

int sumA = lambda(a);
float sumB = lambda(b);
double sumC = lambda(c);

然后还可以应用sub typing的规则把这个lambda表达式转成一个函数指针。C++里面所有中括号不写东西的lambda表达式都可以被转成一个函数指针的，因为他本来就可以当成一个普通函数，只是你为了让业务逻辑更紧凑，选择把这个东西写在了你的代码里面而已：

doube(*summer)(const vector<double>&);
summer = lambda;

只要搞明白了C++之后，那些花里胡俏的类型系统的论文的概念并不难理解。他们深入研究了各种类型系统的主要原因是要做系统验证，证明这个证明那个。其实编译器的类型检查部分也可以当成是一个系统验证的程序，他要检查你的程序是不是有问题，于是首先检查系统。不过可惜的是，除了Haskell以外的其他程序语言，就算你过了类型系统检查，也不见得你的程序就是对的。当然了，对于像javascript这种动态类型就罢了还那么多坑（ruby在这里就做得很好）的语言，得通过大量的自动化测试来保证。没有类型的帮助，要写出同等质量的程序，需要花的时间要更多。什么？你不关心质量？你不要当程序员了！是因为老板催得太紧？我们Microsoft最近有招聘了，快来吧，可以慢慢写程序！

不过正因为编译器会检查类型，所以我们其实可以把一个程序用类型武装起来，使得错误的写法会变成错误的语法被检查出来了。这种事情在C++里面做尤为方便，因为它支持dependent type——好吧，就是可以在模板类型里面放一些不是类型的东西。我来举一个正常人都熟练掌握的例子——单位。

一、类型检查（type rich programming）

我们都知道物理的三大基本单位是米、秒和千克，其它东西都可以从这些单位拼出来（大概是吧，我忘记了）。譬如说我们通过F=ma可以知道力的单位，通过W=FS可以知道功的单位，等等。然后我们发现，单位之间的关系都是乘法的关系，每个单位还带有自己的幂。只要弄清楚了这一点，那事情就很好做了。现在让我们来用C++定义单位：

template<int m, int s, int kg>
struct unit
{
    double value;

    unit():value(0){}
    unit(double _value):value(_value){}
};

好了，现在我们要通过类型系统来实现几个操作的约束。对于乘除法我们要自动计算出单位的同时，加减法必须在相同的单位上才能做。其实这样做还不够完备，因为对于任何的单位x来讲，他们的差单位Δx还有一些额外的规则，就像C#的DateTime和TimeSpan一样。不过这里先不管了，我们来做出加减乘除几个操作：

template<int m, int s, int kg>
unit<m, s, kg> operator+(unit<m, s, kg> a, unit<m, s, kg> b)
{
    return a.value + b.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator-(unit<m, s, kg> a, unit<m, s, kg> b)
{
    return a.value - b.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator+(unit<m, s, kg> a)
{
    return a.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator-(unit<m, s, kg> a)
{
    return -a.value;
}

template<int m1, int s1, int kg1, int m2, int s2, int kg2>
unit<m1+m2, s1+s2, kg1+kg2>operator*(unit<m1, s1, kg1> a, unit<m2, s2, kg2> b)
{
    return a.value * b.value;
}

template<int m1, int s1, int kg1, int m2, int s2, int kg2>
unit<m1-m2, s1-s2, kg1-kg2>operator/(unit<m1, s1, kg1> a, unit<m2, s2, kg2> b)
{
    return a.value / b.value;
}

但是这个其实还不够，我们还需要带单位的值乘以或除以一个系数的代码。为什么不能加减呢？因为不同单位的东西本来就不能加减。系数其实是可以描写成unit<0, 0, 0>的，但是为了让代码更紧凑，于是多定义了下面的四个函数：

template<int m, int s, int kg>
unit<m, s, kg> operator*(double v, unit<m, s, kg> a)
{
    return v * a.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator*(unit<m, s, kg> a, double v)
{
    return a.value * v;
}

template<int m, int s, int kg>
unit<m, s, kg> operator/(double v, unit<m, s, kg> a)
{
    return v / a.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator/(unit<m, s, kg> a, double v)
{
    return a.value / v;
}

我们已经用dependent type之间的变化来描述了带单位的量的加减乘除的规则。这看起来好像很复杂，但是一旦我们加入了下面的新的函数，一切将变得简单明了：

constexpr unit<1, 0, 0> operator""_meter(double value)
{
    return value;
}

constexpr unit<0, 1, 0> operator""_second(double value)
{
    return value;
}

constexpr unit<0, 0, 1> operator""_kilogram(double value)
{
    return value;
}

constexpr unit<1, -2,1> operator""_N(double value) // 牛不知道怎么写-_-
{
    return value;
}

constexpr unit<2, -2,1> operator""_J(double value) // 焦耳也不知道怎么写-_-
{
    return value;
}

然后我们就可以用来写一些神奇的代码了：

auto m = 16_kilogram; // unit<0, 0, 1>(16)
auto s = 3_meter; // unit<1, 0, 0>(3)
auto t = 2_second; // unit<0, 1, 0>(2)
auto a = s / (t*t); // unit<1, -2, 0>(3/4)
auto F = m * a; // unit<1, -2, 1>(12)

下面的代码虽然也神奇，但因为违反了物理定律，所以C++编译器决定不让他编译通过：

auto W = F * s; // unit<2, -2, 1>(36)
auto x = F + W; // bang!

这样你还怕你在物理引擎里面东西倒腾来倒腾去然后公式手抖写错了吗？类似的错误是不可能发生的！除非系数被你弄错了……如果没有unit，要用原始的方法写出来：

double m = 16;
double s = 3;
double t = 2;
double a = s / (t*t);
double F = m * a;
double W = F * s;
double x = F + W; //????

时间过得久了以后，根本不知道是什么意思了。所以为了解决这个问题，我们得用应用匈牙利命名法（这个不是那个臭名昭著的你们熟悉的傻逼（系统）匈牙利命名法）。我举个例子：

string dogName = "kula";
Person person;
person.name = dogName;

这个代码大家一看就知道不对对吧，这就是应用匈牙利命名法了。我们通过给名字一个单位——狗的——来让person.name = dogName;这句话显得很滑稽，从而避免低级错误的发生。上面的unit就更进一步了，把这个东西带进了类型系统里面，就算写出来不滑稽，编译器都会告诉你，错误的东西就是错误的。

然后大家可能会问，用unit这么写程序的性能会不会大打折扣呀？如今已经是2013年了，靠谱的C++编译器编译出来的代码，跟你直接用几个double倒腾来倒腾去的代码其实是一样的。C++比起其他语言的抽象的好处就是，就算你要用来做高性能的程序，也不怕因为抽象而丧失性能。当然如果你使用了面向对象的技术，那就另当别论了。

注，上面这段话我写完之后贴到了粉丝群里面，然后九姑娘跟我讲了很多量纲分析的故事，然后升级到航空领域的check list，最后讲到了医院把这一技术引进了之后有效地阻止了手术弄错人等严重事故。那些特别靠谱的程序还得用C++来写，譬如说洛克希德马丁的战斗机，NASA的卫星什么的。

人的精力是有限的，需要一些错误规避来防止引进低级的错误或者负担，保留精力解决最核心的问题。很多软件都是这样的。譬如说超容易配置的MSBuild、用起来巨爽无比的Visual Studio，出了问题反正用正版安装程序点一下repair就可以恢复的windows，给我们带来的好处就是——保留精力解决最核心的问题。编程语言也是如此，类型系统也是如此，人类发明出的所有东西，都是为了让你可以把更多的精力放在更加核心的问题上，更少的精力放在周边的问题上。

但是类型到处都出现其实也会让我们程序写起来很烦的，所以现代的语言都有第二个功能，就是类型推导了。

二、类型推导

这里讲的类型推导可不是Go语言那个半吊子的:=赋值操作符。真正的类型推导，就要跟C++的泛型lambda表达式、C#的linq语法糖，或者Haskell的函数一样，要可以自己计算出模板的类型参数的位置或者内容，才能全方位的实现什么类型都不写，都还能使用强类型和type rich programming带来的好处。C++的lambda表达式上面已经看到了，所以还是从Haskell一个老掉牙的demo开始讲起吧。

今天，我们用Haskell来写一个merge sort：

merge [] [] = []
merge [] xs = xs
merge xs [] = xs
merge (x:xs) (y:ys) = if x<y then x:(merge xs (y:ys)) else y:(merge (x:xs) ys)

mergeSort [] = []
mergeSort xs = merge (mergeSort a) (mergeSort b)
    where
        len = length xs
        a = take $ len `div` 2 $ xs
        b = drop $ len - len `div` 2 $ xs

我们可以很清楚的看出来，merge的类型是[a] –> [a] –> [a]，mergeSort的类型是[a] –> [a]。到底编译器是怎么计算出类型的呢？

首先，[]告诉我们，这是一个空列表，但是类型是什么不知道，所以他是forall a –> [a]。所以merge [] [] = []告诉我们，merge的类型至少是[a] –> [b] –> [c]。
其次，merge [] xs = xs告诉我们，merge的类型至少是[d] –> e –> e。这个类型跟[a]->[b]->[c]求一个交集就会得到merge的更准确的类型：[a] –> [b] –> [b]。
然后，merge xs [] = []告诉我们，merge的类型至少是f –> [g] –> f。这个类型跟[a] –> [b] –> [b]求一个交集就会得到merge的更准确的类型：[a] –> [a] –> [a]。
最后看到那个长长的式子，根据一番推导之后，会发现[a]->[a]->[a]就是我们要的最终类型了。
只要把相同的技术放在mergeSort上面，就可以得到mergeSort的类型是[a]->[a]了。

当然对于Haskell这种Hindley-Milner类型系统来说，只要我们在代码里面计算出所有类型的方程，然后一个一个去解，最后就可以收敛到一个最准确的类型上面了。倘若我们在迭代的时候发现收敛之后无解了，那这个程序就是错的。这种简单粗暴的方法很容易构造出一些只要人够蛋定就很容易使用的语言，譬如说Haskell。

Haskell看完就可以来看C#了。C#的linq真是个好东西啊，只要不把它看成SQL，那很多事情都可以表达的。譬如说是个人都知道的linq to object啦，后面还有linq to xml，linq to sql，reactive programming，甚至是parser combinator等等。一个典型的linq的程序是长这个样子的：

var w = 
    from x in xs
    from y in ys
    from z in zs
    select f(x, y, z);

光看这个程序可能看不出什么来，因为xs、ys、zs和f这几个单词都是没有意义的。但是linq的魅力正在这里。如果from和select就已经强行规定了xs、ys、zs和f的意思的话。那可扩展性就全没有了。因此当我们看到一个这样的程序的时候，其实可以是下面这几种意思：

W f(X x, Y y, Z z);

var /*IEnumerable<W>*/w = 
    from /*X*/x in /*IEnumerable<X>*/xs
    from /*Y*/y in /*IEnumerable<Y>*/ys
    from /*Z*/z in /*IEnumerable<Z>*/zs
    select f(x, y, z);

var /*IObservable<W>*/w = 
    from /*X*/x in /*IObservable<X>*/xs
    from /*Y*/y in /*IObservable<Y>*/ys
    from /*Z*/z in /*IObservable<Z>*/zs
    select f(x, y, z);

var /*IParser<W>*/w = 
    from /*X*/x in /*IParser<X>*/xs
    from /*Y*/y in /*IParser<Y>*/ys
    from /*Z*/z in /*IParser<Z>*/zs
    select f(x, y, z);

var /*IQueryable<W>*/w =
    from /*X*/x in /*IQueryable<X>*/xs
    from /*Y*/y in /*IQueryable<Y>*/ys
    from /*Z*/z in /*IQueryable<Z>*/zs
    select f(x, y, z);

var /*?<W>*/w = 
    from /*X*/x in /*?<X>*/xs
    from /*Y*/y in /*?<Y>*/ys
    from /*Z*/z in /*?<Z>*/zs
    select f(x, y, z);

相信大家已经看到了里面的pattern了。只要你有一个?<T>类型，而它又支持linq provider的话，你就可以把代码写成这样了。

不过我们知道，把程序写成这样并不是我们编程的目的，我们的目的是要让程序写得让具有同样知识背景的人可以很快就看懂。为什么要看懂？因为总有一天你会不维护这个程序的，这样就可以让另一个合格的人来继续维护了。一个软件是要做几十年的，那些只有一两年甚至只有半年生命周期的，只能叫垃圾了。

那现在让我们看一组有意义的linq代码。首先是linq to object的，求一个数组里面出现最多的数字是哪个：

var theNumber = (
    from n in numbers
    group by n into g
    select g.ToArray() into gs
    order by gs.Length descending
    select gs[0]
    ).First()

其次是一个parser，这个parser用来得到一个函数调用表达式：

IParser<FunctionCallExpression> Call()
{
    return
        from name in PrimitiveExpression()
        from _1 in Text("(")
        from arguments in
            many(
                Expression().
                Text(",")
            )
        from _2 in Text(")")
        select new FunctionCallExpression
        {
            Name = name,
            Arguments = arguments.ToArray(),
        };
}

我们可以看到，一旦linq表达式里面的元素都有了自己的名字，就不会跟上面的xyz的例子一样莫名其妙了。那这两个例子到底为什么要用linq呢？

第一个例子很简单，因为linq to object就是设计来解决这种问题的。

第二个例子就比较复杂一点了，为什么好好地parser要写成这样呢？我们知道，parser时可能会parse失败的。一个大的parser，里面的一些小部件失败了，那么大parser就要回滚，token stream的当前光标也要回滚，等等需要类似的一系列的操作。如果我们始终都让这些逻辑都贯穿在整个parser里面，那代码根本不能看。于是我们可以写一个linq provider，让SelectMany函数来处理所有的回滚操作，然后把parser写成上面这个样子。上面这个parser的所有的in左边是临时变量，所有的in右边刚好组成了一个EBNF文法：

PrimitiveExpression "(" [Expression {"," Expression}] ")"

最后的select语句告诉我们在所有小parser都parse成功之后，如何用parse得到的临时变量来返回一颗语法树。整个parsing的代码就会非常的容易看懂。当然，前提是你必须要懂的EBNF。不过一个不懂EBNF的人，又如何能写语法分析器呢。

那这跟类型推导有什么关系呢？我们会发现上面的所有linq的例子里面，除了函数签名以外，根本没有出现任何类型的声明。而且更重要的是，这些类型尽管没有写出来，但是每一个中间变量的类型都是自明的。当然这有一部分归功于好的命名方法——也就是应用匈牙利命名法了。剩下的部分是跟业务逻辑相关的。譬如说，一个FunctionCallExpression所调用的函数当然也是一个Expression了。如果这是唯一的选择，那为什么要写出来呢？

我们可以看到，正是因为有了类型推导，我们可以在写出清晰的代码的同时，还不需要花费那么多废话来指定各种类型。程序员都是怕麻烦的，无论复杂的方法有多好，他总是会选择简单的（废话，用复杂的那个不仅要加班修bug，还没有涨工资。用简单的那个，先让他过了，bug留给下一任程序员去头疼就好了——某web程序员如是说）。类型推导让type rich programming的程序写起来简单了许多。所以我们一旦有了类型推导，就可以放心大胆的使用type rich programming了。

三、大道理

有了type rich programming，就可以让编译器帮我们检查一些模式化的手都会犯的错误。让我们重温一下这篇文章前面的一段话：

人的精力是有限的，需要一些错误规避来防止引进低级的错误或者负担，保留精力解决最核心的问题。很多软件都是这样的。譬如说超容易配置的MSBuild、用起来巨爽无比的Visual Studio，出了问题反正用正版安装程序点一下repair就可以恢复的windows，给我们带来的好处就是——保留精力解决最核心的问题。编程语言也是如此，类型系统也是如此，人类发明出的所有东西，都是为了让你可以把更多的精力放在更加核心的问题上，更少的精力放在周边的问题上。

这让我想起了一个在微博上看到的故事：NASA的员工在推一辆装了卫星的小车的时候，因为忘记看check list，没有固定号卫星，结果卫星一推倒在了地上摔坏了，一下子没了两个亿的美元。

写程序也一样。一个代表力的变量，只能跟另一个代表力的变量相加，这就是check list。但是我们知道，每一个程序都相当复杂，check list需要检查的地方遍布所有文件。那难道我们在code review的时候可以一行一行仔细看吗？这是不可能的。正因为如此，我们要把程序写成“让编译器可以检查很多我们可能会手抖犯的错误”的形式，让我们从这些琐碎的事情里面解放出来。

银弹这种东西是不存在的，所以type rich programming能解决的事情就是防止手抖而犯错误。有一些错误不是手抖可以抖出来的，譬如说错误的设计，这并不是type rich programming能很好地处理的范围。为了解决这些事情，我们就需要更多可以遵守的best practice了。

当然，其中的一个将是DSL——domain specific language，领域特定语言了。敬请关注下一篇，《如何设计一门语言（十）——DSL与建模》。

树状数组学习笔记

一.理论准备

        从图上看出：C[1] = A[1]，C[2] = A[1] + A[2]，C[3] = A[3]，C[4] = A[1] + A[2] + A[3] + A[4]，C[5] = A[5]，C[6] = A[5] + A[6]，C[7] = A[7]，C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]。

二.发现规律

        1（0001）、3（0011）、5（0101）、7（0111）：单项之和

        2（0010）、6（0110）：连续两项之和

        4（0100）：连续四项之和

        8（1000）：连续八项之和

        假设二进制化后右端结尾0的个数为x，则改C数组项为A数组项的 2^x 项之和，因此C[i] 定义为由A数组某个数据开始累加到A[i]的和，累加的项数目为2^x。因此可以表示为C[i] = A[i - 2^x + 1] + …… + A[i - 1] + A[i]。

        考虑解决前k项和S[k]的问题：以k=7为例，7的二进制为0111。1出现在第一位上，因此会有一个单项之和a[7]，即C[7]；去掉第一位的1，数据变成0110，因此会有一个连续二项之和，即C[6]；去掉第二位的1，数据变成0100，因此还会有一个连续四项之和，即C[4]。表达出来为：

S[i] = C[i] + C[i-2^x] + ……直到i - 2^x <= 0。2^x的算法：i & (-i);假设i可以表示为A1B，其中B都为0，A' B'分别为A B的补码表示。(-i)二进制补码表示为取反加一：A'0B' + 1 = A'1B。因此i & (-i)就是A1B & A'1B = 1B = 2^x，得证。

        参考资料：http://blog.csdn.net/wyzxk888/article/details/7362286

三.二维树状数组

C[x][y]=sum(A[i][j])。其中，x-lowBit(x)+1<=i<=x，y-lowBit(y)+1<=j<=y，二维树状数组一般就是对矩阵的操作，更新、求值。。。

四.Java实现

import java.util.Scanner;

public class POJ1195 {

  static int instruction;

  static int n;//阶数

  static int map[][];

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    while(true) {

      instruction = sc.nextInt();

      if(0==instruction) {

        n = sc.nextInt();

        map = new int[n+2][n+2];

      }else if(3==instruction) {

        break;

      }else if(1==instruction) {

        int i = sc.nextInt()+1;

        int j = sc.nextInt()+1;

        int delta = sc.nextInt();

        update(i,j,delta);

      }else {

        int i = sc.nextInt()+1;

        int j = sc.nextInt()+1;

        int k = sc.nextInt()+1;

        int t = sc.nextInt()+1;

/*

         * 注意下标，包括k行，不包括i行；包括t列，不包括j列

         * 俩wa

*/

        int ans = getSum(k,t) - getSum(i-1,t)

            - getSum(k,j-1) + getSum(i-1,j-1);

        System.out.println(ans);

  private static int getSum(int x, int y) {

    int sum = 0;

/*

     * 下标从1开始，防止死循环

     * 因为若i或j是0，那么i-=lowbit(i)仍是0

*/

    for(int i=x; i>=1; i-=lowbit(i)) {

      for(int j=y; j>=1; j-=lowbit(j)) {

        sum += map[i][j];

    return sum;

  private static void update(int x, int y, int delta) {

    for(int i=x; i<n+2; i+=lowbit(i)) {

      for(int j=y; j<n+2; j+=lowbit(j)) {

        map[i][j] += delta;

  private static int lowbit(int x) {

/*

     * x&(x^(x-1))

     * 个人感觉上面的好理解

*/

    return  x&(-x);

-------------------------------------------------------------------------------------------

import java.util.Arrays;

import java.util.Scanner;

/*

题目描述：给定n个数字保证唯一的序列，如果两个数a[i],a[j]要交换，那么代价为a[i]+a[j]

求让他们变成升序的最小代价

分析：其实这个结果和逆序数有关，对某个位置i，如果前面比他大的有x个，那么a[i]至少要加x次

如果后面有y个比a[i]小，那么a[i]至少要加y次，也就是说用两个树状数组来分别维护当前位置时前面有多少比他大后面有多少个比他小

*/

/*

 * 原因很简单，大家都知道最少的交换次数是求逆序数。但是总花费最小是不是也是这样求？答案是：是。

 * 每次只能交换相邻两个数,否则1 5 3 4 2答案明显是交换5和2，就是7，实际是35

*/

public class HDU2838 {

/*

   * 这道题和第二届省赛的一题类似

   * 当时用的是置换群

*/

  //这个是暴躁度

  static final int MAXN = 100010;

  static long[] sum = new long[MAXN];

  static int[] cnt = new int[MAXN];

  static int[] a;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    while(sc.hasNext())  {

      Arrays.fill(cnt,0);

      Arrays.fill(sum,0);

      int n = sc.nextInt();

      a = new int[n+1];

      for(int i=1; i<=n; i++) {

        a[i] = sc.nextInt();

      long ans = 0;

      //前面比他大的

      for(int i=n; i>=1; i--) {

/*

         * modify函数在后面，防止多加本身

*/

        long num = getCnt(a[i]);

        ans += a[i]*num;

        ans += getSum(a[i]);

        modify(a[i]);

      System.out.println(ans);

  private static void modify(int x) {

    long delta = x;

    while(x<MAXN) {

      cnt[x] += 1;

      //不是加x，否则测试都不过

      sum[x] += delta;

      x += lowbit(x);

  private static long getSum(int x) {

    long ans = 0;

    while(x>=1) {

      ans += sum[x];

      x -= lowbit(x);

    return ans;

  private static int lowbit(int x) {

    return x&(-x);

  private static int getCnt(int x) {

    int ans = 0;

    while(x>=1) {

      ans += cnt[x];

      x -= lowbit(x);

    return ans;

---------------------------------------------------------------------------------------

import java.util.Scanner;

//点更新，求区间

public class HDU1166 {

  static int n;

  static int[] a;

  public static void main(String[] args) {

    int T;

    Scanner sc = new Scanner(System.in);

    T = sc.nextInt();

    int flag = 1;

    for(int j=1; j<=T; j++) {

      n = sc.nextInt();

      a = new int[n+1];

      for(int i=1; i<=n; i++) {

        modify(i,sc.nextInt());

      System.out.println("Case "+flag+":");

      String str;

      while(true) {

        str = sc.next();

        if(str.equals("End")) {

          break;

        }else if(str.equals("Query")) {

          int from = sc.nextInt();

          int to = sc.nextInt();

          int ans = getSum(to) - getSum(from-1);

          System.out.println(ans);

        }else if(str.equals("Add")) {

          int index = sc.nextInt();

          int delta = sc.nextInt();

          modify(index,delta);

        }else {

          int index = sc.nextInt();

          int delta = sc.nextInt();

          modify(index,-delta);

      flag++;

  private static int getSum(int to) {

    int sum = 0;

    while(to>=1) {

      sum += a[to];

      to -= lowbit(to);

    return sum;

  private static void modify(int index, int nextInt) {

    while(index<=n) {

      a[index] += nextInt;

      index += lowbit(index);

  private static int lowbit(int index) {

    return  index&(-index);

----------------------------------------------------------------------------------------

//区间更新，求点

import java.util.Scanner;

/*

 *第一次涂色是对区间[A,B]涂色一次，可以让nNum[nA]++,nNum[nB+1]--即可。因为这样对于区间[0,nA-1]的任意值i有

都要nNum[1]+nNum[2]+...+nNum[i] = 0。而对于区间[nA,nB]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。

对于区间[nB+1, nN]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。

   那么重复多次了。如果上述求和nNum[1]+nNum[2]+...+nNum[i] 刚好代表每个结点i的涂色次数，那么这个题就可解了。

 * #include <stdio.h>

int a[100005];

int main()

    int i,n,p,q,s;

    while(scanf("%d",&n)==1 && n)

        for(i = 1;i <= n;i ++)

            a[i] = 0;

        for(i = 1;i <= n;i ++)

            scanf("%d %d",&p,&q);

            a[p] ++;

            a[q+1] --;

        printf("%d",a[1]);

        s = a[1];

        for(i = 2;i <= n;i ++)

            s += a[i];

            printf(" %d",s);

        puts("");

    return 0;

*/

public class HDU1556 {

  static int array[];

  static int n;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int a,b;

    while(true) {

      n = sc.nextInt();

      array = new int[n+1];

      if(0==n) {

        break;

      for(int i=0; i<n; i++) {

        a = sc.nextInt();

        b = sc.nextInt();

        modify(a, 1);

        modify(b+1,-1);

      for(int i=1; i<=n; i++) {

        if(i<n) {

          System.out.print(getSum(i)+"");

        }else {

          System.out.println(getSum(i));

  private static int getSum(int index) {

    int sum = 0;

    for(int i=index; i>=1; i -= lowbit(i)) {

      sum += array[i];

    return sum;

  private static void modify(int index, int delta) {

    while(index<=n) {

      array[index] += delta;

      index += lowbit(index);

  private static int lowbit(int x) {

    //下标是0的话死循环

    return x&(-x);

分类: 编译器相关