c/c++语言开发共享[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("%dn",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; }