[luogu3939][数颜色]

题目链接

思路

对于每一种颜色都建立一个动态开点线段树。然后每次查询的时候就去这个颜色的线段树上查询就行了。修改之后不要忘记交换颜色。

这个题目数据有点强。抄了个比较快的读入优化才卡过去。

代码

/*
* @Author: wxyww
* @Date:   2018-12-13 08:59:51
* @Last Modified time: 2018-12-13 09:56:16
*/
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 600000;
#include <sys/mman.h>
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#define Finline __inline__ __attribute__ ((always_inline))
struct io{
    char *s;
    io():s((char*)mmap(0, 1<<26, PROT_READ, MAP_PRIVATE, fileno(stdin), 0)) {}
    inline operator int()
    {
        register int x=0;
        for(;*s<48;++s);
        for(;*s>47;)x=x*10+*s++-48;
        return x;
    }
}io;
int TR[N * 20],a[N],ls[N * 20],rs[N * 20];
int tot,root[N];
inline void update(int &cur,int l,int r,int pos,int c) {
    if(!cur) cur = ++tot;
    if(l == r) {
        TR[cur] += c;
        return;
    }
    TR[cur] += c;
    int mid = (l + r) >> 1;
    if(pos <= mid) update(ls[cur],l,mid,pos,c);
    else update(rs[cur],mid + 1,r,pos,c);
}
inline int query(int cur,int l,int r,int L,int R) {
    if(L <= l && R >= r) return TR[cur];
    int mid = (l + r) >> 1,ans = 0;
    if(L <= mid) ans += query(ls[cur],l,mid,L,R);
    if(R > mid) ans += query(rs[cur],mid + 1,r,L,R);
    return ans;
}
int main() {
    int n = io,m = io;
    for(int i = 1;i <= n;++i) {
        a[i] = io;
        update(root[a[i]],1,n,i,1);
    }
    while(m--) {
        int opt = io;
        if(opt == 1) {
            int l = io,r = io,c = io;
            printf("%d\\n",query(root[c],1,n,l,r));
        }
        else {
            int x = io;
            update(root[a[x]],1,n,x,-1);
            update(root[a[x]],1,n,x + 1,1);
            update(root[a[x + 1]],1,n,x + 1,-1);
            update(root[a[x + 1]],1,n,x,1);
            swap(a[x],a[x + 1]);
        }
    }
    return 0;
}