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;
}
查看29道真题和解析