数列分块入门题集 LOJ 6277 ~ LOJ 6285

超、凢脫俗 2023-06-13 12:28 29阅读 0赞

这几天把LOJ的分块专题刷了个大概，总结一下。

## ##

### LOJ 6277 数列分块入门一 ###

***给出一个长为 n的数列，以及 n个操作，操作涉及区间加法，单点查值。***

思路：这个还是比较容易的，我们只需要快内暴力修改，再记录一个标记就可以了。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e5 + 10;
    ll a[maxn], ad[maxn]; //sum[i]第i块的和，ad[i]第i块的增量
    ll L[maxn], R[maxn], pos[maxn]; //每段左右端点和每个位置属于哪一段
    int n, m, k; //k个块
    
    void add(int l, int r, ll d) //区间[l, r]加上d
    {
        int p = pos[l], q = pos[r];
        if(p == q) //同块
        {
            for(int i = l; i <= r; ++i) a[i] += d;
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i) ad[i] += d;
            for(int i = l; i <= R[p]; ++i) a[i] += d;
            for(int i = L[q]; i <= r; ++i) a[i] += d;
        }
    }
    ll ask(int r)
    {
        int q = pos[r];
        return a[r] + ad[q];
    }
    
    int main()
    {
        scanf("%d", &n);
        m = n;
        for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        k = sqrt(n); //分成k块
        for(int i = 1; i <= k; ++i)
        {
            L[i] = (i - 1) * k + 1;
            R[i] = i * k;
        }
        if(R[k] < n) //最后有一小块
        {
            ++k;
            L[k] = R[k - 1] + 1;
            R[k] = n;
        }
        for(int i = 1; i <= k; ++i)
        {
            for(int j = L[i]; j <= R[i]; ++j)
            {
                pos[j] = i;
            }
        }
        while(m--)
        {
            int l, r, op;
            ll d;
            scanf("%d%d%d%lld", &op, &l, &r, &d);
            if(op == 0)
            {
                add(l, r, d);
            }
            else if(op == 1)
                printf("%lld\n", ask(r));
        }
        return 0;
    }

### LOJ 6278 数列分块入门2 ###

***给出一个长为 n的数列，以及 n个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。***

思路：我们对每个块进行排序，当修改操作时只需要修改两边的块然后再排序，中间的只需要记录标记就行了。查询的时候二分一下就可以了

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 5e5 + 10;
    ll L[maxn], R[maxn], pos[maxn], ad[maxn], a[maxn];
    vector<ll> v[1010];
    int n, m, k; //k个块
    
    int read()
    {
        int x = 0, w = 1;
        char ch = 0;
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') w = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * w;
    }
    void rset(int x)
    {
        v[x].clear();
        for(int i = L[x]; i <= R[x]; ++i) v[x].push_back(a[i]);
        sort(v[x].begin(), v[x].end());
    }
    void add(int l, int r, ll d) //区间[l, r]加上d
    {
        int p = pos[l], q = pos[r];
        if(p == q) //同块
        {
            for(int i = l; i <= r; ++i) a[i] += d;
            rset(p);
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i) ad[i] += d;
            for(int i = l; i <= R[p]; ++i) a[i] += d;
            for(int i = L[q]; i <= r; ++i) a[i] += d;
            rset(p), rset(q);
        }
    }
    ll ask(int l, int r, ll d)
    {
        int p = pos[l], q = pos[r];
        ll ret = 0;
        if(p == q)
        {
            for(int i = l; i <= r; ++i)
                if(a[i] + ad[p] < d)
                    ++ret;
        }
        else
        {
            for(int i = l; i <= R[p]; ++i) if(a[i] + ad[p] < d) ++ret;
            for(int i = L[q]; i <= r; ++i) if(a[i] + ad[q] < d) ++ret;
            for(int i = p + 1; i <= q - 1; ++i)
            {
                int id = lower_bound(v[i].begin(), v[i].end(), d - ad[i]) - v[i].begin();
                ret += id;
            }
        }
        return ret;
    }
    
    int main()
    {
        n = read(), m = n;
        for(int i = 1; i <= n; ++i) a[i] = read();
        k = sqrt(n); //分成k块
        for(int i = 1; i <= k; ++i)
        {
            L[i] = (i - 1) * k + 1;
            R[i] = i * k;
        }
        if(R[k] < n) //最后有一小块
        {
            ++k;
            L[k] = R[k - 1] + 1;
            R[k] = n;
        }
        for(int i = 1; i <= k; ++i)
        {
            for(int j = L[i]; j <= R[i]; ++j)
            {
                pos[j] = i;
                v[i].push_back(a[j]);
            }
            sort(v[i].begin(), v[i].end());
        }
        while(m--)
        {
            int l, r, op;
            ll d;
            op = read(), l = read(), r = read(), d = read();
            if(op == 0)
            {
                add(l, r, d);
            }
            else if(op == 1)
                printf("%lld\n", ask(l, r, d * d));
        }
        return 0;
    }

### LOJ 6279 数列分块入门3 ###

***给出一个长为 n 的数列，以及  n个操作，操作涉及区间加法，询问区间内小于某个值x  的前驱（比其小的最大元素）。***

思路：这题其实和分块2差不多，同样是需要排序然后二分找，就是一些细节方面需要注意一下

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e6 + 10;
    const ll linf = 0x3f3f3f3f3f3f3f3f;
    ll L[maxn], R[maxn], pos[maxn], ad[maxn], a[maxn];
    vector<ll> v[1010];
    int n, m, k; //k个块
    
    int read()
    {
        int x = 0, w = 1;
        char ch = 0;
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') w = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * w;
    }
    void rset(int x)
    {
        v[x].clear();
        for(int i = L[x]; i <= R[x]; ++i) v[x].push_back(a[i]);
        sort(v[x].begin(), v[x].end());
    }
    void add(int l, int r, ll d) //区间[l, r]加上d
    {
        int p = pos[l], q = pos[r];
        if(p == q) //同块
        {
            for(int i = l; i <= r; ++i) a[i] += d;
            rset(p);
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i) ad[i] += d;
            for(int i = l; i <= R[p]; ++i) a[i] += d;
            for(int i = L[q]; i <= r; ++i) a[i] += d;
            rset(p), rset(q);
        }
    }
    ll ask(int l, int r, ll d)
    {
        int p = pos[l], q = pos[r];
        ll ret = -linf;
        if(p == q)
        {
            for(int i = l; i <= r; ++i)
                if(a[i] + ad[p] < d)
                    ret = max(ret, a[i] + ad[p]);
        }
        else
        {
            for(int i = l; i <= R[p]; ++i) if(a[i] + ad[p] < d) ret = max(ret, a[i] + ad[p]);
            for(int i = L[q]; i <= r; ++i) if(a[i] + ad[q] < d) ret = max(ret, a[i] + ad[q]);
            for(int i = p + 1; i <= q - 1; ++i)
            {
                int id = lower_bound(v[i].begin(), v[i].end(), d - ad[i]) - v[i].begin();
                if(id >= 1 && v[i][id - 1] + ad[i] < d) ret = max(ret, v[i][id - 1] + ad[i]);
                if(id >= 2 && v[i][id - 2] + ad[i] < d) ret = max(ret, v[i][id - 2] + ad[i]);
            }
        }
        if(ret != -linf)
            return ret;
        return -1;
    }
    
    int main()
    {
        n = read(), m = n;
        for(int i = 1; i <= n; ++i) a[i] = read();
        k = sqrt(n); //分成k块
        for(int i = 1; i <= k; ++i)
        {
            L[i] = (i - 1) * k + 1;
            R[i] = i * k;
        }
        if(R[k] < n) //最后有一小块
        {
            ++k;
            L[k] = R[k - 1] + 1;
            R[k] = n;
        }
        for(int i = 1; i <= k; ++i)
        {
            for(int j = L[i]; j <= R[i]; ++j)
            {
                pos[j] = i;
                v[i].push_back(a[j]);
            }
            sort(v[i].begin(), v[i].end());
        }
        while(m--)
        {
            int l, r, op;
            ll d;
            op = read(), l = read(), r = read(), d = read();
            if(op == 0)
            {
                add(l, r, d);
            }
            else if(op == 1)
                printf("%lld\n", ask(l, r, d));
        }
        return 0;
    }

## ##

### LOJ 6280 数列分块入门4 ###

***给出一个长为 n的数列，以及 n个操作，操作涉及区间加法，区间求和。***

思路：在分块1的基础上，我们需要再用一个sum来记录每个块增加的和，如果一个块都增加了就 加上block \* x， 否则该块有多少个元素增加就加上多少个x。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e5 + 10;
    ll a[maxn], sum[maxn], ad[maxn]; //数组，sum[i]第i块的和，ad[i]第i块的增量
    ll L[maxn], R[maxn], pos[maxn]; //每段左右端点和每个位置属于哪一段
    int n, m, k; //k个块
    
    void add(int l, int r, ll d) //区间[l, r]加上d
    {
        int p = pos[l], q = pos[r];
        if(p == q) //同块
        {
            for(int i = l; i <= r; ++i) a[i] += d;
            sum[p] += d * (r - l + 1);
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i) ad[i] += d;
            for(int i = l; i <= R[p]; ++i) a[i] += d;
            for(int i = L[q]; i <= r; ++i) a[i] += d;
            sum[p] += d * (R[p] - l + 1);
            sum[q] += d * (r - L[q] + 1);
        }
    }
    ll ask(int l, int r, ll d)
    {
        int p = pos[l], q = pos[r];
        ll ret = 0;
        if(p == q)
        {
            for(int i = l; i <= r; ++i) ret += a[i];
            ret += ad[p] * (r - l + 1);
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i) ret += sum[i] + ad[i] * (R[i] - L[i] + 1);
            for(int i = l; i <= R[p]; ++i) ret += a[i];
            for(int i = L[q]; i <= r; ++i) ret += a[i];
            ret += ad[p] * (R[p] - l + 1);
            ret += ad[q] * (r - L[q] + 1);
        }
        return ret % d;
    }
    
    int main()
    {
        scanf("%d", &n); m = n;
        for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        k = sqrt(n); //分成k块
        for(int i = 1; i <= k; ++i)
        {
            L[i] = (i - 1) * k + 1;
            R[i] = i * k;
        }
        if(R[k] < n) //最后有一小块
        {
            ++k;
            L[k] = R[k - 1] + 1;
            R[k] = n;
        }
        for(int i = 1; i <= k; ++i)
        {
            for(int j = L[i]; j <= R[i]; ++j)
            {
                pos[j] = i;
                sum[i] += a[j];
            }
        }
        while(m--)
        {
            int l, r, op; ll d;
            scanf("%d%d%d%lld", &op, &l, &r, &d);
            if(op == 0)
            {
                add(l, r, d);
            }
            else if(op == 1)
                printf("%lld\n", ask(l, r, d + 1));
        }
        return 0;
    }

### LOJ 6281 数列分块入门5 ###

***给出一个长为  n的数列 ，以及  n个操作，操作涉及区间开方，区间求和。***

思路：对于这道题，我们可以发现对于任意数，在经历若干次开方后都变成了0或者1，所以我们记录一下这个块是否还需要更新，如果需要就暴力更新就行了

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e5 + 10;
    ll a[maxn], sum[maxn]; //数组，sum[i]第i块的和
    ll L[maxn], R[maxn], pos[maxn]; //每段左右端点和每个位置属于哪一段
    bool vis[maxn]; //true表示有元素修改还会变化
    int n, m, k; //k个块
    
    void add(int l, int r) //区间[l, r]加上d
    {
        int p = pos[l], q = pos[r];
        if(p == q) //同块
        {
            for(int i = l; i <= r; ++i)
            {
                sum[p] = sum[p] - a[i] + sqrt(a[i]);
                a[i] = sqrt(a[i]);
            }
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i)
            {
                if(vis[i]) //如果需要更改
                {
                    bool flag = false;
                    for(int j = L[i]; j <= R[i]; ++j)
                    {
                        sum[i] = sum[i] - a[j] + sqrt(a[j]);
                        a[j] = sqrt(a[j]);
                        if(a[j] > 1) flag = true;
                    }
                    vis[i] = flag;
                }
            }
            for(int i = l; i <= R[p]; ++i)
            {
                sum[p] = sum[p] - a[i] + sqrt(a[i]);
                a[i] = sqrt(a[i]);
            }
            for(int i = L[q]; i <= r; ++i)
            {
                sum[q] = sum[q] - a[i] + sqrt(a[i]);
                a[i] = sqrt(a[i]);
            }
        }
    }
    ll ask(int l, int r)
    {
        int p = pos[l], q = pos[r];
        ll ret = 0;
        if(p == q)
        {
            for(int i = l; i <= r; ++i) ret += a[i];
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i) ret += sum[i];
            for(int i = l; i <= R[p]; ++i) ret += a[i];
            for(int i = L[q]; i <= r; ++i) ret += a[i];
        }
        return ret;
    }
    
    int main()
    {
        scanf("%d", &n); m = n;
        for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        k = sqrt(n); //分成k块
        for(int i = 1; i <= k; ++i)
        {
            L[i] = (i - 1) * k + 1;
            R[i] = i * k;
        }
        if(R[k] < n) //最后有一小块
        {
            ++k;
            L[k] = R[k - 1] + 1;
            R[k] = n;
        }
        for(int i = 1; i <= k; ++i)
        {
            bool flag = false;
            for(int j = L[i]; j <= R[i]; ++j)
            {
                pos[j] = i;
                if(a[j] > 1) flag = true;
                sum[i] += a[j];
            }
            vis[i] = flag;
        }
        while(m--)
        {
            int l, r, op; ll d;
            scanf("%d%d%d%lld", &op, &l, &r, &d);
            if(op == 0)
            {
                add(l, r);
            }
            else if(op == 1)
                printf("%lld\n", ask(l, r));
        }
        return 0;
    }

### LOJ 6282 数列分块入门6 ###

***给出一个长为 n的数列，以及  n个操作，操作涉及单点插入，单点询问，数据随机生成。***

思路：由于数据随机，所以我们可以维护一个动态的块，每次就动态插入就行了，如果某个块比较大的时候我们就再重新分块一下。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 2e5 + 10;
    vector<ll> v[1010];
    ll a[maxn], L[maxn], R[maxn], b[maxn];
    int n, m, k; //k个块
    
    int read()
    {
        int x = 0, w = 1;
        char ch = 0;
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') w = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * w;
    }
    void build(int f)
    {
        if(f)
        {
            int tot = 0;
            for(int i = 1; i <= k; ++i)
            {
                for(int j = 0; j < v[i].size(); ++j)
                    a[++tot] = v[i][j];
            }
        }
        k = sqrt(n); //分成k块
        for(int i = 1; i <= k; ++i)
        {
            L[i] = (i - 1) * k + 1;
            R[i] = i * k;
        }
        if(R[k] < n) //最后有一小块
        {
            ++k;
            L[k] = R[k - 1] + 1;
            R[k] = n;
        }
        for(int i = 1; i <= k; ++i)
        {
            v[i].clear();
            for(int j = L[i]; j <= R[i]; ++j)
                v[i].push_back(a[j]);
        }
    }
    void add(int l, int r) //l前插入k
    {
        int p = 1;
        while(l > R[p]) ++p;
        if(p > k) return;
        int tot = 0;
        for(int i = R[p]; i >= l; --i)
            b[++tot] = v[p].back(), v[p].pop_back();
        v[p].push_back(r);
        while(tot) v[p].push_back(b[tot--]);
        R[p]++;
        for(int i = p + 1; i <= k; ++i) L[i]++, R[i]++;
        if(R[p] - L[p] > 3 * k) build(1);
    }
    ll ask(int r)
    {
        int p = 1;
        while(r > R[p]) ++p;
        if(p > k) return -1;
        return v[p][r - L[p]];
    }
    
    int main()
    {
        n = read(); m = n;
        for(int i = 1; i <= n; ++i) a[i] = read();
        build(0);
        while(m--)
        {
            int l, r, op; ll d;
            op = read(), l = read(), r = read(), d = read();
            if(op == 0)
            {
                add(l, r);
                ++n;
            }
            else if(op == 1)
                printf("%lld\n", ask(r));
        }
        return 0;
    }

### LOJ 6283 数列分块入门7 ###

***给出一个长为 n 的数列，以及 n 个操作，操作涉及区间乘法，区间加法，单点询问。***

思路：分块区间加，区间乘，单点查询，主要在于标记的更新  
如果已经乘标记m1，加标记a1，那么进行乘m2时，m1 -> m1 \* m2, a1 -> a1 \* m2  
如果已经乘标记m1，加标记a1，那么进行加a2时，m1 -> m1, a1 -> a1 + a2  
对于两端块，我们将块计算并清空标记，中间块就继续叠加标记

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 2e5 + 10;
    const int mod = 10007;
    ll a[maxn], L[maxn], R[maxn], pos[maxn];
    ll ad[maxn], mu[maxn]; //加标记和乘标记
    int n, m, k; //k个块
    
    int read()
    {
        int x = 0, w = 1;
        char ch = 0;
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') w = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * w;
    }
    void build()
    {
        k = sqrt(n); //分成k块
        for(int i = 1; i <= k; ++i)
        {
            L[i] = (i - 1) * k + 1;
            R[i] = i * k;
        }
        if(R[k] < n) //最后有一小块
        {
            ++k;
            L[k] = R[k - 1] + 1;
            R[k] = n;
        }
        for(int i = 1; i <= k; ++i)
            for(int j = L[i]; j <= R[i]; ++j)
                pos[j] = i;
    }
    void slove(int p)
    {
        for(int i = L[p]; i <= R[p]; ++i)
            a[i] = (a[i] * mu[p] % mod + ad[p]) % mod;
        ad[p] = 0, mu[p] = 1;
    }
    void add(int l, int r, ll c)
    {
        int p = pos[l], q = pos[r];
        if(p == q)
        {
            slove(p);
            for(int i = l; i <= r; ++i) a[i] = (a[i] + c) % mod; //然后再进行操作
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i) ad[i] = (ad[i] + c) % mod;
            slove(p), slove(q);
            for(int i = l; i <= R[p]; ++i) a[i] = (a[i] + c) % mod;
            for(int i = L[q]; i <= r; ++i) a[i] = (a[i] + c) % mod;
        }
    }
    void mul(int l, int r, ll c)
    {
        int p = pos[l], q = pos[r];
        if(p == q)
        {
            slove(p);
            for(int i = l; i <= r; ++i) a[i] = a[i] * c % mod;
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i) ad[i] = ad[i] * c % mod, mu[i] = mu[i] * c % mod;
            slove(p), slove(q);
            for(int i = l; i <= R[p]; ++i) a[i] = (a[i] * c) % mod;
            for(int i = L[q]; i <= r; ++i) a[i] = (a[i] * c) % mod;
        }
    }
    ll ask(int r)
    {
        int p = pos[r];
        return (a[r] * mu[p] % mod + ad[p]) % mod;
    }
    
    int main()
    {
        n = read(); m = n;
        for(int i = 1; i <= n; ++i) a[i] = read(), mu[i] = 1;
        build();
        while(m--)
        {
            int l, r, op; ll c;
            op = read(), l = read(), r = read(), c = read();
            if(op == 0) add(l, r, c % mod);
            else if(op == 1) mul(l, r, c % mod);
            else printf("%lld\n", ask(r));
        }
        return 0;
    }

### LOJ 6284 数列分块入门8 ###

***给出一个长为 n 的数列，以及 n 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 。***

思路：这题也不难，记录一下当前块是否需要修改，需要就暴力修改，细节需要注意，我就是扣了半天

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 2e5 + 10;
    const ll linf = 0x3f3f3f3f3f3f3f3f;
    ll a[maxn], L[maxn], R[maxn], pos[maxn], num[maxn];
    int n, m, k; //k个块
    
    int read()
    {
        int x = 0, w = 1;
        char ch = 0;
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') w = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * w;
    }
    void build()
    {
        k = sqrt(n); //分成k块
        for(int i = 1; i <= k; ++i)
        {
            L[i] = (i - 1) * k + 1;
            R[i] = i * k;
            num[i] = -linf;
        }
        if(R[k] < n) //最后有一小块
        {
            ++k;
            L[k] = R[k - 1] + 1;
            R[k] = n;
            num[k] = -linf;
        }
        for(int i = 1; i <= k; ++i)
            for(int j = L[i]; j <= R[i]; ++j)
                pos[j] = i;
    }
    ll slove(int l, int r, ll c)
    {
        int p = pos[l], q = pos[r];
        ll ret = 0;
        if(p == q)
        {
            if(num[p] != -linf) //当前有值
            {
                if(num[p] == c) ret += r - l + 1;
                else
                {
                    for(int i = L[p]; i <= R[p]; ++i)
                    {
                        if(i >= l && i <= r) a[i] = c;
                        else a[i] = num[p];
                    }
                    num[p] = -linf;
                }
            }
            else
            {
                for(int i = l; i <= r; ++i)
                {
                    if(a[i] == c) ++ret;
                    a[i] = c;
                }
            }
        }
        else
        {
            for(int i = p + 1; i <= q - 1; ++i)
            {
                if(num[i] != -linf)
                {
                    if(num[i] == c)
                        ret += R[i] - L[i] + 1;
                    num[i] = c;
                }
                else
                {
                    for(int j = L[i]; j <= R[i]; ++j)
                    {
                        if(a[j] == c) ++ret;
                        a[j] = c;
                    }
                    num[i] = c;
                }
            }
            if(num[p] != -linf)
            {
                if(num[p] == c) ret += R[p] - l + 1;
                else
                {
                    for(int i = L[p]; i <= R[p]; ++i)
                    {
                        if(i >= l) a[i] = c;
                        else a[i] = num[p];
                    }
                    num[p] = -linf;
                }
            }
            else
            {
                for(int i = l; i <= R[p]; ++i)
                {
                    if(a[i] == c) ++ret;
                    a[i] = c;
                }
            }
            if(num[q] != -linf)
            {
                if(num[q] == c) ret += r - L[q] + 1;
                else
                {
                    for(int i = L[q]; i <= R[q]; ++i)
                    {
                        if(i <= r) a[i] = c;
                        else a[i] = num[q];
                    }
                    num[q] = -linf;
                }
            }
            else
            {
                for(int i = L[q]; i <= r; ++i)
                {
                    if(a[i] == c) ++ret;
                    a[i] = c;
                }
            }
        }
        return ret;
    }
    
    int main()
    {
        n = read(); m = n;
        for(int i = 1; i <= n; ++i) a[i] = read();
        build();
        while(m--)
        {
            int l, r, op; ll c;
            l = read(), r = read(), c = read();
            printf("%lld\n", slove(l, r, c));
        }
        return 0;
    }