BZOJ 2120[国家集训队]数颜色

BZOJ 2120[国家集训队]数颜色

Description
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：

1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。

2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

Output
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

Sample Input6 5 1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

Sample Output
4
4
3
4

带修改的莫队。。同样是将询问通过排序来减少转移距离

但由于有修改，又要按询问排序，所以记一下每个询问之前有多少修改

如果当前比询问的修改多了就撤销，如果少了就继续修改

在排序时应该在区间转移尽量小的情况下，让重复修改次数尽量少

洛谷上的数据强度很大，需要一些排序技巧，比如说奇数左偶数右。。这个我还不知道原理

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define ll long long
int c[6000000],n,m; 
int block;
    int l=0,r=-1;
struct anss{
    int l,r,pos,bl,cn;
    bool operator < (const anss m) const{
        if(bl!=m.bl) return bl<m.bl;
        if(r/block!=m.r/(block)){
        if(bl&1)  
            return r/block<m.r/block;
                return r/block>m.r/block;
        }
        return cn<m.cn;
    }
}a[60000];
inline ll gcd(ll a,ll b){
    //if(a<b) std::swap(a,b);
    return b==0?a:gcd(b,a%b);
}
ll fm,fz,cnt[6000000],a1[60000],a2[60000];
inline int add(int x){
    cnt[x]++;
    if(cnt[x]==1) fz++;
}
inline int del(int x){
    cnt[x]--;
    if(cnt[x]==0) fz--;
}
int ch1[60000];
int ch2[60000];
inline int change(int x){
    std::swap(c[ch1[x]],ch2[x]);
    if(l<=ch1[x]&&ch1[x]<=r){//精髓
        cnt[c[ch1[x]]]++;
        cnt[ch2[x]]--;
        if(cnt[c[ch1[x]]]==1) fz++;
        if(cnt[ch2[x]]==0) fz--;
    }
}
int cn=0,tot=0;
int main () {
    scanf("%d %d",&n,&m);
    block=pow(n,2.0/3);//块大小开根号2/3n
    for(int i=1;i<=n;++i) scanf("%d",&c[i]);
    for(int i=1;i<=m;++i){
        char x;
        scanf(" %c",&x);
        if(x=='Q') {
            ++tot;
            scanf("%d %d",&a[tot].l,&a[tot].r);
            if(a[tot].l>a[tot].r)std::swap(a[tot].l,a[tot].r);
            a[tot].pos=tot;a[tot].bl=(a[tot].l-1)/(block)+1; 
            a[tot].cn=cn;
        }
        if(x=='R'){
            int xx,y;
            scanf("%d %d",&xx,&y);
            ch1[++cn]=xx,ch2[cn]=y;
        }
    }
    cn=0;
    std::sort(a+1,a+1+tot);
    for(int i=1;i<=tot;++i){
        while(cn>a[i].cn){//修改次数
            change(cn);
            cn--;           
        }
        while(cn<a[i].cn){
            cn++;
            change(cn);
        }
        while(l<a[i].l){
            del(c[l]);
            l++;
        }
        while(l>a[i].l){
            l--;
            add(c[l]);
        }
        while(r<a[i].r){
            r++;
            add(c[r]);
        }
        while(a[i].r<r){
            del(c[r]);
            r--;
        }
        a1[a[i].pos]=fz;
    }
    for(int i=1;i<=tot;++i){
        printf("%lld\n",a1[i]);
    }
    return 0;
}