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;

}

巴特西

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

最新文章

热门文章