题解 | #牛牛玩 generals#

大家好，我不会珂朵莉树。

但是我喜欢暴力。

所以我用分块草过了这题。

具体地，维护当前每个块中有多少 $xx$ 的兵力，整块覆盖直接维护整块兵力然后打标记即可，散块需要重构。合并过程中每个块没有 tag 的直接合并过来，否则忽略。

这样做复杂度是 $O(qB\times \alpha (n)+\frac{qm}{B}\times \alpha (n))O(qB\backslash times\; \backslash alpha(n)+\backslash frac\{qm\}\{B\}\backslash times\; \backslash alpha(n))$ 的。

注意到整块的 tag 可以直接在合并过程中修改，所以复杂度降为 $O(qB\times \alpha (n)+\frac{qm}{B})O(qB\backslash times\; \backslash alpha(n)+\backslash frac\{qm\}\{B\})$ ，因此可以通过精细调块长来通过此题。

上式算出来 $BB$ 取 $100\sim 200100\backslash sim200$ 最优，实际通过调整发现 $BB$ 取 $500500$ 才可以通过本题。

（写了半个多小时调了一个小时，感谢出题人大恩大德放我过了）

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
//#define int ll
#define N 100005
#define B 505
#define bh Bh
using namespace std;
inline char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
//#define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int Tot[(N/B)+5][N];
int tot,n,m,q;
int Totsum[N];
int tag[N];
int col[N];
int fa[N];
int a[N];
int tagval[N];
int L[N],R[N];
int From[N];
int Bh[N];
int hme[N];
int all[N];
vector<int>Ghme[N];
inline int gf(int x)
{
	if (x==fa[x]) return x;
	return fa[x]=gf(fa[x]);
}
inline void rebuild(int x)
{
	if (tag[x])
	{
		for (int j=L[x];j<=R[x];j++)
		{
			Tot[x][gf(col[j])]=0;
			col[j]=tag[x];
			a[j]=tagval[x];
		}
		for (int j=L[x];j<=R[x];j++)
		{
			Tot[x][gf(col[j])]-=a[j]*2;
		}
		tag[x]=0;
		tagval[x]=0;
	}
}
inline void merge(int x,int y)
{
	for (int i=1;i<=tot;i++)
	{
		if (tag[i]==y)
		{
			tag[i]=x;
		}
		else
		{
			Tot[i][x]+=Tot[i][y];
			Tot[i][y]=0;
		}
	}
	fa[y]=x;
}
void What_will_Diana_eat_today()
{
	n=read(),m=read(),q=read();
	for (int i=1;i<=n;i++)
		fa[i]=i;
	for (int i=1;i<=n;i++) 
	{
		int x=read();
		hme[i]=x;
		Bh[x]=i;
	}
	for (int i=1;i<=m;i++) 
		From[i]=(i-1)/B+1;
	tot=From[m];
	for (int i=1;i<=tot;i++) L[i]=m+1,R[i]=0;
	for (int i=1;i<=m;i++) L[From[i]]=min(L[From[i]],i),R[From[i]]=max(R[From[i]],i);
	for (int i=1;i<=n;i++)
		Ghme[From[i]].push_back(hme[i]);
	while (q--)
	{
		int opt=read();
		if (opt==1)
		{
			int nowcol=read(),x=read(),y=read(),p=read();
			int sum=0;
			if (From[x]==From[y])
			{
				rebuild(From[x]);
				for (int j=x;j<=y;j++)
				{
					if (gf(col[j])==nowcol) sum-=a[j];
					else sum+=a[j];
					Tot[From[j]][gf(col[j])]+=a[j]*2;
					Totsum[From[j]]-=a[j];
					col[j]=nowcol;
					a[j]=p;
					Tot[From[j]][gf(col[j])]-=a[j]*2;
					Totsum[From[j]]+=a[j];
				}
				sum+=(y-x+1)*p;
				writeln(sum);
				for (int j=x;j<=y;j++)
					if (Bh[j])
					{
						if (Bh[j]!=nowcol) 
						{
							merge(nowcol,Bh[j]);
							Bh[j]=0;
						}
					}
			} else
			{
				int X=x,Y=y;
				x=x,y=R[From[x]];
				rebuild(From[x]);
				for (int j=x;j<=y;j++)
				{
					if (gf(col[j])==nowcol) sum-=a[j];
					else sum+=a[j];
					Tot[From[j]][gf(col[j])]+=a[j]*2;
					Totsum[From[j]]-=a[j];
					col[j]=nowcol;
					a[j]=p;
					Tot[From[j]][gf(col[j])]-=a[j]*2;
					Totsum[From[j]]+=a[j];
				}
				sum+=(y-x+1)*p;
				x=X,y=Y;
				
				x=L[From[y]];
				rebuild(From[x]);
				for (int j=x;j<=y;j++)
				{
					if (gf(col[j])==nowcol) sum-=a[j];
					else sum+=a[j];
					Tot[From[j]][gf(col[j])]+=a[j]*2;
					Totsum[From[j]]-=a[j];
					col[j]=nowcol;
					a[j]=p;
					Tot[From[j]][gf(col[j])]-=a[j]*2;
					Totsum[From[j]]+=a[j];
				}
				sum+=(y-x+1)*p;
				x=X,y=Y;
				
				for (int j=From[x]+1;j<From[y];j++)
				{
					if (!tag[j]) 
						sum+=(R[j]-L[j]+1)*p-Tot[j][nowcol]*2+Totsum[j];
					else
						sum+=(R[j]-L[j]+1)*p+Totsum[j];
					tag[j]=nowcol;
					Totsum[j]=p*(R[j]-L[j]+1);
					tagval[j]=p;
				}
				writeln(sum);
				x=X,y=Y;
				x=x,y=R[From[x]];
				for (int j=x;j<=y;j++)
					if (Bh[j])
					{
						if (Bh[j]!=nowcol) 
						{
							merge(nowcol,Bh[j]);
							Bh[j]=0;
						}
					}
				x=X,y=Y;
				
				x=L[From[y]],y=y;
				for (int j=x;j<=y;j++)
					if (Bh[j])
					{
						if (Bh[j]!=nowcol) 
						{
							merge(nowcol,Bh[j]);
							Bh[j]=0;
						}
					}
				x=X,y=Y;
				
				for (int j=From[x]+1;j<From[y];j++)
				{
					bool bl=0;
					for (auto u:Ghme[j])
					{
						if (u!=gf(u)) continue;
						if (Bh[u]!=nowcol) merge(nowcol,bh[u]),bh[u]=0;
						else bl=1;
					}
					vector<int>().swap(Ghme[j]);
					if (bl) Ghme[j].push_back(hme[nowcol]);
				}
			}
		} else
		{
			int x=read();
			int sum=0;
			for (int j=1;j<=tot;j++)
			{
				if (tag[j]&&tag[j]==x)
				{
					sum+=Totsum[j];
				} else
				if (!tag[j])
				{
					sum-=Tot[j][x]/2;
				}
			}
			writeln(sum);
		}
	}
	for (int i=1;i<=n;i++)
		if (gf(i)==i) writeln(i);
}
signed main()
{
	int T=1;
	while (T--)
	{
	 	  What_will_Diana_eat_today();
	}
}