传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6464
免费送气球
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 264 Accepted Submission(s): 53
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取模后输出。
第一行一个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均不大于目前已添加进序列的数的数量。
解题思路：
理解学习一波主席树：https://blog.csdn.net/g21wcr/article/details/82970228
1操作正常建权值线段树，查询操作则是利用 前缀和作差的方法来求区间和。
AC code：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL INF = 0x3f3f3f3f;
const LL MOD = 1e9+;
const int MAXN = 1e5+; LL sum[MAXN*], val[MAXN*];
int ls[MAXN*], rs[MAXN*];
int cnt; void update(int &Root, int L, int R, LL k, LL num)
{
if(!Root) Root = ++cnt;
sum[Root]+=k;
val[Root]+=(LL)k*num;
val[Root]%=MOD;
if(L == R) return;
int mid = (L+R)>>;
if(num <= mid) update(ls[Root], L, mid, k, num);
else update(rs[Root], mid+, R, k, num);
} LL query(int Root, int L, int R, LL k) //前 k 小的值的和
{
if(L == R) return 1LL*k*L%MOD;
int mid = (L+R)>>;
LL ans = ;
if(k > sum[ls[Root]])
ans = (val[ls[Root]] + query(rs[Root], mid+, R, k-sum[ls[Root]]))%MOD;
else
ans = query(ls[Root], L, mid, k); return ans%MOD;
} int main()
{
int Q_case, rt = ;
scanf("%d", &Q_case);
while(Q_case--){
int op;
LL L, R;
scanf("%d %lld %lld", &op, &L, &R);
if(op == ) update(rt, , 1e9, L, R);
else{
LL ans = (query(rt, , 1e9, R) - query(rt, , 1e9, L-)%MOD + MOD)%MOD; //类似于利用前缀和的差 来 求解区间的和
printf("%lld\n", ans);
}
}
return ;
}