http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=843

C++版本一

https://www.cnblogs.com/kls123/p/10542573.html

题解：

每次1操作会往序列底加first个second，first 和 second 都是最大1e9的数据，每次2操作询问序列中第first到第second个数的和

一开始就感觉有点像线段树，输入数据太大我们可以离线处理把数据离散化下，然后扔到线段树上，维护两个数组：

sum: 区间数的值的和  num: 区间数的数量和  ,对于每次询问的first和second，我们找到第first个和第second个分别是哪两个数字，

如果两个数字不相同，那么就先算出分别取了多少个这两个数字，对于两个数字中间的数字和我们可以直接用线段树区间求和得到

 

感觉应该有更简单的写法，不过一开始思路就往线段树上偏了，干脆直接用线段树写了。。。。。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid ll m = (l + r) >> 1
const ll mod = 1000000007;
const ll M = 2e5+10;
ll sum[M<<2],num[M<<2],b[M],op[M],vis[M ];
struct node{
    ll x,y;
}a[M];
void update(ll p,ll c,ll l,ll r,ll rt){
     if(l == r){
        sum[rt] = (sum[rt]+(b[p]*c)%mod)%mod;
        num[rt] += c;
        return ;
     }
     mid;
     if(p <= m) update(p,c,lson);
     else update(p,c,rson);
     sum[rt] = (sum[rt<<1] + sum[rt<<1|1])%mod;
     num[rt] = num[rt<<1] + num[rt<<1|1];
}

ll ask(ll L,ll R,ll l,ll r,ll rt){  //求区间[L,R]的区间和
    if(L <= l&&R >= r){
        return sum[rt];
    }
    mid;
    ll ret = 0;
    if(L <= m) ret = (ret + ask(L,R,lson))%mod;
    if(R > m) ret = (ret + ask(L,R,rson))%mod;
    return ret;
}

ll ask1(ll p,ll l,ll r,ll rt){  //寻找序列中第p个是那个数字
    if(num[rt] >= p&& num[rt] - vis[r] < p){
        return r;
    }
    mid;
    if(p <= num[rt<<1]) ask1(p,lson);
    else ask1(p-num[rt<<1],rson);
}

ll ask2(ll L,ll R,ll l,ll r,ll rt){  //求区间[L,R]中有多少个数字
    if(L <= l&&R >= r){
        return num[rt];
    }
    mid;
    ll ret = 0;
    if(L <= m) ret += ask2(L,R,lson);
    if(R > m) ret += ask2(L,R,rson);
    return ret;
}

int main()
{
    ll n,cnt = 0;
    cin>>n;
    for(ll i = 1;i <= n;i ++){
        cin>>op[i]>>a[i].x >> a[i].y;
        if(op[i] == 1) b[++cnt] = a[i].y;
    }
    sort(b+1,b+1+cnt);
    for(ll i = 1;i <= n;i ++){
        if(op[i] == 1){
            ll id = lower_bound(b+1,b+1+cnt,a[i].y)-b;
            update(id,a[i].x,1,cnt,1);
            vis[id] += a[i].x;
        }
        else{
            ll l = ask1(a[i].x,1,cnt,1);
            ll r = ask1(a[i].y,1,cnt,1);
            if(l == r){
                cout<<(b[l]*((a[i].y-a[i].x+1)%mod))%mod<<endl;
            }
            else{
                ll l = ask1(a[i].x,1,cnt,1);
                ll r = ask1(a[i].y,1,cnt,1);
                ll k1 = (((ask2(1,l,1,cnt,1) - a[i].x+1)%mod)*b[l])%mod;
                ll k2 = (((a[i].y - ask2(1,r-1,1,cnt,1))%mod)*b[r])%mod;
                ll k = 0;
                k = ask(l+1,r-1,1,cnt,1);
                cout<<(k+k1+k2)%mod<<endl;
            }
        }
    }
}