P1903

Myth丶恋晨 2022-01-27 02:23 158阅读 0赞

## 题目：[https://www.luogu.org/problemnew/show/P1903][https_www.luogu.org_problemnew_show_P1903] ##

## 分析：主席可以做，也可以用动态（带修改）莫队，模板题。 ##

## 参考博客：[https://www.cnblogs.com/zwfymqz/p/7154145.html][https_www.cnblogs.com_zwfymqz_p_7154145.html] ##

## [https://blog.csdn.net/wu\_tongtong/article/details/77924765][https_blog.csdn.net_wu_tongtong_article_details_77924765] ##

## 注意：对于n和m同级的题目，块的大小为![n^\{\\frac\{2\}\{3\}\}][n_frac_2_3]时复杂度为![O\\left ( n^\{\\frac\{5\}\{3\}\} \\right )][O_left _ n_frac_5_3_ _right]，可以证明，此处略去。如果修改次数少，所以块的大小为![\\sqrt\{n\}][sqrt_n]更快。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N=1000010;
    int n,m;
    int c[N];
    struct node1{
        int l,r,x,id;
    };
    node1 q[N];
    struct node2{
        int x,y;
    };
    node2 ch[N];
    int totq=0,totch=0,unit,ans[N],tot=0,sum[N];
    
    int cmp(const node1 &a,const node1 &b)
    {
        if (a.l/unit!=b.l/unit) return a.l/unit<b.l/unit;
        else if (a.r/unit!=b.r/unit) return a.r/unit<b.r/unit;
        else return a.x<b.x;
    }
    
    void update(int wz,int z)
    {
        if (z==-1) {
            sum[c[wz]]--;
            if (!sum[c[wz]]) tot--;
        }
        else
        {
            sum[c[wz]]++;
            if (sum[c[wz]]==1) tot++;
        }
    }
    
    void change(int bh,int z,int l,int r)
    {
        if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,-1);   //删除从前的影响
        swap(c[ch[bh].x],ch[bh].y);
        if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,1);   //添加影响
    }
    
    void solve()
    {
        int l=1,r=0,now=0;
        for (int i=1;i<=m;i++)
        {
            while (r<q[i].r) update(r+1,1),r++;
            while (r>q[i].r) update(r,-1),r--;
            while (l>q[i].l) update(l-1,1),l--;
            while (l<q[i].l) update(l,-1),l++;
            while (now<q[i].x) change(now+1,1,l,r),now++;
            while (now>q[i].x) change(now,-1,l,r),now--;
            ans[q[i].id]=tot;
        }
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) scanf("%d",&c[i]);
        for (int i=1;i<=m;i++)
        {
            char s[2];
            int x,y;
            scanf("%s%d%d",&s,&x,&y);
            if (s[0]=='Q')
            {
                totq++;
                q[totq].l=x; q[totq].r=y;
                q[totq].x=totch;
                q[totq].id=totq;
            }
            else
            {
                totch++;
                ch[totch].x=x;
                ch[totch].y=y;
            }
        }
        unit=(int)pow(n,0.666666);
        sort(q+1,q+1+totq,cmp);
        solve();
        for (int i=1;i<=totq;i++) printf("%d\n",ans[i]);
        return 0;
    }

[https_www.luogu.org_problemnew_show_P1903]: https://www.luogu.org/problemnew/show/P1903
[https_www.cnblogs.com_zwfymqz_p_7154145.html]: https://www.cnblogs.com/zwfymqz/p/7154145.html
[https_blog.csdn.net_wu_tongtong_article_details_77924765]: https://blog.csdn.net/wu_tongtong/article/details/77924765
[n_frac_2_3]: https://private.codecogs.com/gif.latex?n%5E%7B%5Cfrac%7B2%7D%7B3%7D%7D
[O_left _ n_frac_5_3_ _right]: https://private.codecogs.com/gif.latex?O%5Cleft%20%28%20n%5E%7B%5Cfrac%7B5%7D%7B3%7D%7D%20%5Cright%20%29
[sqrt_n]: https://private.codecogs.com/gif.latex?%5Csqrt%7Bn%7D