免费送气球
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 581 Accepted Submission(s): 130
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均不大于目前已添加进序列的数的数量。
1 5 1
1 6 3
2 2 5
2 4 8
1 2 2
2 4 8
11
9
//6464-权值线段树
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int inf=0x3f3f3f3f;
const int mod=1e9+;
#define lson l,m
#define rson m+1,r ll sum[maxn*],val[maxn*];
int ls[maxn*],rs[maxn*];
int cnt; void update(int &rt,int l,int r,ll k,ll num)
{
if(!rt) rt=++cnt;
sum[rt]+=k;
cout<<rt<<" "<<sum[rt]<<endl;
val[rt]+=(ll)k*num;
val[rt]%=mod;
if(l==r){
return ;
} int m=(l+r)>>;
if(num<=m) update(ls[rt],lson,k,num);
else update(rs[rt],rson,k,num);
} ll query(int rt,int l,int r,ll k)
{
if(l==r){
return 1ll*k*l%mod;
} int m=(l+r)>>;
ll ans=;
if(k>sum[ls[rt]]) ans=(val[ls[rt]]+query(rs[rt],rson,k-sum[ls[rt]]))%mod;
else ans=query(ls[rt],lson,k);
return ans%mod;
} int main()
{
int q,rt=;
scanf("%d",&q);
while(q--){
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 ;
}