洛谷P3939 數顔色【主席樹 or 莫隊】

題目簡述

小 C 把她标号從1到n的n隻兔子排成長長的一排，來給他們喂胡蘿蔔吃。 第 i 隻兔子的顔色是 a_i

小 C 想知道在區間 [l_j,r_j] 裡有多少隻顔色為 c_j的兔子。

有時編号為 x_j 和 x_j+1的兩隻兔子會交換位置

輸入格式

輸入第 1 行兩個正整數 n，m。

輸入第 2 行 n 個正整數，第 i 個數表示第 i 隻兔子的顔色 a_i

輸入接下來 m 行，每行為以下兩種中的一種：

“ 1   l j   r j   c j “1\ l_j\ r_j\ c_j “1 lj​ rj​ cj​ ” ：詢問在區間 [ l j , r j ] [l_j,r_j] [lj​,rj​]裡有多少隻顔色為 c j c_j cj​的兔子

“ 2   x j ” “2\ x_j” “2 xj​”： x j x_j xj​和 x j + 1 x_j+1 xj​+1兩隻兔子交換了位置。

n , m ≤ 3 ∗ 1 0 5 n,m \leq 3*10^5 n,m≤3∗105

輸出格式

輸出到标準輸出中。

對于每個 1 操作，輸出一行一個正整數，表示你對于這個詢問的答案。

題目分析

首先說一下官方正解是vector存每個顔色出現位置，然後每次詢問在對應vector裡二分就行

但本人資料結構學傻了，第一眼帶修改莫隊，然後卡70pts，之後就怒寫主席樹，過了

是以這裡貼主席樹和莫隊寫法

按套路建主席樹

每次交換x和x+1隻用修改第x個線段樹就行了

// 主席樹

const int maxn=400010;
int n,m;
int a[maxn],b[maxn];
int pos[maxn],cnt;
int rt[maxn<<6],ch[maxn<<6][2],sz;
int size[maxn<<6];
int rem[maxn];

int update(int pre,int ll,int rr,int x,int w)
{
	int tt=++sz;
	size[tt]=size[pre]+w;
	ch[tt][0]=ch[pre][0]; ch[tt][1]=ch[pre][1];
	
	int mid=ll+rr>>1;
	if(ll<rr)
	{
		if(x<=mid) ch[tt][0]=update(ch[pre][0],ll,mid,x,w);
		else ch[tt][1]=update(ch[pre][1],mid+1,rr,x,w);
	}
	return tt;
}

int query(int lft,int rht,int ll,int rr,int c)
{
	if(ll==rr) return size[rht]-size[lft];
	int mid=ll+rr>>1;
	if(c<=mid) return query(ch[lft][0],ch[rht][0],ll,mid,c);
	else return query(ch[lft][1],ch[rht][1],mid+1,rr,c);
}

int main()
{
	n=read(); m=read();
	for(int i=1;i<=n;++i)
	a[i]=b[i]=read();
	
	sort(b+1,b+1+n);
	for(int i=1;i<=n;++i)
	if(i==1||b[i]!=b[i-1])
	pos[++cnt]=b[i];
	
	for(int i=1;i<=n;++i)
	{
		rem[a[i]]=1;
		a[i]=lower_bound(pos+1,pos+1+cnt,a[i])-pos;
		
		rt[i]=update(rt[i-1],1,cnt,a[i],1);
	}
	
	
	for(int i=1;i<=m;++i)
	{
		int opt=read();
		if(opt==1)
		{
			int ll=read(),rr=read(),c=read();
			if(!rem[c])
			{
				printf("0\n");
				continue;
			}
			
			c=lower_bound(pos+1,pos+1+cnt,c)-pos;
			printf("%d\n",query(rt[ll-1],rt[rr],1,cnt,c));
		}
		else if(opt==2)
		{
			int loc=read();
			
			rt[loc]=update(rt[loc],1,cnt,a[loc],-1); // 删掉原來的數
			rt[loc]=update(rt[loc],1,cnt,a[loc+1],1); // 加上下一位的數
			
			swap(a[loc],a[loc+1]);
		}
	}
	
	return 0;
}
           

// 帶修改莫隊

const int maxn=300010;
int n,m,sz;
struct Query{ int ll,rr,c,pre,id;}q[maxn];
struct Change{ int pos;}change[maxn];
int cntq,cntc;
int a[maxn],cnt[maxn];
int ans[maxn];

bool cmp(Query a,Query b)
{
	if(a.ll/sz!=b.ll/sz) return a.ll/sz<b.ll/sz;
    if(a.rr/sz!=b.rr/sz) 
    {
    	if((a.ll/sz)&1) return a.rr<b.rr;
    	else return a.rr>b.rr;
	}
    return a.pre<b.pre;
}

void add(int idx){ cnt[a[idx]]++;}
void del(int idx){ cnt[a[idx]]--;}
void modify(int idx, Query q)
{
	if(idx==q.ll-1)
	{
		--cnt[a[idx+1]];
		++cnt[a[idx]];
	}
	else if(idx==q.rr)
	{
		--cnt[a[idx]];
		++cnt[a[idx+1]];
	}
	swap(a[idx],a[idx+1]);
}

int main()
{
	n=read(); m=read();
	for(int i=1;i<=n;++i)
	a[i]=read();
	
	for(int i=1;i<=m;++i)
	{
		int opt=read();
		if(opt==1)
		{
			q[++cntq].ll=read();
			q[cntq].rr=read();
			q[cntq].c=read();
			
			q[cntq].pre=cntc;
			q[cntq].id=cntq;
		}
		else if(opt==2){
			change[++cntc].pos=read();
		}
	}
	
	sz=pow(n,2.0/3);
	sort(q+1,q+1+cntq,cmp);
	
	int L=1,R=0, cur=0;
	for(int i=1;i<=cntq;++i)
	{
		while(R<q[i].rr) add(++R);
		while(R>q[i].rr) del(R--);
		while(L<q[i].ll) del(L++);
		while(L>q[i].ll) add(--L);
		
		while(cur<q[i].pre) modify(change[++cur].pos, q[i]);
		while(cur>q[i].pre) modify(change[cur--].pos, q[i]);
		
		ans[q[i].id]=cnt[q[i].c];
	}
	
	for(int i=1;i<=cntq;++i)
	printf("%d\n",ans[i]);
	
	return 0;
}