树状数组+离散化)"/>
AtCoder 2581 Meaningful Mean(树状数组+离散化)
E - Meaningful Mean
Time limit : 2sec / Memory limit : 256MB
Score : 600 points
Problem Statement
You are given an integer sequence of length N, a= {a1,a2,…,aN}, and an integer K.
a has N(N+1)⁄2 non-empty contiguous subsequences, {al,al+1,…,ar} (1≤l≤r≤N). Among them, how many have an arithmetic mean that is greater than or equal to K?
Constraints
- All input values are integers.
- 1≤N≤2×105
- 1≤K≤109
- 1≤ai≤109
Input
Input is given from Standard Input in the following format:
N K a1 a2 : aN
Output
Print the number of the non-empty contiguous subsequences with an arithmetic mean that is greater than or equal to K.
Sample Input 1
Copy3 6 7 5 7
Sample Output 1
Copy5
All the non-empty contiguous subsequences of a are listed below:
- {a1} = {7}
- {a1,a2} = {7,5}
- {a1,a2,a3} = {7,5,7}
- {a2} = {5}
- {a2,a3} = {5,7}
- {a3} = {7}
Their means are 7, 6, 19⁄3, 5, 6 and 7, respectively, and five among them are 6 or greater. Note that {a1} and {a3} are indistinguishable by the values of their elements, but we count them individually.
Sample Input 2
Copy1 2 1
Sample Output 2
Copy0
Sample Input 3
Copy7 26 10 20 30 40 30 20 10
Sample Output 3
Copy13【思路】
这道题给了一串整数,要求的是算数平均数大于等于K的区间的数目。也就是a1,a2,a3,...,an,求任意[l,r]的区间和s(其中l <= r),若s/(r-l+1) >= K,则给答案加1。为了便于观察,我们将下标改为从0开始,用下面这种形式变化,可以得到br >= bl这种形式的式子,那么问题就转化成了求一对l和r(其中0 <= l < r <= n),使得bl <= br的l和r的对数,也就是求顺序对的对数。
很自然地就能想到用树状数组来维护,由于b可能非常大,所以要进行离散化。离散化的方式在这里有两种方式,
一是将b的值进行排序,从小到大扫一遍,找前面的数里头有多少下标小于等于当前数(由于下标不会重复,所以与严格小于是一样的),然后加起来,不过要尤其注意排序的时候若b值相等,要将下标小的排在前面,并且得注意处理0下标。
二是将b原序保留在s里,再对b排序去重离散化,然后把s扫一遍,找直到当前下标有多少个数小于等于当前数。
显然第二种方法又要排序,又要去重,又要保留原数组,所以时空复杂度都稍逊于第一种方法,但是第一种方法较易出错。我自己先写的第一种总是WA,看了同学代码后写出了第二种,然后突然明白第一种应该要双关键字排序,又改了改才对了。这里也附上两种写法。
【代码1】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int MAXN=200005;struct node{long long num;int id;bool operator<(const node &another)const{if(num==another.num)return id<another.id;return num<another.num;}
};int n,k;
long long a[MAXN];
node b[MAXN];int lowbit(int x)
{return (x&-x);
}void modify(int x,int num)
{if(x==0){a[x]+=(long long)num;return;}while(x<=n){a[x]+=(long long)num;x+=lowbit(x);}
}long long sum(int x)
{long long ans=a[0];while(x>0){ans+=a[x];x-=lowbit(x);}return ans;
}int main()
{scanf("%d %d",&n,&k);b[0].num=0;b[0].id=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);b[i].num=b[i-1].num+(long long)(x-k);b[i].id=i;}sort(b,b+1+n);long long cnt=0;memset(a,0,sizeof(a));for(int i=0;i<=n;i++){if(b[i].id>0)cnt+=sum(b[i].id-1);modify(b[i].id,1);}printf("%lld\n",cnt);return 0;
}
【代码2】
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;const int MAXN=200005;int n,k;
long long a[MAXN],s[MAXN],b[MAXN];
map<long long,int> mp;int lowbit(int x)
{return (x&-x);
}void modify(int x,int num)
{while(x<=n+1){a[x]+=(long long)num;x+=lowbit(x);}
}long long sum(int x)
{long long ans=0;while(x>0){ans+=a[x];x-=lowbit(x);}return ans;
}int main()
{scanf("%d %d",&n,&k);s[0]=0;b[0]=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);s[i]=s[i-1]+(long long)(x-k);b[i]=s[i];}sort(b,b+1+n);int tot=0;for(int i=0;i<=n;i++)if(!mp.count(b[i]))mp[b[i]]=++tot;long long cnt=0;memset(a,0,sizeof(a));for(int i=0;i<=n;i++){cnt+=sum(mp[s[i]]);modify(mp[s[i]],1);}printf("%lld\n",cnt);return 0;
}
更多推荐
AtCoder 2581 Meaningful Mean(树状数组+离散化)
发布评论