自动搬运

查看原文

来自洛谷，原作者为

	konjacq 对不起 给大家丢脸了

搬运于2025-08-24 22:26:56，当前版本为作者最后更新于2020-12-20 09:30:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作为出题人过来发个题解.

首先很抱歉比赛时被暴力艹过去了,现在数据已经加强(时限也对应开大),欢迎大家用更奇怪的暴力来艹过.

分块.

对于整块的修改,直接用珂朵莉树维护每个值的出现次数;对于散块的修改,遍历从上次作为散块以来的所有修改,记录每个出现过的数最后变成了哪个数即可.注意散块修改细节实现的时候不能用并查集:比如依次进行$1\gets2$,$3\gets1$两个操作,并查集会记录为$1~\text{and}~3\gets2$.所以只能保存每一个数最后被修改成了什么,而不能记录中间过程.清空也请注意复杂度保持在$\sqrt n$以内.

每一块最多从第一次修改到第$m$次,参考珂朵莉树的证明可以发现每次修改时每块内的值的种类数期望是$\log n$的,所以散块总复杂度的期望大致是$m\sqrt n\log n$的.

对于询问,散块暴力整块珂朵莉树.

总复杂度大概是$n\sqrt n\log n$乘巨大的常数.不是很会分析,如果哪位大佬能仔细证一下的话就多谢了.

#include <algorithm>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;

typedef long long ll;

/* ---- read() & rlong() - begin ---- */
#define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048576,stdin),p0==p1)?EOF:*p0++)
char buf[1048576],*p0,*p1;
inline int read() {
	int r=0; char c=gc(); while (c<48||c>57) c=gc();
	while (c>47&&c<58) {r=(r<<3)+(r<<1)+(c^48); c=gc();} return r;
}
#undef gc
/* ---- read() & rlong() -- end ----- */

const int q=188; int p[35505],tim,val[35505],fat[35505],cnt[35505];
int upl[35505],upr[35505],upu[35505],upv[35505],upw[35505];
struct txb {
	int w; mutable int t;
	inline txb (int _w):w(_w),t(0) {}
	inline txb (int _w,int _t):w(_w),t(_t) {}
	bool operator <(const txb &op) const {return w<op.w;}
};
typedef set<txb>::iterator sit;
struct bxt {
	int l,r; vector<int> g; set<txb> s;

	inline void clear() {
		vector<int> e; int f;
		for (int i=l;i<=r;++i) {
			if (!fat[val[i]]) {
				f=val[i];
				for (auto j:g) if (f>=upu[j]&&f<=upv[j])
					f=upw[j]; fat[val[i]]=f;
			}
			e.push_back(val[i]); val[i]=fat[val[i]];
		}
		for (auto i:e) fat[i]=0; g.clear();
	}

	inline void flatten(int u,int v,int w) {
		int t=0; g.push_back(tim);
		sit spl=s.lower_bound(txb(u)),spr=s.upper_bound(txb(v));
		if (spl==spr) return;
		for (sit i=spl;i!=spr;++i) t+=i->t;
		s.erase(spl,spr); spl=s.lower_bound(txb(w));
		if (spl->w==w) spl->t+=t; else s.insert(txb(w,t));
	}

	inline void update(int a,int b,int u,int v,int w) {
		clear(); s.clear();
		for (int i=l;i<=r;++i) {
			if (i>=a&&i<=b&&val[i]>=u&&val[i]<=v) val[i]=w;
			++cnt[val[i]];
		}
		for (int i=l;i<=r;++i) if (cnt[val[i]]) {
			s.insert(txb(val[i],cnt[val[i]])); cnt[val[i]]=0;
		}
	}
} b[405];

inline int mjly(int u,int v) {return u<v?u:u-v;}

inline int ksm(int u,int v,int w) {
	int r=1; while (v) {
		if (v&1) r=(ll)u*r%w;
		u=(ll)u*u%w; v>>=1;
	}
	return r;
}

inline void update(int l,int r,int u,int v,int w) {
	if (p[l]==p[r]) b[p[l]].update(l,r,u,v,w);
	else {
		b[p[l]].update(l,r,u,v,w); b[p[r]].update(l,r,u,v,w);
		for (int i=p[l]+1;i<p[r];++i) b[i].flatten(u,v,w);
	}
}

inline int powmk(int l,int r,int t,int k) {
	int w=0;
	if (p[l]==p[r]) {
		b[p[l]].clear();
		for (int i=l;i<=r;++i) w=mjly(w+ksm(val[i],t,k),k);
		return w;
	}
	b[p[l]].clear(); b[p[r]].clear();
	for (int i=l;p[i]==p[l];++i) w=mjly(w+ksm(val[i],t,k),k);
	for (int i=r;p[i]==p[r];--i) w=mjly(w+ksm(val[i],t,k),k);
	for (int i=p[l]+1;i<p[r];++i)
		for (auto j:b[i].s) w=(w+(ll)j.t*ksm(j.w,t,k))%k;
	return w;
}

int main() {
	int n,m,l,r,t,k,a=0; n=read(); m=read(); p[0]=p[n+1]=-1;
	for (int i=1;i<=n;i+=q) {
		for (int j=0;j<q&&i+j<=n;++j) {
			p[i+j]=i/q; ++cnt[val[i+j]=read()];
		}
		b[p[i]].l=i; b[p[i]].r=min(i+q-1,n);
		for (int j=b[p[i]].l;j<=b[p[i]].r;++j) if (cnt[val[j]]) {
			b[p[i]].s.insert(txb(val[j],cnt[val[j]])); cnt[val[j]]=0;
		}
	}
	for (;tim<m;++tim) {
		if (read()) {
			l=read(); r=read(); t=read(); k=read();
			a^=powmk(l,r,t,k);
		}
		else {
			upl[tim]=read(); upr[tim]=read();
			upu[tim]=read(); upv[tim]=read(); upw[tim]=read();
			update(upl[tim],upr[tim],upu[tim],upv[tim],upw[tim]);
		}
	}
	printf("%d",a);
	return 0;
}