差别

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

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_728_div._1 [2021/07/06 10:29]
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|比赛链接]]
@@ 行 117: / 行 117: @@
 设 $\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$。
+最后有 $\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)$。
@@ 行 168: / 行 168: @@
 		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;

CVBB ACM Team

用户工具

站点工具

差别

页面工具