CF455D Serega and Fun 题解

link T4 desu. vj

给定长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），$q$ 次操作：

1. 1 l r：将区间 $[l, r]$ 循环右移一位。即 $a_r$ 移到 $a_l$，其余元素依次右移
2. 2 l r k：询问区间 $[l, r]$ 中 $k$ 的出现次数

---

一眼分块题。

考虑对每个块维护一个队列。由于是右移，因此队头在右边，队尾在左边。

然后再维护 shownc[maxsqn][maxn] 表示块内某个颜色的出现次数。

由于 stl 的队列是不支持下标访问的，那么我们搞一个“拆包”和“封包”的东西。

给前后不完整的块拆包，然后手动修改这两个块的值，中间的块只需要 pop 和 push 各一遍即可。同步把 shownc 也给修改。

同理，查询时也是先拆包，然后手动统计，中间的块只需要访问 shownc 即可。

最后封包即可。

inline void del(int p,int val){
	shownc[p][val]--;
}
inline void add(int p,int val){
	shownc[p][val]++;
}

inline void unpag(int bk,vector<int> &s){
	s.clear();
	while(que[bk].size()) s.push_back(que[bk].front()),que[bk].pop();
}
inline void addpag(vector<int> &s,int bk){
	for(int i=0;i<s.size();++i) que[bk].push(s[i]);
}
//拆出来的包顺序与队列一致


vector<int> _this;
void inblock_update(int l,int r,int in){
	unpag(in,_this);
	int lpos=bk[in].len-inbkpos[l],rpos=bk[in].len-inbkpos[r];
	int x=_this[rpos];
	for(int i=rpos;i<lpos;++i){
		_this[i]=_this[i+1];
	}
	_this[lpos]=x;
	addpag(_this,in);
}


vector<int> front,back;
void update(int l,int r){
	int lin=inbk[l],rin=inbk[r];
	if(lin==rin){
		inblock_update(l,r,lin);
		return;
	}
	unpag(lin,front);
	unpag(rin,back);
	
	int lpos=bk[lin].len-inbkpos[l],rpos=bk[rin].len-inbkpos[r];

	int x=front[0];
	for(int i=0;i<lpos;++i){
		front[i]=front[i+1];
	}
	front[lpos]=back[rpos];
	del(lin,x);
	add(lin,back[rpos]);

	for(int i=lin+1;i<=rin-1;++i){
		que[i].push(x);
		add(i,x);
		x=que[i].front();
		del(i,x);
		que[i].pop();
	}

	del(rin,back[rpos]);
	for(int i=rpos;i<back.size()-1;++i){
		back[i]=back[i+1];
	}
	back[back.size()-1]=x;
	add(rin,x);
	
	addpag(front,lin);
	addpag(back,rin);
}




ll inblock_query(int l,int r,int in,ll k){
	ll res=0;
	unpag(in,_this);
	int lpos=bk[in].len-inbkpos[l],rpos=bk[in].len-inbkpos[r];
	for(int i=rpos;i<=lpos;++i){
		if(_this[i]==k) ++res;
	}
	addpag(_this,in);
	return res;
}


ll query(int l,int r,ll k){
	int lin=inbk[l],rin=inbk[r];
	if(lin==rin){
		return inblock_query(l,r,lin,k);
	}
	ll res=0;
	unpag(lin,front);
	unpag(rin,back);

	int lpos=bk[lin].len-inbkpos[l],rpos=bk[rin].len-inbkpos[r];

	for(int i=0;i<=lpos;++i) if(front[i]==k) ++res;
	for(int i=rpos;i<back.size();++i) if(back[i]==k) ++res;

	for(int i=lin+1;i<=rin-1;++i){
		res+=shownc[i][k];
	}
	addpag(front,lin);
	addpag(back,rin);
	return res;
}

不要看我的实现，我觉得我的实现已经能懂了我就不管了。

sub