HDOJ 6464

先离线，离散化
在线段树维护区间和以及数量

#include <bits/stdc++.h>
using namespace std;

///#pragma GCC optimize(2)

#define Mode 1000000007

const int N = 1<<17;

struct node
{
    long long Sum;
    long long Cnt;
};

struct que
{
    int type;
    long long first;
    long long second;
};

long long Res[1<<17];

que A[1<<17];

node dat[2*N];

long long Date[1<<17];

void Init(void)
{
    for(int i = 0; i  < 2*N; i++)
    {
        dat[i].Sum = 0;
        dat[i].Cnt = 0;
    }
}
void update(int k, long long a)
{
    k += N-1;
    dat[k].Cnt += a;
    dat[k].Sum += ((Date[k-N+1]%Mode)*(a%Mode))%Mode;

    while(k > 0)
    {
        k = k/2;
        dat[k].Cnt = dat[k*2].Cnt + dat[k*2+1].Cnt;
        dat[k].Sum = (dat[k*2].Sum%Mode + dat[k*2+1].Sum %Mode) %Mode;
    }
}

int query(int k, long long b)
{
    if(k >= N && k <= 2*N-1)
        return Date[k - N+1]*b % Mode;

    if(dat[k].Cnt == b)
        return dat[k].Sum % Mode;

    if(dat[k].Cnt < b)
    {
        return (dat[k].Sum%Mode + query(k*2+1, b-dat[k].Cnt)%Mode) %Mode;
    }

    if(dat[k].Cnt > b)
    {
        if(dat[k*2].Cnt >= b)
            return query(k*2, b)%Mode;
        else
            return (dat[k*2].Sum%Mode + query(k*2+1, b-dat[k*2].Cnt)%Mode)%Mode;
    }
}


int q;

int main(void)
{
    freopen("G:\\data.txt", "r", stdin);
    cin >> q;
    int S = 0;

    for(int i = 0; i < q; i++)
    {
        cin >> A[i].type >> A[i].first >> A[i].second;
        if(A[i].type == 1)
        {
            Res[++S] = A[i].second;
        }
    }
    sort(Res+1, Res+S+1);
    S=unique(Res+1,Res+1+S)-(Res+1);
    for(int i = 1; i <= S; i++)
    {
        Date[i] = Res[i]%Mode;
    }
    Init();
    for(int i = 0; i < q; i++)
    {
        if(A[i].type == 1)
        {
            int cc = lower_bound(Res+1, Res+S+1, A[i].second) - Res;
            update(cc, A[i].first);
        }
        else if(A[i].type == 2)
        {
            long long c1 = query(1, A[i].first-1)%Mode;
            long long c2 = query(1, A[i].second);
            long long ANS = (c2 - c1+Mode) % Mode;
            cout << ANS << endl;
        }
    }
    return 0;
}