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

void solve(int Q, int type[], long long first[], long long second[]) {
vector 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
6
1 5 1
1 6 3
2 2 5
2 4 8
1 2 2
2 4 8

Sample Output
4
11
9

题意：给你n个操作，有两种操作，1 x y表示你得到了x个y，2 x y表示输出在你得到的这些数中，第x小到第y小的数的和是多少
离线+线段树？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const int maxn = 2e6 + 5;
struct Tree {
    ll lson, rson;
    ll sum;
    ll cnt;
}tree[maxn];
int n;
struct Q {
    ll ty, first, second;
}q[maxn];
int Hash[maxn], len;

void build(int i, int l, int r) {
    tree[i].lson = l; tree[i].rson = r;
    if(l == r) {
        return ;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
}

void pushup(int i) {
    tree[i].cnt = tree[i * 2].cnt + tree[i * 2 + 1].cnt;
    tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
    tree[i].sum %= mod;
}

void insert(int i, int x, ll cnt) {
    if(tree[i].lson == tree[i].rson) {
        tree[i].cnt += cnt;
        tree[i].sum = (tree[i].sum + cnt * 1LL * Hash[x]) % mod;
        return ;
    }
    int mid = (tree[i].lson + tree[i].rson) / 2;
    if (mid >= x) {
        insert(i * 2, x, cnt);
    } else {
        insert(i * 2 + 1, x, cnt);
    }
    pushup(i);
}

struct Node {
    ll first, second, va;
};

Node Kth(int i, ll k) { //返回1到当前节点的数量 和 1到前一个节点数量， 和当前节点的值（用于离散化回来） 
    Node p;
    if(tree[i].lson == tree[i].rson) {
        p.first = 0; p.second = tree[i].cnt;
        p.va = tree[i].lson;
        return p;
    }
    int mid = (tree[i].lson + tree[i].rson) / 2;
    long long cnt = tree[i * 2].cnt;
    if(cnt >= k) {
        return Kth(i * 2, k);
    } else {
        p = Kth(i * 2 + 1, k - cnt);
        p.first += cnt;
        p.second += cnt;
        return p;
    }
}

ll sum(int i, int l, int r) {
    if(tree[i].lson == l && tree[i].rson == r)  {
        return tree[i].sum;
    }
    int mid = (tree[i].lson + tree[i].rson) / 2;
    if (mid >= r) {
        return sum(i * 2, l, r);
    } else if (l > mid) {
        return sum(i * 2 + 1, l, r);
    } else {
        return (sum(i * 2, l, mid) + sum(i * 2 + 1, mid + 1, r)) % mod;
    }
}

int main() {
    scanf("%d", &n);
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld", &q[i].ty, &q[i].first, &q[i].second);
        if(q[i].ty == 1) {
            Hash[++len] = q[i].second;
        }
    }
    sort(Hash + 1, Hash + len + 1);
    len = unique(Hash + 1, Hash + len + 1) - Hash - 1;
    for (int i = 1; i <= n; i++) { // 离散化 
        if(q[i].ty == 1) {
            q[i].second = lower_bound(Hash + 1, Hash + len + 1, q[i].second) - Hash;
        }
    }
    ll res1, res2, res3;
    for (int i = 1; i <= n; i++) {
        if(q[i].ty == 1) {
            insert(1, q[i].second, q[i].first);
        } else {
            Node L = Kth(1, q[i].first); //查询第first小的所有信息 
            Node R = Kth(1, q[i].second); //查询第second小的所有信息 
            if (L.va == R.va) { //如果都是同一个点 直接打印结果 
                ll x = q[i].second - q[i].first + 1;
                printf("%lld\n", (x * 1LL * Hash[L.va]) % mod);
            } else { //否则处理处两边的结果 + 中间的结果 
                res1 = res2 = res3 = 0; 
                ll cnt = L.second - L.first;
                ll xx = q[i].first - L.first;
                ll yy = cnt - xx + 1;
                res1 = (yy * Hash[L.va]) % mod;
                res3 = (q[i].second - R.first) * Hash[R.va] % mod;
                if(L.va + 1 < R.va) { //是否有中间 
                    res2 = sum(1, L.va + 1, R.va - 1) % mod;
                }
                printf("%lld\n", (res1 + res2 + res3) % mod);
            }
        }
    }
    return 0;
}