题解：CF2077E Another Folding Strip

线性做法看不太懂，这里是一个

\log

的做法(/kel)。

显然一次折叠会使得若干位置的

a_i

减一，考察这个位置集合的性质。

考虑这个位置集合中相邻的两个元素，它们之间至多只能存在一条折痕，同时由于折痕只能存在于两个相邻格子中间，因此这相邻的两个元素的奇偶性一定是不同的。

同时，只要这个位置集合满足相邻的两个元素的奇偶性都不同，就一定是可以被构造出来的（从前往后依次折叠即可）。

于是问题变成了，每次操作选定一个子序列

-1

，满足子序列相邻两项坐标奇偶性不同，用最少的操作次数覆盖完

a

。

这个问题就非常类似于积木大赛之类的套路，维护前面偶数结尾位置和奇数结尾位置可以延过来多少个子序列

c_0,c_1

，然后对一个

a_i

，以

i

为奇数为例（偶数同理）：

$a_i$ 需要从前面的偶数位置延过来，因此若 $c_0<a_i$ ，则需要补上 $a_i-c_0$ 个子序列，同时 $c_0:=0$ ，否则 $c_0$ 减去 $a_i$
$c_1$ 会加上 $a_i$ 。

这样就可以线性地跑出一个序列的答案。

对所有区间来求，考虑从前面扫描到后面，对每个

a_i

求出它对答案的贡献。

具体来说，每个区间起点

l

到当前位置

i

的时候，其

c_{0,l},c_{1,l}

都是确定的，于是

a_i

的操作就可以写为（以

i,l

的奇偶性相同的情况为例）：

会产生 $\max(0,a_i-c_{0,l})$ 个新子序列，并令 $c_{0,l}:=\max(0,c_{0,l}-a_i)$
$c_{1,l}:=c_{1,l}+a_i$

于是多个

l

的操作就可以同时进行，维护四颗权值线段树分别维护所有起点是偶数/奇数的

c_{0/1}

。

那么就要维护以下操作：

所有权值 $+d$
区间求和（权值个数/权值之和）
单点加

所有权值

+d

相当于位移，不好操作，所以维护一个基准点表示

0

的位置，这样就变成了基准点的移动。

最后求出

a_i

的贡献之后，区间右端点可以在

[i,n]

中取，因此还要乘上

n-i+1

再加到答案中。

时间复杂度

O(\sum n\log W)(W=\sum a_i)

。

好像要卡一下空间。

CPP

struct seg_tree{ int rt; ll d; } T[2][2];
inline void pushdown(int now){
	if (tag[now]){
		if (ls[now]) cnt[ls[now]]=sum[ls[now]]=0,tag[ls[now]]=1;
		if (rs[now]) cnt[rs[now]]=sum[rs[now]]=0,tag[rs[now]]=1;
		tag[now]=0;
	}
}
void update(int& now, ll l, ll r, ll x, int y){
	if (!now) now=++tsiz;
	cnt[now]+=y,sum[now]=(sum[now]+1ll*x%mod*y%mod+mod)%mod;
	if (l==r) return;
	ll mid=(l+r)>>1; pushdown(now);
	mid>=x?update(ls[now],l,mid,x,y):update(rs[now],mid+1,r,x,y);
}
pair<int,int> query(int now, ll l, ll r, ll x, ll y){
	if (!now) return make_pair(0,0);
	if (l==x && r==y){
		int d1=cnt[now],d2=sum[now];
		cnt[now]=sum[now]=0,tag[now]=1;
		return {d1,d2};
	}
	ll mid=(l+r)>>1; pushdown(now);
	if (mid>=y){
		auto P=query(ls[now],l,mid,x,y);
		cnt[now]=cnt[ls[now]]+cnt[rs[now]];
		sum[now]=(sum[ls[now]]+sum[rs[now]])%mod;
		return P;
	} else
	if (mid<x){
		auto P=query(rs[now],mid+1,r,x,y);
		cnt[now]=cnt[ls[now]]+cnt[rs[now]];
		sum[now]=(sum[ls[now]]+sum[rs[now]])%mod;
		return P;
	} else {
		auto P1=query(ls[now],l,mid,x,mid),P2=query(rs[now],mid+1,r,mid+1,y);
		cnt[now]=cnt[ls[now]]+cnt[rs[now]];
		sum[now]=(sum[ls[now]]+sum[rs[now]])%mod;
		return {P1.first+P2.first,(P1.second+P2.second)%mod};
	}
}
//求区间中的权值个数和权值之和，在查询完之后直接删除这部分
int main(){
	for (cin>>Tc; Tc; Tc--){
		scanf("%d",&n); int ans=0;
		
		for (int i=1; i<=n; i++){
			scanf("%d",&x);
			update(T[i&1][0].rt,-L,L,T[i&1][0].d,1);
			update(T[i&1][1].rt,-L,L,T[i&1][1].d,1);
			
			int res=0;
			auto P0=query(T[i&1][0].rt,-L,L,T[i&1][0].d,T[i&1][0].d+x);
			int c0=P0.first,s0=P0.second;
			res=(res+1ll*c0*(x+T[i&1][0].d%mod)+mod-s0)%mod;
			T[i&1][1].d-=x; T[i&1][0].d+=x;
			update(T[i&1][0].rt,-L,L,T[i&1][0].d,c0);
			
			auto P1=query(T[(i&1)^1][1].rt,-L,L,T[(i&1)^1][1].d,T[(i&1)^1][1].d+x);
			int c1=P1.first,s1=P1.second;
			res=(res+1ll*c1*(x+T[(i&1)^1][1].d%mod)+mod-s1)%mod;
			T[(i&1)^1][0].d-=x; T[(i&1)^1][1].d+=x;
			update(T[(i&1)^1][1].rt,-L,L,T[(i&1)^1][1].d,c1);
			
			ans=(ans+1ll*(res%mod+mod)*(n-i+1))%mod;
		}
		printf("%d\n",ans);
		
		for (int i=1; i<=tsiz; i++) ls[i]=rs[i]=cnt[i]=sum[i]=tag[i]=0;
		tsiz=T[0][0].d=T[0][0].rt=T[0][1].d=T[0][1].rt=T[1][0].d=T[1][0].rt=T[1][1].d=T[1][1].rt=0;
	}
}

题解：CF2077E Another Folding Strip

文章操作

相关推荐

评论

题解：CF2077E Another Folding Strip