学步园

/*
题意：
刷墙， 以开始 有 n个节点，每个节点有一种颜色 ，m 次询问
m次 输入 a，l，r，z 如果 a=1 将 l到 r 刷为 z 颜色，如果 a=2  询问 l 到 r 有 多少个 和 z 相同的 节点
官方题解是： 分段哈希，自己一开始想写 一下 ，单写着写着 就 觉得很麻烦 ，各中判断条件。。。。。
后来改为 线段树  优化了下 ，就是加了 个 mi mx  判断 查询的颜色 是否在这里面。。。。。
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define MAX 100010
using namespace std;

//线段树模板
struct line
{
    int left, right; //左端点、右端点
    int c;//color
    int mini, most;
}a[4*MAX];
int v[MAX];

//建立
void build(int s, int t, int n)
{
    int mid = (s + t) / 2;
    a[n].left = s;
    a[n].right = t;
    if (s == t)
    {
        a[n].c = v[s];
        a[n].mini = v[s];
        a[n].most = v[s];
        return;
    }
    build(s, mid, 2 * n);
    build(mid + 1, t, 2 * n + 1);
    if(a[2*n].c == a[2*n+1].c)
        a[n].c = a[2*n].c;
    else
        a[n].c = -1;
    a[n].mini = min(a[2*n].mini, a[2*n+1].mini);
    a[n].most = max(a[2*n].most, a[2*n+1].most);
}
void up(int step)
{
    a[step].mini = min(a[2*step].mini, a[2*step+1].mini);
    a[step].most = max(a[2*step].most, a[2*step+1].most);
    return ;
}
void down(int step)
{
    if(a[step].c != -1)
    {
        a[2*step].c = a[2*step+1].c = a[step].c;
        a[step].c = -1;
        a[2*step].mini = a[2*step+1].mini = a[step].mini;//note
        a[2*step].most = a[2*step+1].most = a[step].most;//note
    }
}
//插入
void modify(int s, int t, int step, int col)
{
    if (s == a[step].left && t == a[step].right)
    {
        a[step].c = col;
        a[step].most = col;
        a[step].mini = col;
        return;
    }
    if (a[step].left == a[step].right)
        return;
    down(step);
    int mid = (a[step].left + a[step].right) / 2;
    if (mid >= t)
        modify(s, t, step * 2, col);
    else if (mid < s)
        modify(s, t, step * 2 + 1, col);
    else
    {
        modify(s, mid, step * 2, col);
        modify(mid + 1, t, step * 2 + 1, col);
    }
    if(a[2*step].c == a[2*step+1].c)
    {
        a[step].c = a[2*step].c;
    }
    up(step);
}
int ans;
void query(int s, int t, int step, int col)
{
    if(a[step].c != -1)//区间的颜色一样
    {
        if(a[step].c == col)//等于查询的颜色
        {
            ans += t - s + 1;
        }
        return;
    }
    if(a[step].left == a[step].right)return;//到底层
    if(a[step].mini > col || a[step].most < col) //重要的优化
        return;
    int mid = (a[step].left + a[step].right) / 2;
    if(mid >= t)
        query(s, t, 2 * step, col);
    else if(mid < s)
        query(s, t, 2 * step + 1, col);
    else
    {
        query(s, mid, 2 * step, col);
        query(mid + 1, t, 2 * step + 1, col);
    }
}

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(a, 0, sizeof(a));
        int i;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &v[i]);
        };
        build(0, n - 1, 1);
        int flag, lt, rt, col;
        for(i = 1; i <= m; i++)
        {
            scanf("%d%d%d%d", &flag, <, &rt, &col);
            if(flag == 1)
            {
                modify(lt, rt, 1, col);
            }
            else
            {
                ans = 0;
                query(lt, rt, 1, col);
                printf("%d\n", ans);
            }
        }
    }
    return 0;                                                                                     
}