MnZn妹子，刚学CDQ，RE/WA/TLE求调

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

int N, M, A[100010], pre[100010], ans[100010];

namespace BinaryIndexedTree
{
    class BinaryIndexedTree
    {
        public:

        int n, tr[100010];

        int lowbit(int x)
        {
            return x & (-x);
        }

        void add(int x, int v)
        {
            for (int i = x; i <= n; i += lowbit(i))
                tr[i] += v;
        }
        
        int query(int x)
        {
            int res = 0;

            for (int i = x; i; i -= lowbit(i))
                res += tr[i];

            return res;
        }
    } BIT;
}

namespace CDQDivide
{
    int nodeCnt;

    struct Node
    {
        int type, time, x, y, flag;

        Node() {}

        Node(int type, int time, int x, int y, int flag) : type(type), time(time), x(x), y(y), flag(flag) {}
    } node[3000010];

    void CDQ(int l, int r)
    {
        if (l == r)
            return;

        int mid = (l + r) >> 1;
        CDQ(l, mid);
        std::sort(node + l, node + r + 1, [](Node a, Node b) -> bool
        {
            if (a.time == b.time)
                return a.type < b.type;

            return a.time < b.time;
        });
        std::sort(node + l, node + mid + 1, [](Node a, Node b) -> bool
        {
            if (a.x == b.x)
                return a.y < b.y;

            return a.x < b.x;
        });
        std::sort(node + mid + 1, node + r + 1, [](Node a, Node b) -> bool
        {
            if (a.x == b.x)
                return a.y < b.y;

            return a.x < b.x;
        });
        
        for (int i = l, j = mid + 1; j <= r; ++ j)
        {
            if (node[j].type == 1)
                continue;
            
            while (i <= mid && node[i].x <= node[j].x)
            {
                if (node[i].type == 1)
                    BinaryIndexedTree::BIT.add(node[i].y + 1, node[i].flag);

                ++ i;
            }

            ans[node[j].time] += node[j].flag * BinaryIndexedTree::BIT.query(node[j].y + 1);
        }

        for (int i = l, j = mid + 1; j <= r; ++ j)
        {
            if (node[j].type == 1)
                continue;

            while (i <= mid && node[i].x <= node[j].x)
            {
                if (node[i].type == 1)
                    BinaryIndexedTree::BIT.add(node[i].y + 1, -node[i].flag);

                ++ i;
            }
        }

        std::sort(node + l, node + r + 1, [](Node a, Node b) -> bool
        {
            return a.time < b.time;
        });
        CDQ(mid + 1, r);
    }
}

namespace ChthollyTree
{
    class ChthollyTree
    {
        public:

        struct Node
        {
            int l, r;
            mutable int v;

            Node(int l, int r, int v) : l(l), r(r), v(v) {}

            bool operator < (const Node &other) const
            {
                return l < other.l;
            }
        } ;

        std::set <Node> ODT;

        auto split(int x)
        {
            auto it = std::prev(ODT.upper_bound(Node(x, 0, 0)));

            if (it->l == x)
                return it;

            int l = it->l, r = it->r, v = it->v;
            ODT.erase(it);
            ODT.insert(Node(l, x - 1, v));

            return ODT.insert(Node(x, r, v)).first;
        }
    } ODT;

    class ChthollyTreeColor : ChthollyTree
    {
        public:

        struct Node
        {
            int l, r;

            Node(int l, int r) : l(l), r(r) {}

            bool operator < (const Node &other) const
            {
                return l < other.l;
            }
        } ;

        std::set <Node> ODT;
    } ODTColor[200010];

    // 初始化 ODT，初始化 pre
    void init()
    {
        for (int i = 1; i <= N; ++ i)
        {
            ODT.ODT.insert(ChthollyTree::Node(i, i, A[i]));
            ODTColor[A[i]].ODT.insert(ChthollyTreeColor::Node(i, i));
        }

        for (int i = 1; i <= N; ++ i)
        {
            auto it = ODTColor[A[i]].ODT.lower_bound(ChthollyTreeColor::Node(i, i));

            if (it == ODTColor[A[i]].ODT.begin())
                pre[i] = 0;
            else
                pre[i] = std::prev(it)->l;
        }
    }

    // 区间修改，维护 pre
    void modifyAssign(int time, int l, int r, int x)
    {
        auto itR = ODT.split(r + 1), itL = ODT.split(l);
        std::set <int> needUpdate; // 存下所有需要修改的位置

        for (auto it = itL; it != itR; ++ it)
        {
            needUpdate.insert(it->l);
            using ChthollyTreeColorNode = ChthollyTreeColor::Node;
            auto next = std::next(ODTColor[it->v].ODT.lower_bound(ChthollyTreeColorNode(it->l, it->r)));

            if (next != ODTColor[it->v].ODT.end())
                needUpdate.insert(next->l);

            ODTColor[it->v].ODT.erase(std::prev(next));
        }

        ODT.ODT.erase(itL, itR);
        using ChthollyTreeNode = ChthollyTree::ChthollyTree::Node;
        ODT.ODT.insert(ChthollyTreeNode(l, r, x));
        using ChthollyTreeColorNode = ChthollyTreeColor::Node;
        auto newPos = ODTColor[x].ODT.insert(ChthollyTreeColorNode(l, r)).first;
        
        if (std::next(newPos) != ODTColor[x].ODT.end())
            needUpdate.insert(std::next(newPos)->l);

        for (int pos : needUpdate)
        {
            int v = ODT.ODT.lower_bound(ChthollyTreeNode(pos, 0, 0))->v;
            int &nodeCnt = CDQDivide::nodeCnt;
            CDQDivide::Node *node = CDQDivide::node;
            node[ ++ nodeCnt] = CDQDivide::Node(1, time, pos, pre[pos], -1);
            auto it = std::prev(ODTColor[v].ODT.upper_bound(ChthollyTreeColorNode(pos, 0)));

            if (pos == it->l)
            {
                if (it == ODTColor[v].ODT.begin())
                {
                    pre[pos] = 0;
                    node[ ++ nodeCnt] = CDQDivide::Node(1, time, pos, 0, 1);
                }
                else
                {
                    pre[pos] = std::prev(it)->r;
                    node[ ++ nodeCnt] = CDQDivide::Node(1, time, pos, pre[pos], 1);
                }
            }
            else
            {
                pre[pos] = pos - 1;
                node[ ++ nodeCnt] = CDQDivide::Node(1, time, pos, pos - 1, 1);
            }
        }
    }
}

namespace Prework
{
    struct Operation
    {
        int type, time, l, r, x;
    } operation[100010];

    // 读入、离散化、树状数组定大小
    void dataPreprocess()
    {
        scanf("%d%d", &N, &M);
        BinaryIndexedTree::BIT.n = 100000;
        std::vector <int> all;

        for (int i = 1; i <= N; ++ i)
        {
            scanf("%d", &A[i]);
            all.push_back(A[i]);
        }

        for (int i = 1; i <= M; ++ i)
        {
            int op;
            scanf("%d", &op);

            if (op == 1)
            {
                int l, r, x;
                scanf("%d%d%d", &l, &r, &x);
                all.push_back(x);
                operation[i] = {1, i, l, r, x};
            }
            else
            {
                int l, r;
                scanf("%d%d", &l, &r);
                operation[i] = {2, i, l, r};
            }
        }

        std::sort(all.begin(), all.end());
        all.erase(std::unique(all.begin(), all.end()), all.end());

        for (int i = 1; i <= N; ++ i)
            A[i] = std::lower_bound(all.begin(), all.end(), A[i]) - all.begin() + 1;

        for (int i = 1; i <= M; ++ i)
            if (operation[i].type == 1)
                operation[i].x = std::lower_bound(all.begin(), all.end(), operation[i].x) - all.begin() + 1;
    }

    void prework()
    {
        dataPreprocess();
        ChthollyTree::init();
        int &nodeCnt = CDQDivide::nodeCnt;
        CDQDivide::Node *node = CDQDivide::node;

        // 初始就有的点，应该算进 CDQ 的修改中
        for (int i = 1; i <= N; ++ i)
            node[ ++ nodeCnt] = CDQDivide::Node(1, 0, i, pre[i], 1);

        // 考虑对于每个操作
        for (int i = 1; i <= M; ++ i)
            if (operation[i].type == 1)
            {
                int l = operation[i].l, r = operation[i].r, x = operation[i].x;
                ChthollyTree::modifyAssign(i, l, r, x);
            }
            else
            {
                int l = operation[i].l, r = operation[i].r;
                node[ ++ nodeCnt] = CDQDivide::Node(2, i, r, l - 1, 1);
                node[ ++ nodeCnt] = CDQDivide::Node(2, i, l - 1, l - 1, -1);
            }
    }
}

int main()
{
    freopen("IceAge.in", "r", stdin);
    freopen("IceAge.out", "w", stdout);

    Prework::prework();
    CDQDivide::CDQ(1, CDQDivide::nodeCnt);

    for (int i = 1; i <= M; ++ i)
        if (Prework::operation[i].type == 2)
            printf("%d\n", ans[i]);

    return 0;
}