分块求调,YTQ说这个题通过就当我npy
查看原帖
分块求调,YTQ说这个题通过就当我npy
817044
cjwdyzxfblzs楼主2023/6/8 19:44

我测样例可以过,交上去却是一片紫色。真的不理解了欸。为了方便各位大佬阅读,我加上了注释。请各位大佬帮蒟蒻康康是哪里的问题呀,为什么全是RE,应该不是我数组开小了的问题。

蒟蒻悬赏若干关注(●'◡'●)

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N = 133335;
const int M = 10000;
int n, m;
int col[N];
/// st 一个块的start
/// ed 一个块的end
/// 一个节点的 belong
int st[M], ed[M], bel[M];
unordered_map<int, int> mp[M]; // 储存每一个块的某一个颜色的个数
bitset<N> vis[M]; // 存储每一个块有哪几种颜色
signed main()
{
    n = read(), m = read();
    int sq = sqrt(n);
    // 确定块长
    for (int i = 1; i <= sq; i++)
    {
        st[i] = n / sq * (i - 1) + 1;
        ed[i] = n / sq * i;
    }
    ed[sq] = n;
    // 确定点的归属
    for (int i = 1; i <= sq; i++)
        for (int j = st[i]; j <= ed[i]; j++)
            bel[j] = i;
    for (int i = 1; i <= sq; i++)
        for (int j = st[i]; j <= ed[i]; j++)
        {
            col[j] = read();
            mp[i][col[j]]++;
            vis[i][col[j]] = true;
        }
    for (int i = 1; i <= m; i++)
    {
        char str = getchar();
        int L, R, P, color;
        if (str == 'Q')
        {
            L = read(), R = read();
            int bell = bel[L], belr = bel[R];
            int res = 0;
            // 如果在同一个块中,暴力
            if (bell == belr)
            {
                unordered_map<int, int> mpp;
                for (int i = L; i <= R; i++)
                {
                    if (!mpp[col[i]])
                        res++,
                        mpp[col[i]]++;
                }
                cout << res << endl;
                continue;
            }
            else
            {
                bitset<N> bi;
                // 确定整块的颜色个数,使用或
                for (int i = bell + 1; i < belr; i++)
                    bi |= vis[i];
                // 确定两端的散块的颜色
                for (int i = L; i <= ed[bell]; i++)
                    bi[col[i]] = true;
                for (int i = st[belr]; i <= R; i++)
                    bi[col[i]] = true;
                // 看有多少个 1
                cout << bi.count() << endl;
                continue;
            }
        }
        else
        {
            P = read(), color = read();
            int belp = bel[P]; // p 属于 belp 这个块
            if (!(--mp[belp][col[P]])) // 如果这个块去掉一个颜色就没了这个颜色
                vis[belp][col[P]] = false;
            col[P] = color; // 更改节点颜色
            vis[belp][color] = true;
            mp[belp][color]++;
            continue;
        }
    }
    return 0;
}

2023/6/8 19:44
加载中...