阳泉住房和城乡建设厅网站,苏州吴江网站建设,上海营销型网站seo,青岛市建设工程管理信息网正题
题目链接:https://www.ybtoj.com.cn/contest/68/problem/1 题目大意 nnn个数字的序列#xff0c;求有多少个区间[l,r][l,r][l,r]的平均值在[L,R][L,R][L,R]的范围内。 解题思路
如果让每个ai−xa_i-xai−x#xff0c;那么统计区间和大于等于111的区间数量就可以统计…正题
题目链接:https://www.ybtoj.com.cn/contest/68/problem/1 题目大意
nnn个数字的序列求有多少个区间[l,r][l,r][l,r]的平均值在[L,R][L,R][L,R]的范围内。 解题思路
如果让每个ai−xa_i-xai−x那么统计区间和大于等于111的区间数量就可以统计平均值大于xxx的区间数量那么我们让平均值大于等于LLL的减去平均值大于RRR的。
为了方便不离散化我们让下标和数值互换一下注意计算RRR时因为是大于的所以不能和LLL的方法相同。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
#define ll long long
using namespace std;
const ll N5e510;
ll n,L,R,p[N],w[N],t[N],a[N],fl;
bool cmp(ll x,ll y)
{return (w[x]w[y])?(fl?(xy):(xy)):(w[x]w[y]);}
void Change(ll x,ll val){x;while(xn1){t[x]val;xlowbit(x);}return;
}
ll Ask(ll x){ll ans0;x;while(x){anst[x];x-lowbit(x);}return ans;
}
ll solve(ll x,bool flag){flflag;memset(t,0,sizeof(t));for(ll i1;in;i)w[i]w[i-1]a[i]-x,p[i]i;ll ans0;p[n1]0;sort(p1,p2n,cmp);for(ll i1;in1;i){ansAsk(p[i]);Change(p[i],1);}return ans;
}
int main()
{freopen(sequence.in,r,stdin);freopen(sequence.out,w,stdout);scanf(%lld%lld%lld,n,L,R);for(ll i1;in;i)scanf(%lld,a[i]);ll asolve(L,0)-solve(R,1);ll bn*(n1ll)/2ll,d__gcd(a,b);a/d;b/d;if(!a)printf(0\n);else if(ab)printf(1\n);else printf(%lld/%lld\n,a,b);return 0;
}
