HDU - 6464 免费送气球 （线段树）

又到了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

6
1 5 1
1 6 3
2 2 5
2 4 8
1 2 2
2 4 8

Sample Output

4
11
9

        一眼过去线段树。。。不过比赛的时候因为没有发现在type = 2的时候first以及second变量是可能大于1e9的（没给范围），所以一直在wa。。。很过分。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
long long sot[maxn]; int cnt = 1;
long long mi[maxn][4];
const int mod = 1000000007;
int Hash(long long x) {
	return lower_bound(sot + 1, sot + cnt, x) - sot;
}
long long sum[maxn * 4], add[maxn * 4];
void pushup(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	add[rt] = add[rt << 1] + add[rt << 1 | 1] % mod;
}
void build(int l, int r, int rt) {
	sum[rt] = 0;//初始化注意
	add[rt] = 0;
	if (l == r) {
		return;
	}
	int m = (l + r) >> 1;
	build(lson); build(rson);
}
void update(long long p, long long x, int l, int r, int rt) {
	if (l == r) {
		sum[rt] += x;
		add[rt] += 1LL * x*sot[p] % mod;
		add[rt] %= mod;
		return;
	}
	int m = (l + r) >> 1;
	if (p <= m)update(p, x, lson);
	else update(p, x, rson);
	pushup(rt);
}
long long query(int l, int r, int rt, long long k) {
	if (l == r) {
		return (1LL * sot[l] * k) % mod;
	}
	int m = (l + r) >> 1;
	long long ans = 0;
	if (k > sum[rt << 1]) {
		ans += (add[rt << 1] + query(rson, k - sum[rt << 1])) % mod;
	}
	else {
		ans += query(lson, k);
	}
	ans %= mod;
	return ans;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld%lld%lld", &mi[i][0], &mi[i][1], &mi[i][2]);
		//if (mi[i][1] >= 1e9 || mi[i][2] >= 1e9)cout << "*** you";
		if (mi[i][0] == 1)
			sot[cnt++] = mi[i][2];
	}
	build(1, cnt, 1);
	sort(sot + 1, sot + cnt);
	for (int i = 1; i <= n; i++) {
		long long a = mi[i][1], b = mi[i][2];
		if (mi[i][0] == 1) {
			b = Hash(b);
			update(b, a, 1, cnt, 1);
		}
		else {
			long long asum = 0, bsum = 0;
			if (a == 1) {
				asum = 0;
				bsum = query(1, cnt, 1, b);
			}
			else {
				asum = query(1, cnt, 1, a - 1);
				bsum = query(1, cnt, 1, b);
			}
			long long ans = (bsum - asum + mod) % mod;
			printf("%lld\n", ans);
		}
	}
	return 0;
}