题目链接：https://loj.ac/problem/6284
题目大意：

区间修改没有什么难度，这题难在区间查询比较奇怪，因为权值种类比较多，似乎没有什么好的维护方法。

模拟一些数据可以发现，询问后一整段都会被修改，几次询问后数列可能只剩下几段不同的区间了。

我们思考这样一个暴力，还是分块，维护每个分块是否只有一种权值，区间操作的时候，对于同权值的一个块就O(1)统计答案，否则暴力统计答案，并修改标记，不完整的块也暴力。

这样看似最差情况每次都会耗费O(n)的时间，但其实可以这样分析：

假设初始序列都是同一个值，那么查询是O(√n)，如果这时进行一个区间操作，它最多破坏首尾2个块的标记，所以只能使后面的询问至多多2个块的暴力时间，所以均摊每次操作复杂度还是O(√n)。

换句话说，要想让一个操作耗费O(n)的时间，要先花费√n个操作对数列进行修改。

初始序列不同值，经过类似分析后，就可以放心的暴力啦。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//由块号寻找第一个块元素的下标
#define LL(x) ((x-1)*Len+1)
const int mod=10007;
LL read()
{
    LL 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-'0';ch=getchar();}
    return x*f;
}

int a[100005], b[100005], flag[1005];
int Len, n;

void reset(int x)//标记下推
{
    if(flag[x]==-1)
    {
        return;
    }
    for(int i=LL(x);i<=min(LL(x+1)-1, n);i++)
    {
        a[i]=flag[x];
    }
    flag[x]=-1;
}

int query(int L, int R, int c)
{
    int bL=b[L], bR=b[R];
    int ans=0;
    if(bL==bR)
    {
        reset(bL);
        for(int i=L;i<=R;i++)
        {
            if(a[i]==c)
            {
                ans++;
            }
            a[i]=c;
        }
    }
    else
    {
        reset(bL);//标记下推
        for(int i=L;i<LL(bL+1);i++)//暴力边块
        {
            if(a[i]==c)
            {
                ans++;
            }
            a[i]=c;
        }

        for(int i=bL+1; i<bR; i++)
        {
            if(flag[i]!=-1)
            {
                if(flag[i]==c)//如果是一整块(全部相同)
                {
                    ans+=Len;
                }
            }
            else
            {
                for(int k=LL(i); k<LL(i+1); k++)//如果不是整块(不全部相同)
                {
                    if(a[k]==c)
                    {
                        ans++;
                    }
                    a[k]=c;
                }
            }
            flag[i]=c;
        }

        reset(bR);//标记下推
        for(int i=LL(bR);i<=R;i++)//暴力边块
        {
            if(a[i]==c)
            {
                ans++;
            }
            a[i]=c;
        }
    }

    return ans;
}

void build(int n)
{
    Len=n/sqrt(n);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=(i-1)/Len+1;
        flag[b[i]]=-1;
    }
}

int main()
{
    n=read();
    build(n);

    for(int i=1;i<=n;i++)
    {
        int L=read(), R=read(), c=read();

        printf("%d\n",query(L, R, c));
    }

    return 0;
}