自动搬运

查看原文

来自洛谷，原作者为

	_AyachiNene AFOed||私の0721を見てください！

搬运于2025-08-24 22:03:49，当前版本为作者最后更新于2024-11-03 14:35:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

模拟赛题，不用根号分治纯分块做法。

思路：

首先有一种显然的根号分治算法，不优化是 $n\sqrt {n\log n}$ 结合数据范围想到写根号算法。考虑分块，首先按所属的环分类，发现对于修改操作的维护是简单的，对于一个块内发现最后一个数会移到下一个块内，其它数对于一个块的和是无影响的，可以不考虑。于是就有一个思路，每一个块内开一个队列，维护队头就行。发现空间复杂度带根号，如果出题人要卡空间就做不了，发现分类后每一块的最后一个数是可以直接求出的，每次踢队就相当于把最后一个数变成上一个数。再考虑查询操作，考虑散块部分怎么做，对于一种颜色算出需要几个，从块内最后一个向前找就行。经过精细实现空间线性，时间 $O(n\sqrt n)$。

Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO
{
	char buff[1<<21],*p1=buff,*p2=buff;
	char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
	template<typename T>void read(T &x){char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}x*=fl;}
	template<typename T>void read_s(T &x){char ch=getch();while(ch<'a'||ch>'z')ch=getch();while(ch>='a'&&ch<='z'){x+=ch;ch=getch();}}
	template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
	char obuf[1<<21],*p3=obuf;
	void putch(char ch) {if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
	char ch[100];
	template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)ch[++top]=x%10+48,x/=10;while(top)putch(ch[top]),top--;}
	template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);write(args...);}
	void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
	void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
int n,m,q;
int c[150005];
ll a[150005];
int siz,bcnt,belong[150005],bl[400],br[400];
ll sum[400];
int vis[150005];
struct node
{
	int id,p;
};
vector<node>v[150005],tag[150005];
vector<int>p[150005];
int tc[150005],tc1[150005];
inline ll calc(int x,int y)
{
	ll res=0;int b=belong[x];
	for(int i=x;i<=y;i++) ++tc[c[i]];
	for(int i=y+1;i<=br[b];i++) ++tc1[c[i]];
	for(int i=0;i<v[b].size();i++) 
	{
		int nc=v[b][i].id;
		int now=tag[nc][v[b][i].p].p;
		while(tc1[nc])
		{
			--now;if(now==-1) now=p[nc].size()-1;
			--tc1[nc];
		}
		while(tc[nc])
		{
			res+=a[p[nc][now]];
			--now;if(now==-1) now=p[nc].size()-1;
			--tc[nc];
		}
	}
	return res;
}
signed main()
{
	freopen("ring.in","r",stdin);
	freopen("ring.out","w",stdout);
	read(n,m,q);
	siz=sqrt(n);
	bcnt=ceil(1.0*n/siz);
	for(int i=1;i<=bcnt;i++)
	{
		bl[i]=(i-1)*siz+1,br[i]=min(n,i*siz);
		for(int j=bl[i];j<=br[i];j++) belong[j]=i;
	}
	for(int i=1;i<=n;i++) read(c[i]),p[c[i]].push_back(i);
	for(int i=1;i<=n;i++) read(a[i]),sum[belong[i]]+=a[i];
	for(int i=1;i<=m;i++) p[i].push_back(n+1);
	for(int i=1;i<=bcnt;i++)
	{
		for(int j=bl[i];j<=br[i];j++)
			if(!vis[c[j]]) v[i].push_back((node){c[j],0}),vis[c[j]]=1;
		for(int j=0;j<v[i].size();j++) 
		{
			int x=v[i][j].id;
			int pos=upper_bound(p[x].begin(),p[x].end(),br[i])-p[x].begin()-1;
			tag[x].push_back((node){i,pos}),vis[x]=0;
			v[i][j].p=tag[x].size()-1;
		}
	}
	for(int i=1;i<=m;i++) p[i].pop_back();
	while(q--)
	{
		int op,x,y;
		read(op,x);
		if(op==1)
		{
			read(y);
			ll ans=0;
			if(belong[x]==belong[y])
			{
				write(calc(x,y)),putch('\n');
				continue;
			}
			for(int i=belong[x]+1;i<=belong[y]-1;i++) ans+=sum[i];
			ans+=calc(x,br[belong[x]])+calc(bl[belong[y]],y);
			write(ans),putch('\n');
		}
		else
		{
			if(tag[x].size()==0) continue;
			node tmp=tag[x].back();
			for(int i=tag[x].size()-1;i;i--)
			{
				sum[tag[x][i].id]+=a[p[x][tag[x][i-1].p]]-a[p[x][tag[x][i].p]];
				--tag[x][i].p;if(tag[x][i].p==-1) tag[x][i].p=p[x].size()-1;
			}
			sum[tag[x][0].id]+=a[p[x][tmp.p]]-a[p[x][tag[x][0].p]];
			--tag[x][0].p;if(tag[x][0].p==-1) tag[x][0].p=p[x].size()-1;
		}
	}
	flush();
	return 0;
}