{
ll v,x;
}a[50005];
bool cmp(A xx,A yy){
if(xx.v==yy.v) return xx.x<yy.x;
return xx.v<yy.v;
}
void addc(ll x,ll y){
for(;x<=50000;x+=(x&-x)) c[x]+=y;
}
void addt(ll x,ll y){
for(;x<=50000;x+=(x&-x)) t[x]+=y;
}
ll sumc(ll x){
ll sum=0;
for(;x;x-=(x&-x)) sum+=c[x];
return sum;
}
ll sumt(ll x){
ll sum=0;
for(;x;x-=(x&-x)) sum+=t[x];
return sum;
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].v,&a[i].x);
sort(a+1,a+n+1,cmp);
ll ans=0,max_num=0;
for(int i=1;i<=n;i++){
max_num=max(max_num,a[i].x);
//以下距离之间的比较限于所有音量比当前奶牛小的奶牛。
//a[i].x*sumc(a[i].x-1) 表示当前奶牛的距离*距离比当前奶牛小的奶牛个数。
//sumt(a[i].x-1) 表示所有距离比当前奶牛小的奶牛的距离和。
//sumt(max_num)-sumt(a[i].x) 表示所有距离比当前奶牛大的奶牛的距离之和。
//sumc(max_num)-sumc(a[i].x))*a[i].x 表示当前奶牛距离 * 距离比当前奶牛大的奶牛个数
ans+=a[i].v*(a[i].x*sumc(a[i].x-1)-sumt(a[i].x-1)+(sumt(max_num)-sumt(a[i].x))-(sumc(max_num)-sumc(a[i].x))*a[i].x) ;
addc(a[i].x,1);
addt(a[i].x,a[i].x);
}
cout<<ans<<endl;
return 0;
}
【summary】
这一题的重点给到题目中树状数组 \(t\)。主要收获为：以数值范围为下标的树状数组，能够处理的信息不仅限于个数。
【题意分析】
本题核心：如何判断一个区间内的贝壳是否重复？
当右端点 \(r\) 固定时，不论 \(l\) 取何值，对于任意一组重复的贝壳，都可以只统计最右端的贝壳。
原因：设一组重复贝壳中最右端的贝壳所在的位置为 \(pos_r\)，那么当 \(pos_r < l\) 时，其他贝壳也不可能算进统计中，当 $pos_r \ge l $时，无论其他贝壳是否被包括，对于区间的贡献都只有 \(1\)，因此，只计算最右端的贝壳即可。
因此，只需要将所有询问区间按 \(r\) 从小到大排序，计算答案即可。
【树状数组作用】
以位置为下标，每遇到一个新的数 \(num(num \le r)\)，判断它是否重复，如果重复，那么将上一个相同的数的贡献值 \(-1\)，将当前数的贡献值 \(+1\)。
对于一段区间 \([l,r]\)，答案为 \(sum(r)-sum(l-1)\)。
【code】
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,ask_r,prev,pos;
int vis[1000005],a[1000005],t[1000005],ans[1000005];
struct A{
int l,r,num;
}ask[1000005];
bool cmp(A x,A y){
return x.r<y.r;
}
int find(int pos){
ask_r=ask[pos++].r;
while(ask_r==ask[pos].r) pos++;
return pos-1;
}
void add(int x,int y){
for(;x<=n;x+=(x&-x)) t[x]+=y;
return;
}
int sum(int x){
int su=0;
for(;x;x-=(x&-x)) su+=t[x];
return su;
}
void replace(){
for(int i=ask[prev].r+1;i<=ask_r;i++){
if(vis[a[i]]!=0) add(vis[a[i]],-1);
add(i,1);
vis[a[i]]=i;
}
for(int i=prev+1;i<=pos;i++) ans[ask[i].num]=sum(ask[i].r)-sum(ask[i].l-1);
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].num=i;
sort(ask+1,ask+m+1,cmp);
while(1){
if(pos==m) break;
prev=pos;
pos=find(pos+1);
replace();
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}
【\(summary\)】
此题不再以数据范围为下标，而是以位置为下标。对于树状数组的应用更加灵活。在想到以最右端的贝壳为有价值的贡献时，对应到树状数组的操作就可以是上一个重复的数的贡献值 \(-1\)，当前数的贡献值 \(+1\)。然后用前缀和统计区间内的个数。算进一步的开阔思维。
与例题三不同，这一题给出的并不是一串，而是一个区间一个区间的给，但求得同样都是某一区间内贝壳的种类数。
【思路分析】
容易发现对于给定的区间，求与其有交集的区间的个数。将 \(L\) 记为区间头，\(R\) 记为区间尾，\(L\) 一定在给定区间的 \(R\) (包含 \(R\))的前面，但不被给定区间包含的区间，\(R\) 一定在给定区间的 \(L\) (不包含 \(L\))的前面。
因此只需要用两个树状数组统计头尾，用 \(R\) 以前所有的头减去 \(L\) 以前所有的尾即可。
【code】
点击查看代码
#inclu