题意：

又到了GDUT一年一度的程序设计竞赛校赛的时间啦。同学们只要参加校赛，并且每解出一道题目就可以免费获得由ACM协会和集训队送出的气球一个。听到这个消息，JMC也想参加免费拿气球。可是，由于JMC太菜了而被禁止参赛，于是他找到你想让你帮忙参加比赛，可以通过执行下面的C++程序解决问题后获得气球并送给他。JMC保证了下面的程序一定能获得正确的结果。 

void solve(int Q, int type[], long long first[], long long second[]) { 

    vector<long long> vec; 

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

        if (type[i] == 1) { 

            long long k = first[i], val = second[i]; 

            while (k--) { 

                vec.push_back(val); 

            } 

        } 

        else if (type[i] == 2) { 

            sort(vec.begin(), vec.end()); 

            long long l = first[i] - 1, r = second[i], res = 0; 

            while (l < r) { 

                res = (res + vec[l++]) % 1000000007; 

            } 

            printf("%lld\n", res); 

        } 

    } 

} 

为防止你被JMC的代码搞到头晕目眩，JMC特意给出了问题的文字描述。已知一开始有一个空序列，接下来有Q次操作，每次操作给出type、first和second三个值。当type为1时，意味着该操作属于第一种操作：往序列尾部添加first个second数。当type为2时，意味着该操作属于第二种操作：查询序列中第first小至第second小的数值之和（一共有(second - first + 1)个数被累加），并将结果对1000000007取模后输出。

Input

单组数据 

第一行一个Q（1 <= Q <= 1e5），代表Q次操作。 

接下来有Q行，每行包含三个整数type、first和second；其中1 <= type <= 2。当type等于1时，0 <= first,second < 1e9。当type等于2时，1 <= first <= second，且first和second均不大于目前已添加进序列的数的数量。Output对于每次操作二，将结果对1000000007取模后输出。Sample Input

61 5 11 6 32 2 52 4 81 2 22 4 8

Sample Output

4119

首先了解离散化的概念：

数据的离散化

有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。

例如：

91054与52143的逆序对个数相同。

设有4个数：

1234567、123456789、12345678、123456

排序：123456<1234567<12345678<123456789

=>1<2<3<4

那么这4个数可以表示成：2、4、3、1

题解：首先将所有将要添加的数离散化，然后建立两颗线段树，分别维护区间内数的数量和区间和。对于操 作一，根据离散化后的值在线段树对应位置添加 k 个 val，并维护线段树每一个节点所代表区间的和。 对于操作二，首先将问题转化成两个前 k 小之和的查询，具体做法：传入参数 k 搜索线段树，先递归 检查左子区间的数的数量，如果小于当前 k，再传入当前 k-'左子区间的数的数量'作为更新后的参数 k 递归搜索右子区间；递归搜索时，应将满足数量条件（当前区间的数的数量小于等于 k）等于的区间和 累加并返回作为答案。 

参考博客：

#include 
     
      #include