[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;
}