二进制分组——强制在线的有力算法

二进制分组——强制在线的有力算法

这个标题似乎有点既视感

这个算法是在2013年的集训队论文集中《浅谈数据结构题的几个非经典解法》里面介绍的。

给个link。

有兴趣的可以自己学习一下。

应用

专门对付强制在线的算法，当修改之间对答案的贡献互相独立（这个和CDQ一样）（或可以快速合并）时，就可以通过套上一个二进制分组的log来做到在线。

介绍

比如现在我有一个数据结构题：

1.添加一个操作:把[l,r]区间中的数加上x。

2.询问如果我执行了[l,r]区间的操作,pos这一个点的值会变为多少。

离线做法就直接大力线段树就可以了，问题不大，相信大家都会。

那如果强制在线呢？

我们一想可以二进制分组（不然我讲它干什么）。

比如当前有22个操作,22=16+4+2

我们对前16个操作建立一个线段树，后面四个建一个，再后面两个建一个。

有二进制进位时就重构就可以了。

实际运用的时候不用真的建好几颗线段树。

重构就判断要不要pushup就可以了。

具体的如果右儿子进位（塞爆）了，自己就也重构就可以了。

例题:UOJ46

/*
@Date    : 2020-01-14 22:21:04
@Author  : Adscn (adscn@qq.com)
@Link    : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IL inline
#define RG register
#define gi geti<int>()
#define gl geti<ll>()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>
IL T geti()
{
	RG T xi=0;
	RG char ch=gc;
	bool f=0;
	while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
	while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
	return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
	if(k<0)k=-k,putchar('-');
	if(k>=10)pi(k/10);
	putchar(k%10+'0');
	if(ch)putchar(ch);
}
const int N=1e5+7;
int n,m;
struct node{
	int l,r,a,b;
	node(){}
	node(int L){l=L;r=a=b=0;}
	node(int L,int R,int A,int B){l=L,r=R,a=A,b=B;}
	bool operator < (const node &b)const{return l<b.l;}
}t[N<<2];
inline void merge(int &a,int &b,int x,int y)
{
	a=1ll*a*x%m,b=(1ll*b*x+y)%m;
}
node operator + (node a,node b){
	merge(a.a,a.b,b.a,b.b);
	return a;
}
#define mid ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
vector<node>s[N<<2];
inline void pushup(int rt)
{
	s[rt].clear();
	int len1=s[ls].size(),len2=s[rs].size(),lst=0;
	for(int i=0,j=0;i<len1&&j<len2;)
	{
		int a=s[ls][i].a,b=s[ls][i].b;
		merge(a,b,s[rs][j].a,s[rs][j].b);
		if(s[ls][i].r<=s[rs][j].r){
			s[rt].emplace_back(lst+1,s[ls][i].r,a,b);
			lst=s[ls][i].r;
			if(s[ls][i].r==s[rs][j].r)++j;
			++i;
		}
		else{
			s[rt].emplace_back(lst+1,s[rs][j].r,a,b);
			lst=s[rs][j].r;
			++j;
		}
	}
}
inline bool modify(int rt,int l,int r,int pos,node a)
{
	if(l==r){
		if(a.l!=1)s[rt].emplace_back(1,a.l-1,1,0);
		s[rt].push_back(a);
		if(a.r!=n)s[rt].emplace_back(a.r+1,n,1,0);
		return 1;
	}
	if(pos<=mid)return modify(ls,l,mid,pos,a),0;
	else{
		if(modify(rs,mid+1,r,pos,a))pushup(rt);
		return 1;
	}
}
inline node query(int rt,int l,int r,int L,int R,int pos)
{
//	cout<<rt<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
//	if(l>r)return (node){0,0,1,0};
	if(L<=l&&r<=R){
//		for(auto i:s[rt])printf("Rt=%d:%d %d %d %d
",rt,i.l,i.r,i.a,i.b);
		auto ret=*--upper_bound(s[rt].begin(),s[rt].end(),node(pos));
//		pi(pos,'
');
//		printf("ret :%d %d %d %d
",ret.l,ret.r,ret.a,ret.b);
		return ret;
	}
	if(R<=mid)return query(ls,l,mid,L,R,pos);
	if(L>mid)return query(rs,mid+1,r,L,R,pos);
	return query(ls,l,mid,L,R,pos)+query(rs,mid+1,r,L,R,pos); 
}
int a[N];
int main(void)
{
	#ifndef ONLINE_JUDGE
//  File("");
	#endif
	int type=gi;
	n=gi,m=gi;
	for(int i=1;i<=n;++i)a[i]=gi;
	int q=gi,ans=0,cnt=0;
	while(q--){
		int opt=gi,l=gi,r=gi;
		if(type&1)l^=ans,r^=ans;
 		if(opt==1){
			int a=gi,b=gi;
			modify(1,1,100000,++cnt,node(l,r,a,b));
		}
		else{
			int pos=gi;
			if(type&1)pos^=ans;
			auto ret=query(1,1,100000,l,r,pos);
//			cout<<ret.a<<" "<<ret.b<<endl;
			pi(ans=(1ll*a[pos]*ret.a+ret.b)%m,'
');
		}
	}
	return 0;
}