首页 > 其他分享 >CF1817D Half-sum

CF1817D Half-sum

时间:2023-05-10 22:56:18浏览次数:54  
标签:ch int sum mid long 正负 Half CF1817D

前言

前几天 @adamant 在 CF 上发表文章介绍了 Anton Trygub 发明的维护大数的算法 The Trygub Numbers

简要地讲,这个算法支持维护一个 \(n\) 位 \(b\) 进制数:

  • 给定 \(i,v\),将数加上 \(vb^i\)。
  • 给定 \(i\),查询数的第 \(i\) 位的值。
  • 查询数的正负。

其主要思想是将平常每位只能存 \([0,b)\) 的限制扩宽成能够存 \((-b,b)\) 内的任意整数。

这样,数的正负仍可以通过删除前导零后第一个数的正负表示;数的第 \(i\) 位的值只需要 lower_bound 后如果第 \(i\) 位有值那么看看其下一个(更低)非零位是正是负决定是否 \(-1\);修改只需正常进位(进位的增量可以为负数),可以证明均摊线性

对于时间限制较为宽松的题目,可以考虑使用 map 维护。
对于时间限制较紧并且不需要查询数的第 \(i\) 位的值的题目,还是用数组维护比较好。具体方法依题而定,以下题解中给出了一种参考实现。

题解

首先不难想到题目等价于求所有 \(i\in [1,n-1]\) 的下列式子的最大值:

\[(2^{n-i-1}a_{i+1}+\sum_{j>i+1}2^{n-j+1}a_j)-(2^{-(i-1)}a_i+\sum_{j<i}2^{-j}a_j) \]

暴力算是 \(O(n^2)\) 的,long double 精度不够,所以只能够用一个高位二进制数来做,需要支持比较大小。

题解给出了一种巧妙的分治做法来优化时间复杂度。

考虑到比较 \(i,j(i<j)\) 的对应式子值的大小实际上是两个高位二进制数作差,而 \(<i-1,>j+1\) 的部分都消掉了,所以实际上只与 \([i-1,j+1]\) 的值有关。

这种“局部性”提示了分治。具体来说,我们每次将 \([l,r]\) 分为 \([l,mid]\) 和 \([mid+1,r]\),分别递归地求出其局部的最大值取到时分界点 \(i\) 的位置——\(L\) 与 \(R\)。这时只需要把 \([L-1,R+1]\) 对应上式的项的值作个差,判断得到的数的正负,来决定返回 \(L\) 还是 \(R\) 作为 \([l,r]\) 的局部最优解。

不用 map 怎么实现查找最高位呢?由于每次预备作差时都会清空这个 Trygub Number,所以我们可以在作差的过程中记录下所有被修改的位,最后把这些位分别取出来,找到现在非零的位中最高的位即可。

时间复杂度 \(O(n\log n)\)(均摊)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
namespace IO {
const int buflen=1<<21;
char ch,buf[buflen],*p1=buf,*p2=buf;
int x,f;
inline char gc(){
	return p1==p2&&(p2=buf+fread(p1=buf,1,buflen,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	x=0,f=1;ch=gc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=gc();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return f?x:-x;
}
}
using IO::read;
const int N=1e6+5,mod=1e9+7,I2=(mod+1)/2;
int n,a[N];
ll res[N];
struct anton {
	int bin[N+122],*mp=bin+60,bin2[N+122],*bk=bin2+60,vis[N+122],tot;
	inline void add(int x,int y){
		mp[x]+=y;if(!bk[x])vis[++tot]=x,bk[x]=1;
		int t;
		do {
			if(mp[x]<0)t=(-mp[x])>>1,t=-t;
			else t=mp[x]>>1;
			mp[x]-=t<<1;
			mp[x-1]+=t;
			if(!bk[x-1])vis[++tot]=x-1,bk[x-1]=1;
			x--;
		}while(t);
	}
	inline int sig(){
		int mn=1e9;
		for(int i=1;i<=tot;i++){
			if(mp[vis[i]])mn=min(mn,vis[i]);
		}
		return mn==1e9?0:mp[mn]>0?1:-1;
	}
	inline void clr(){
		for(int i=1;i<=tot;i++)mp[vis[i]]=bk[vis[i]]=0;tot=0;
	}
}haha;
int solve(int l,int r){//returns the best position k
	if(l==r)return l;
	int mid=l+r>>1;
	int L=solve(l,mid);
	int R=solve(mid+1,r);
	haha.clr();
	for(int i=L-1;i<=R+1;i++)haha.add(i<=R?i-(i==R):n-i+1-(i==R+1),i<=R?-a[i]:a[i]),haha.add(i<=L?i-(i==L):n-i+1-(i==L+1),i<=L?a[i]:-a[i]);
	return haha.sig()>=0?R:L;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		n=read();
		for(int i=1;i<=n;i++)a[i]=read();
		sort(a+1,a+n+1);
		int pos=solve(1,n-1);
		for(int i=0;i<=n;i++)res[i]=0;
		for(int i=1;i<pos;i++)res[i]-=a[i];
		res[pos-1]-=a[pos];
		for(int i=pos+2;i<=n;i++)res[n-i+1]+=a[i];
		res[n-pos-1]+=a[pos+1];
		int ans=0;
		for(int i=0,I=1;i<=n;i++,I=(ll)I*I2%mod)ans=(ans+(ll)I*(res[i]+mod))%mod;
		cout<<ans<<'\n';
	}
}

标签:ch,int,sum,mid,long,正负,Half,CF1817D
From: https://www.cnblogs.com/impyl/p/17389590.html

相关文章

  • 「USACO2016JAN」Subsequences Summing to Sevens
    [USACO16JAN]SubsequencesSummingtoSevensS题目描述FarmerJohn's\(N\)cowsarestandinginarow,astheyhaveatendencytodofromtimetotime.EachcowislabeledwithadistinctintegerIDnumbersoFJcantellthemapart.FJwouldliketota......
  • 2021 Summer Petrozavodsk Camp, Day 3 IQ test (XXII Open Cup, Grand Prix of IMO)
    AND先看最小值是不是所有的子集,如果不是就无解,否则把剩下的中间塞一个最小值就好了。submissionMath移项,平方差变成\(a_j=(k-a_i)(k+a_i)\),爆枚\(k-a_i\)和\(k+a_i\)就是\(O(A\lnA)\)的。submissionFancyFormulas首先我们发现操作不改变\((a+b)\bmodp\),因此如果......
  • (hdu step 3.2.1)Max Sum(简单dp:求最大子序列和、起点、终点)
    题目:MaxSumTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):1390AcceptedSubmission(s):542 ProblemDescriptionGivenasequencea[1],a[2],a[3]......a[n],yourjobistocalculatethemaxsu......
  • POJ2739 Sum of Consecutive Prime Numbers&&Acwing4938 连续质数之和
    方法:单调队列为什么是单调队列?因为这里让我们求连续的质数和,我们可以利用欧拉筛来维护质数,再利用单调队列来维护连续的质数。代码(POJ不支持C++11差评):#include<cstdlib>#include<cstring>#include<cstdio>#include<cctype>namespaceFastIo{ #definegcgetchar() #d......
  • PAT Advanced 1007. Maximum Subsequence Sum
    PATAdvanced1007.MaximumSubsequenceSum1.ProblemDescription:Givenasequenceof\(K\)integers{\(N_1,N_2,...,N_K\)}.Acontinuoussubsequenceisdefinedtobe{\(N_i,N_{i+1},...,N_j\)}where\(1≤i≤j≤K\).TheMaximumSubsequencei......
  • Prometheus之sum_over_time函数
    一、sum_over_timesum_over_time是Prometheus中用于计算指定时间段内时间序列数据的和的函数。它可以对单个时间序列或多个时间序列进行操作,并返回指定时间范围内时间序列值的总和。sum_over_time函数的语法如下:sum_over_time(rangevector-expression)其中,range指定......
  • 第十一篇——通达信指标公式编写常用函数(七)——SUMBARS以及MACD底背离(从零起步编写通
    内容提要:本文主要介绍通达信指标公式常用函数SUMBARS以及函数的应用,并且综合运用函数来编写MACD底背离。 一、SUMBARS函数简介SUMBARS这个函数名由SUM和BARS两部分组成,SUM在前一篇文章《第十篇——通达信指标公式编写常用函数(六)——SUM、IF(从零起步编写通达信指标公式系......
  • 第十篇——通达信指标公式编写常用函数(六)——SUM、IF(从零起步编写通达信指标公式系列)
    内容提要:本文主要介绍了编写通达信指标公式常用函数SUM、IF,并结合自带OBV指标熟悉函数的使用。 在《第五篇——通达信指标公式编写常用函数(一)——REF、MA、EMA、CROSS(从零起步编写通达信指标公式系列)》这篇文章中讲到均线相关的函数MA,这里简单复习一下。 MA(C,N):收盘价......
  • summarizeabundance.py
    报错信息为:(base)[wz@localhosttemp]$python./summarizeAbundance.py-igene.count-moutput-c'9,16,21'-s',+,+*'-nraw-oeggnog/10t/wz/temp/./summarizeAbundance.py:176:FutureWarning:Thedefaultvalueofnumeric_onlyinDataFrameGr......
  • 「解题报告」ARC103D Distance Sums
    给Kaguya看了一眼,Kaguya用了一分钟切了。我看了一个小时。这就是神吗。考虑一个点往叶子走答案的贡献,显然距离和会变化\(-siz_u+(n-siz_u)=n-2siz_u\)。如果我们以重心为根,那么所有的\(n-2siz_u>0\),那么这实际上是一个小根堆。那么我们考虑从大往小枚举叶子,然......