双指针维护可交换结合贡献区间价值的正攻法

nkxjlym / 2024-10-13 / 原文

对于一类区间价值 V(l,r) = a[l] opt a[l+1] opt ... opt a[r]

当我们维护双指针同时需要维护内部区间的价值时，如果操作可交换结合并且可消去(存在y，x opt y = 0)，l右移时直接去掉a[l]的价值即可；如果不可消去但可重复贡献(x opt x = x)，可以使用ST表计算区间贡献；如果只满足结合律，我们可以利用线段树额外花费log的时间计算区间贡献。这里给出一个巧妙的做法，只要这个操作可交换结合，那么不需要任何额外数据结构，每次移动指针所需维护开销均摊后即为操作复杂度的做法。

多维护一个x，把当前维护的双指针分成两部分[l,x]和[x+1,r]分别维护价值，[l,x]的部分存储一个 $w[i](l<=i<=x)$，表示[i,x]的价值，

再维护一个数e，表示[x+1,r]的价值。当l右移超过x之后，把x设置为当前的r，重新计算[l,x]的w，e清空。每次查询只需要计算w[l] opt t的值。因为每个w只被算了一次，所以均摊复杂度是O(nk)，其中k是操作复杂度。

下面给出CF2006C的代码，当中使用了这个技巧，避免了ST表维护gcd。(不过用ST表维护gcd也可以证明是一个log的)

const int N=4e5+3;
int a[N];
struct twop{
	int w[N],l,x,r,e;
	void init(){
		l=r=x=1;
		e=0;
	}
	void addr(){
		e=gcd(e,a[r++]);
	}
	void addl(){
		++l;
		if(l<=x)return;
		x=r-1;
		w[r]=e=0;
		for(int i=x;i>=l;i--)w[i]=gcd(a[i],w[i+1]);
	}
	int get(){
		return gcd(w[l],e);
	}
}T;

void solve(){
	int n;
	cin>>n;
	ll ans=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=a[i-1])cnt=1;
		else ++cnt;
		ans+=cnt;
		a[i-1]-=a[i];
	}
	T.init();
	for(int i=2;i<=n;i++){
		T.addr();
		int tmp;
		while(tmp=T.get(),tmp!=0&&(tmp&tmp-1)==0)
			T.addl();
		ans+=T.l-1;
	}
	cout<<ans<<endl;
}