2019.8.3 [HZOI]NOIP模拟测试12 B. 数颜色

2019.8.3 [HZOI]NOIP模拟测试12 B. 数颜色

全场比赛题解：https://pan.baidu.com/s/1eSAMuXk
数据结构学傻的做法：
对每种颜色开动态开点线段树直接维护
操作一区间查询 操作二转化为单点修改
常数有点大，需要稍微卡常。

正解：
对每种颜色开vector存储出现位置（下标），可以发现每种颜色出现位置满足单调性，操作一直接二分找到这段区间，操作二找到两个位置修改。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N=6e7+5;
int n,m,tot,ans,a[N],rt[N],ls[N],rs[N],sum[N];
#define mid ((l+r)>>1)
void In(int &num){
    register char c=getchar();
    for(num=0;!isdigit(c);c=getchar());
    for(;isdigit(c);num=num*10+c-48,c=getchar()); 
}
void add(int &p,int l,int r,int pos,int val){
    if(!p) p=++tot; sum[p]+=val;
    if(l!=r) pos<=mid?add(ls[p],l,mid,pos,val):add(rs[p],mid+1,r,pos,val);
}
void query(int p,int l,int r,int L,int R){
    if(!p) return;
    if(L<=l&&r<=R) return (void) (ans+=sum[p]);
    if(L<=mid&&ls[p]&&sum[ls[p]]>0) query(ls[p],l,mid,L,R);
    if(R>mid&&rs[p]&&sum[rs[p]]>0) query(rs[p],mid+1,r,L,R);
}
int main(){
    In(n);In(m);
    for(register int i=1;i<=n;++i){
        In(a[i]);++a[i];
        add(rt[a[i]],1,n,i,1);
    }
    for(register int i=1,op,l,r,c,pos;i<=m;++i){
        In(op);
        if(op==1) {
            ans=0;
            In(l);In(r);In(c);++c;
            query(rt[c],1,n,l,r);
            printf("%d\n",ans);
        }
        else {
            In(pos);
            add(rt[a[pos]],1,n,pos,-1);
            add(rt[a[pos]],1,n,pos+1,1);
            add(rt[a[pos+1]],1,n,pos+1,-1);
            add(rt[a[pos+1]],1,n,pos,1);
            swap(a[pos],a[pos+1]);
        }
    }
    return 0;
}