csp-s模拟测试52平均数，序列题解
题面：https://www.cnblogs.com/Juve/articles/11602244.html
平均数：
第k个平均数不好求，我们考虑二分，转化成平均数小于x的有几个
虑把序列中的每个数减去 x,则我们只需求区间和小于 0 的区间数量。
我们对这个序列求前缀和,则区间[L,R]和小于 0 当且仅当 SL-1>SR,
答案即为前缀和序列 S 的逆序对数量,使用经典的归并排序即可解决
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define int long long
#define double long double
using namespace std;
const int MAXN=1e5+5;
int n,k,ans=0;
double L=0.0,R=1e9+1,sum[MAXN],temp[MAXN],res,a[MAXN];
double max(double a,double b){
return a>b?a:b;
}
void merge_sort(int l,int r){
int mid,i,j,k;
if(l==r) return;
mid=(l+r)/2;
merge_sort(l,mid);merge_sort(mid+1,r);
i=l;j=mid+1;k=l;
while(i<=mid&&j<=r){
if(sum[i]>sum[j]){
ans+=mid-i+1;
temp[k]=sum[j];
j++;
k++;
}else{
temp[k]=sum[i];
i++;
k++;
}
}
while(i<=mid){
temp[k]=sum[i];
i++;
k++;
}
while(j<=r){
temp[k]=sum[j];
j++;
k++;
}
for(i=l;i<=r;i++)
sum[i]=temp[i];
}
bool check(double x){
ans=0;
sum[0]=0;
for(int i=1;i<=n;++i){
sum[i]=sum[i-1]+a[i]-x;
}
merge_sort(0,n);
return ans<k;
}
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;++i){
scanf("%Lf",&a[i]);
}
while(L<R-(1e-5)){
double mid=(L+R)/2.0;
if(check(mid)) L=mid;
else R=mid;
}
printf("%0.4Lf\n",L);
return 0;
}
序列：
考虑主席树，相当与对每一个位置建一棵动态开点权值线段树，
我们不能把所有区间插进去，我们插入询问，对于每一个位置，经过它的询问有很多，我们统计a[i]对整个答案的贡献
我们对每一个位置插入所有在这个位置上要查询的x，然后答案就是对于每一个位置i，在i所在的线段树中找小于a[i]的x的数量，这是a[i]对整个答案的贡献
修改后我们还像之前那样查询，如果将p位置更改为v，那么减去a[p]的贡献，在加上更改后的v对整个答案的贡献
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
#define re register
using namespace std;
const int MAXN=1e5+5;
int n,m,q,a[MAXN],ans,x[MAXN];
int root[MAXN],tot=0,ls[MAXN<<6],rs[MAXN<<6],tr[MAXN<<6];
struct node{
int pos,val;
};
vector<node>v[MAXN];
inline void insert(re int &k,re int pre,re int l,re int r,re int pos,re int val){
k=++tot;
ls[k]=ls[pre],rs[k]=rs[pre],tr[k]=tr[pre];
if(l==r){
tr[k]+=val;
return ;
}
re int mid=(l+r)>>1;
if(pos<=mid) insert(ls[k],ls[pre],l,mid,pos,val);
else insert(rs[k],rs[pre],mid+1,r,pos,val);
tr[k]=tr[ls[k]]+tr[rs[k]];
}
inline int query(re int k,re int l,re int r,re int opl,re int opr){
if(opl<=l&&r<=opr) return tr[k];
re int mid=(l+r)>>1,res=0;
if(opl<=mid) res+=query(ls[k],l,mid,opl,opr);
if(opr>mid) res+=query(rs[k],mid+1,r,opl,opr);
return res;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&q);
for(re int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
for(re int i=1,l,r;i<=m;++i){
scanf("%lld%lld%lld",&l,&r,&x[i]);
v[l].push_back((node){x[i],1});
v[r+1].push_back((node){x[i],-1});
}
for(re int i=1;i<=n;++i){
root[i]=root[i-1];
int N=v[i].size();
for(re int j=0;j<N;++j){
insert(root[i],root[i],1,n,v[i][j].pos,v[i][j].val);
}
}
for(re int i=1;i<=n;++i){
ans+=query(root[i],1,n,1,a[i]);
}
printf("%lld\n",ans);
for(re int i=1,p,v;i<=q;++i){
scanf("%lld%lld",&p,&v);
p^=ans,v^=ans;
ans+=(query(root[p],1,n,1,v)-query(root[p],1,n,1,a[p]));
a[p]=v;
printf("%lld\n",ans);
}
return 0;
}
版权声明：本文为Juve原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。