HDU 6464 /// 权值线段树

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意：

共Q次操作操作有两种

操作一在序列尾部加入f[i]个s[i]

操作二查询序列第f[i]小到第s[i]小之间的总和

离线操作把序列内的值离散化

然后利用离散化后的值在线段树上对应权值操作

权值线段树维护权值对应的值的个数和总和

查询用s[i]的前缀和减去f[i]-1的前缀和具体看注释

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,j,sizeof(i))
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define gcd(i,j) __gcd(i,j);
const int N=1e5+;
const int mod=;LL p[N], f[N], s[N];
LL cop[N], tot;#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
LL num[N<<], sum[N<<];
void pushUp(int rt) {
num[rt]=num[rt<<]+num[rt<<|];
sum[rt]=(sum[rt<<]+sum[rt<<|])%mod;
}
void update(LL ind,LL k,int l,int r,int rt) {
if(l==r) {
num[rt]+=k; // 这个值在序列内的个数
sum[rt]=(sum[rt]+cop[ind]*k)%mod; // 总和
return ;
}
int m=(l+r)>>;
if(m>=ind) update(ind,k,lson);
else update(ind,k,rson);
pushUp(rt);
}
LL query(LL k,int l,int r,int rt) {
if(k==) return ;
if(l==r) return k*cop[l]%mod;
// 在l位置还差k个 k可能不需要num[l]那么多
// 所以应该是k*cop[l] 而不是sum[l]
int m=(l+r)>>, L=rt<<;
if(num[L]<=k) return (sum[L]+query(k-num[L],rson))%mod;
// 左儿子区间不足k个那么左儿子区间的总和+右儿子区间差的个数的总和
else return query(k,lson);
// 左儿子区间的数已超过k个就在左儿子区间内继续缩小
}int main()
{
mem(num,0LL); mem(sum,0LL);
int q; scanf("%d",&q);
inc(i,,q) scanf("%lld%lld%lld",&p[i],&f[i],&s[i]);
tot=;
inc(i,,q) if(p[i]==)
cop[++tot]=s[i];
sort(cop+,cop++tot);
tot=unique(cop+,cop++tot)-cop-;
inc(i,,q) {
if(p[i]==) {
int ind=lower_bound(cop+,cop++tot,s[i])-cop;
update(ind,f[i],,tot,); // 离散化后的值在对应权值位置操作
}
else {
LL R=query(s[i],,tot,);
LL L=query(f[i]-,,tot,);
printf("%lld\n",(R-L+mod)%mod);
}
} return ;
}