差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_728_div._1 [2021/07/05 20:12]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_728_div._1 [2021/07/09 20:24] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== Codeforces Round #706 (Div. 1) ======
+====== Codeforces Round #728 (Div. 1) ======
 [[http://codeforces.com/contest/1540|比赛链接]]
@@ 行 88: / 行 88: @@
 </hidden>
+===== C. Converging Array =====
+==== 题意 ====
+一开始有 $a[1\sim n],b[1\sim n-1]$，接下来有无限次操作。
+每次操作随机选择一个 $1\le i\le n-1$， $a_i=\min\left(a_i,\cfrac {a_i+a_{i+1}-b_i}2\right),a_{i+1}=\max\left(a_i,\cfrac {a_i+a_{i+1}+b_i}2\right)$。
+可以证明无限次操作后序列 $a[1\sim n]$ 收敛于固定值。
+每次询问给定 $x$，问有多少序列 $a[1\sim n]$ 满足：
+  - $0\le a_i\le c_i$
+  - 最终收敛后 $a_1\ge x$
+==== 题解 ====
+设最终得到序列为 $f[1\sim n]$。观察发现，每次操作不改变 $\sum a_i$，且最后有 $f_{i+1}-f_i\ge b_i$。
+设 $sa_i=\sum_{j=1}^i a_j,sb_1=0,sb_{i+1}=\sum_{k=1}^j b_k,ssb_i=\sum_{j=1}^i sb_i,sc_i=\sum_{j=1}^i c_j$。
+不难发现最后形式为 $f_1+sb_1,f_1+sb_2,f_1+sb_3 \cdots f_1+sb_k,f_{k+1}\cdots$，其中 $f_t\gt f_1+sb_t(t\gt k)$。
+同时有 $\sum_{i=1}^k f_i+sb_i=\sum_{i=1}^k a_i$，且 $\sum_{i=1}^t f_i+sb_i=\sum_{i=1}^t a_i\ge \sum_{i=1}^t a_i(t\neq k)$。
+于是有 $f_1=\min_{i=1}^n\left(\cfrac {sa_i-ssb_i}i\right)$。枚举询问的 $x$，对每个 $x$，保证 $\cfrac {sa_i-ssb_i}i\ge x$ 即可计算答案个数。
+设 $\text{dp}(i,s)$ 表示 $\sum_{j=1}^i a_i=s$ 的情况，$m=\max c_i$，利用差分可以 $O(n^2m)$ 计算答案。
+最后有 $\min\left(\cfrac {-ssb_i}i\right)\le f_1\le \min\left(\cfrac {sc_i-ssb_i}i\right)$，于是有 $\max(f_1)-\min (f_1)\le m$。
+即有效的 $x$ 只有 $O(m)$ 个，最终时间复杂度 $O\left(n^2m^2\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=105,MAXV=1e4+5,mod=1e9+7,inf=1e9;
+int b[MAXN],c[MAXN],dp[MAXN][MAXV],ans[MAXN],n;
+int solve(int x){
+	mem(dp,0);
+	dp[0][0]=1;
+	_rep(i,1,n){
+		_for(j,1,MAXV)
+		dp[i-1][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;
+		_for(j,max(x*i+b[i],0),MAXV){
+			if(j-c[i]>0)
+			dp[i][j]=(dp[i-1][j]-dp[i-1][j-c[i]-1]+mod)%mod;
+			else
+			dp[i][j]=dp[i-1][j];
+		}
+	}
+	int ans=0;
+	_for(i,0,MAXV)
+	ans=(ans+dp[n][i])%mod;
+	return ans;
+}
+int Div(int a,int b){
+	if(a<0)
+	return (a-b+1)/b;
+	else
+	return a/b;
+}
+int main()
+{
+	n=read_int();
+	_rep(i,1,n)c[i]=read_int();
+	_rep(i,2,n)b[i]=read_int()+b[i-1];
+	_rep(i,2,n)b[i]=b[i]+b[i-1];
+	int lef=inf,rig=inf,s=0;
+	_rep(i,1,n){
+		s+=c[i];
+		lef=min(lef,Div(-b[i],i));
+		rig=min(rig,Div(s-b[i],i));
+	}
+	_rep(i,lef,rig)
+	ans[i-lef]=solve(i);
+	int q=read_int();
+	while(q--){
+		int x=read_int();
+		x=min(max(lef,x),rig+1);
+		enter(ans[x-lef]);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== D. Inverse Inversions =====
+==== 题意 ====
+现有一个 $1\sim n$ 的排列，设 $p_i$ 表示元素 $i$ 在排列中的位置。已知序列 $b$，其中 $b_i=\sum_{j=1}^i[p_j\gt p_i]$。
+接下来两种操作：
+  - 修改某个 $b_x$
+  - 询问某个 $p_x$
+==== 题解 ====
+设 $P(i,r)=\sum_{j=1}^r[p_j\gt p_i]$，$c_i=i-1-b_i$，于是有 $P(i,i)=c_i,P(i,n)=p_i-1$。
+不难发现 $P(i,r+1)=P(i,r)+[c_{r+1}\le P(i,r)]$。
+对修改操作仅维护 $c_i$，时间复杂度 $O(1)$。对询问操作直接暴力转移，时间复杂度 $O(n)$。
+考虑分块，设分块大小为 $B$。对每个块 $[l_i,r_i]$，考虑线段树维护 $P(x,l_i)(l_i\le x\le r_i)$。
+对线段树的每个区间 $[L,R]$，维护 $P(x,R)(L\le x\le R)$，于是 $\text{push_up}$ 操作可以双指针维护，时间复杂度 $O(R-L)$。
+修改某个 $b_x$ 对应线段树的单点修改操作，于是修改操作的总复杂度 $O(B)$。
+对于查询操作，设 $x\in [l_i,r_i]$，可以先 $O(B)$ 暴力计算出 $P(x,r_i)$。
+然后对后续每个块 $k$，利用序列 $P(x,r_k)$ 可以二分计算贡献，时间复杂度 $O(\frac nB\log B)$。
+不难发现取 $B=O(\sqrt{n\log n})$ 时复杂的最小，此时时间复杂度为 $O\left(q\sqrt{n\log n}\right)$，空间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXB=600;
+int b[MAXN];
+struct Tree{
+	int lef[MAXB<<2],rig[MAXB<<2];
+	vector<int> p[MAXB<<2];
+	void push_up(int k){
+		int pos1=0,pos2=0,k1=k<<1,k2=k<<1|1;
+		p[k].clear();
+		_rep(i,lef[k],rig[k]){
+			if(pos1<p[k1].size()&&pos2<p[k2].size()){
+				if(p[k1][pos1]+pos2<p[k2][pos2])
+				p[k].push_back(p[k1][pos1++]+pos2);
+				else
+				p[k].push_back(p[k2][pos2++]);
+			}
+			else if(pos1<p[k1].size())
+			p[k].push_back(p[k1][pos1++]+pos2);
+			else
+			p[k].push_back(p[k2][pos2++]);
+		}
+	}
+	void build(int k,int L,int R){
+		lef[k]=L,rig[k]=R;
+		int M=L+R>>1;
+		if(L==R){
+			p[k].push_back(b[M]);
+			return;
+		}
+		build(k<<1,L,M);
+		build(k<<1|1,M+1,R);
+		push_up(k);
+	}
+	void update(int k,int pos){
+		if(lef[k]==rig[k]){
+			p[k][0]=b[pos];
+			return;
+		}
+		int mid=lef[k]+rig[k]>>1;
+		if(pos<=mid)
+		update(k<<1,pos);
+		else
+		update(k<<1|1,pos);
+		push_up(k);
+	}
+	int query(int v){
+		int lef=1,rig=p[1].size(),ans=0;
+		while(lef<=rig){
+			int mid=lef+rig>>1;
+			if(v+mid>p[1][mid-1]){
+				ans=mid;
+				lef=mid+1;
+			}
+			else
+			rig=mid-1;
+		}
+		return ans;
+	}
+}tree[MAXB];
+int blk_id[MAXN],lef[MAXB],rig[MAXB];
+int main()
+{
+	int n=read_int(),blk_sz=sqrt(n*log(n))/2+1,m=n/blk_sz;
+	if(n%blk_sz)m++;
+	_rep(i,1,n)b[i]=i-1-read_int();
+	_for(i,0,m){
+		lef[i]=i*blk_sz+1;
+		rig[i]=min((i+1)*blk_sz,n);
+		_rep(j,lef[i],rig[i])
+		blk_id[j]=i;
+		tree[i].build(1,lef[i],rig[i]);
+	}
+	int q=read_int();
+	while(q--){
+		int opt=read_int(),x=read_int();
+		if(opt==1){
+			b[x]=x-1-read_int();
+			tree[blk_id[x]].update(1,x);
+		}
+		else{
+			int ans=b[x];
+			_rep(i,x+1,rig[blk_id[x]]){
+				if(ans>=b[i])
+				ans++;
+			}
+			_for(i,blk_id[x]+1,m)
+			ans+=tree[i].query(ans);
+			enter(ans+1);
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+另外附上一份时间复杂度 $O\left(q\sqrt nlog n\right)$，空间复杂度 $O(n)$ 的代码，树状数组上二分写的。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+#define lowbit(x) ((x)&(-x))
+int c[MAXN];
+void add(int pos,int v){
+	while(pos<MAXN){
+		c[pos]+=v;
+		pos+=lowbit(pos);
+	}
+}
+int query(int b){
+	int pos=0,curb=0;
+	for(int i=16;i>=0;i--){
+		if(pos+(1<<i)<MAXN&&c[pos+(1<<i)]+(1<<i)+curb<b){
+			curb+=c[pos+(1<<i)]+(1<<i);
+			pos+=(1<<i);
+		}
+	}
+	return pos+1;
+}
+int b[MAXN],lef[MAXN],rig[MAXN],blk_id[MAXN];
+vector<int> a[MAXN];
+void build(int k){
+	a[k].clear();
+	_rep(i,lef[k],rig[k]){
+		int t=query(b[i]+1)-1;
+		a[k].push_back(t);
+		add(t+1,1);
+	}
+	sort(a[k].begin(),a[k].end());
+	_for(i,0,a[k].size())
+	add(a[k][i]+1,-1);
+}
+int main()
+{
+	int n=read_int(),blk_sz=sqrt(n/2)+1,m=n/blk_sz;
+	if(n%blk_sz)m++;
+	_rep(i,1,n)b[i]=read_int();
+	_for(i,0,m){
+		lef[i]=i*blk_sz+1;
+		rig[i]=min((i+1)*blk_sz,n);
+		_rep(j,lef[i],rig[i])
+		blk_id[j]=i;
+		build(i);
+	}
+	int q=read_int();
+	while(q--){
+		int opt=read_int(),x=read_int();
+		if(opt==1){
+			b[x]=read_int();
+			build(blk_id[x]);
+		}
+		else{
+			int ans=b[x];
+			_rep(i,x+1,rig[blk_id[x]]){
+				if(ans>=b[i])
+				ans++;
+			}
+			_for(i,blk_id[x]+1,m)
+			ans+=upper_bound(a[i].begin(),a[i].end(),ans)-a[i].begin();
+			enter(n-ans);
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具