「Luogu P3939」数颜色

发表于 |
字数统计: 450 | 阅读时长 ≈ 2

给定一个序列，支持交换两个元素和询问区间$(l,r)$内等于这个值的位置的数量。

链接

Luogu P3939

题解

肯定有人学数据结构学傻了吧，我们机房有写cdq的，有写主席树的，跑的都很快亲测这份代码不吸氧比上面两份代码吸氧还快……
评测结果
用vector记录每一种颜色的兔子出现在从左到右的哪几个位置，对于每个询问，二分查找出当前右端点$r$的位置和左端点$l-1$的位置，两个值相减即得答案，但是要注意边界处理。
对于交换，找到两个兔子的位置，直接进行交换即可，注意要把所有的信息都交换……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=3e5+51;
vector<ll>rabbit[MAXN];
ll cnt,ccnt,op,l,r,x,lx,rx,maxn;
vector<ll>::iterator bg,ed;
ll color[MAXN],ind[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
int main()
{
    cnt=read(),ccnt=read();
    for(register int i=1;i<=cnt;i++)
    {
        color[i]=read();
        rabbit[color[i]].push_back(i);
        ind[i]=rabbit[color[i]].size()-1;
    }
    for(register int i=1;i<=ccnt;i++)
    {
        op=read();
        if(op==1)
        {
            l=read()-1,r=read(),x=read();
            bg=rabbit[x].begin();
            ed=rabbit[x].end();
            if(bg==ed)
            {
                puts("0");
                continue;
            }
            lx=lower_bound(bg,ed,l)-bg,rx=lower_bound(bg,ed,r)-bg;
            if(rabbit[x][lx]==l)
            {
                lx++;
            }
            if(rabbit[x][rx]==r)
            {
                rx++;
            }
            printf("%d\n",rx-lx);
        }
        else
        {
            x=read();
            if(color[x]!=color[x+1])
            {
                rabbit[color[x]][ind[x]]=x+1;
                rabbit[color[x+1]][ind[x+1]]=x;
                swap(color[x],color[x+1]);
                swap(ind[x],ind[x+1]);
            }
        }
    }
}