csp-s模拟测试52平均数，序列题解

题面：https://www.cnblogs.com/Juve/articles/11602244.html

平均数：

第k个平均数不好求，我们考虑二分，转化成平均数小于x的有几个

虑把序列中的每个数减去 x,则我们只需求区间和小于 0 的区间数量。

我们对这个序列求前缀和,则区间[L,R]和小于 0 当且仅当 S_L-1>S_R,

答案即为前缀和序列 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;
}