2019.8.3 [HZOI]NOIP模拟测试12 B. 数颜色

2019.8.3 [HZOI]NOIP模拟测试12 B. 数颜色

全场比赛题解：https://pan.baidu.com/s/1eSAMuXk

数据结构学傻的做法：

对每种颜色开动态开点线段树直接维护

操作一区间查询 操作二转化为单点修改

常数有点大，需要稍微卡常。

正解：

对每种颜色开vector存储出现位置（下标），可以发现每种颜色出现位置满足单调性，操作一直接二分找到这段区间，操作二找到两个位置修改。

Code：

#include <bits/stdc++.h>

using namespace std;

const int N=6e7+5;

int n,m,tot,ans,a[N],rt[N],ls[N],rs[N],sum[N];

#define mid ((l+r)>>1)

void In(int &num){

	register char c=getchar();

	for(num=0;!isdigit(c);c=getchar());

	for(;isdigit(c);num=num*10+c-48,c=getchar());

}

void add(int &p,int l,int r,int pos,int val){

	if(!p) p=++tot; sum[p]+=val;

	if(l!=r) pos<=mid?add(ls[p],l,mid,pos,val):add(rs[p],mid+1,r,pos,val);

}

void query(int p,int l,int r,int L,int R){

	if(!p) return;

	if(L<=l&&r<=R) return (void) (ans+=sum[p]);

	if(L<=mid&&ls[p]&&sum[ls[p]]>0) query(ls[p],l,mid,L,R);

	if(R>mid&&rs[p]&&sum[rs[p]]>0) query(rs[p],mid+1,r,L,R);

}

int main(){

	In(n);In(m);

	for(register int i=1;i<=n;++i){

		In(a[i]);++a[i];

		add(rt[a[i]],1,n,i,1);

	}

	for(register int i=1,op,l,r,c,pos;i<=m;++i){

		In(op);

		if(op==1) {

			ans=0;

			In(l);In(r);In(c);++c;

			query(rt[c],1,n,l,r);

			printf("%d\n",ans);

		}

		else {

			In(pos);

			add(rt[a[pos]],1,n,pos,-1);

			add(rt[a[pos]],1,n,pos+1,1);

			add(rt[a[pos+1]],1,n,pos+1,-1);

			add(rt[a[pos+1]],1,n,pos,1);

			swap(a[pos],a[pos+1]);

		}

	}

	return 0;

}

2019.8.3 [HZOI]NOIP模拟测试12 B. 数颜色的相关教程结束。