题解 P3939 数颜色

zero4338 · 2021-06-20 18:50:13 · 个人记录

Solution

对于兔子们按照颜色为第一关键字 , 位置为第二关键字排序 , 查询个数时直接二分 , 相同颜色的修改不用管 , 不同颜色的修改不会改变统一颜色内的大小顺序 , 直接修改不会影响有序性 .
时间复杂度 O(nlogn)

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int read()
{
    int ret=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c<='9'&&c>='0')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return ret;
}
const int maxn=3e5+5;
int n,m;
int a[maxn];
struct rabbit
{
    int col,p;
    const bool operator <(const rabbit x)const{if(col!=x.col)return col<x.col;return p<x.p;}
}r[maxn];
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        r[i].col=a[i];r[i].p=i;
    }
    sort(r+1,r+n+1);
    while(m--)
    {
        int opt=read();
        if(opt==1)
        {
            int nl,nr,c;nl=read();nr=read();c=read();
            nr=upper_bound(r+1,r+n+1,rabbit{c,nr})-r-1;
            nl=lower_bound(r+1,r+n+1,rabbit{c,nl})-r;
            printf("%d\n",nr-nl+1);
        }
        else 
        {
            int x=read();
            if(a[x]==a[x+1])continue;
            int now=lower_bound(r+1,r+n+1,rabbit{a[x],x})-r;r[now].p=x+1;
            now=lower_bound(r+1,r+n+1,rabbit{a[x+1],x+1})-r;r[now].p=x;
            swap(a[x],a[x+1]);
        }
    }
    return 0;
}