题目描述

给定一个长度为 $n$ 的序列，序列上的数为 $a_i \leq n$
进行 $m$ 次操作，每次操作为区间取$min$ 或求区间第 $k$ 小数
$1 \leq n, m \leq 8 \times 10^4$

输入样例

3 5
1 2 3
2 1 3 2
1 3 3 1
2 1 3 2
1 1 2 3
2 1 3 2

输出样例

2
1
1

分块

数据范围不大而且给了 $6$ 秒直接分块

块内的数升序存储，同时维护每块的最大值 $d$

修改操作：
对于不是完整块的部分直接修改，然后重构其所在的块
完整的块只对最大值取 $min$ （懒标记效果）

查询操作：
二分答案，$check$ 区间中是否存在 $k$ 个 $\leq mid$ 的数
对于不是完整块的部分，遍历并且用其所在块的最大值对它取 $min$ （下放懒标记）

完整的块的最大值 $\leq mid$ 时累计块的大小
否则二分求块内有多少 $\leq mid$ 的数，取第一个大于等于mid + 1的数的下标-1

时间复杂度 $O(mlog(n)sqrt(n))$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 80010, M = 285;

int n, m;
int a[N];

struct Block{
    int l, r, len;
    int a[M], d;        //  块内的最大值
}blk[M];

int s, cnt;     //  块的大小，个数
int id[N];      //  每个数是属于哪块的

void build()
{
    s = sqrt(n);
    cnt = n / s;  if(n % s)  cnt ++;

    blk[1].l = 1;
    for(int i = 1, j = 1; i <= n; i ++)
    {
        id[i] = (i - 1) / s + 1;
        blk[id[i]].a[j ++] = a[i];
        if(j > s)
        {
            blk[id[i]].r = i;
            blk[id[i] + 1].l = i + 1;
            j = 1;
        }
    }
    blk[cnt].r = n;

    for(int i = 1; i <= cnt; i ++)
    {
        blk[i].len = blk[i].r - blk[i].l + 1;
        sort(blk[i].a + 1, blk[i].a + blk[i].len + 1);
        blk[i].d = blk[i].a[blk[i].len];
    }
}

void modify(int l, int r, int x)
{
    if(id[l] == id[r])
    {
        Block &u = blk[id[l]];
        for(int i = l; i <= r; i ++)  a[i] = min(a[i], x);
        for(int i = u.l, j = 1; i <= u.r; i ++)
            u.a[j ++] = min(a[i], u.d);
        sort(u.a + 1, u.a + u.len + 1);
        u.d = u.a[u.len];
    }
    else
    {
        {
            Block &u = blk[id[l]];
            for(int i = l; i <= u.r; i ++)  a[i] = min(a[i], x);
            for(int i = u.l, j = 1; i <= u.r; i ++)
                u.a[j ++] = min(a[i], u.d);
            sort(u.a + 1, u.a + u.len + 1);
            u.d = u.a[u.len];
        }
        {
            Block &u = blk[id[r]];
            for(int i = u.l; i <= r; i ++)  a[i] = min(a[i], x);        
            for(int i = u.l, j = 1; i <= u.r; i ++)
                u.a[j ++] = min(a[i], u.d);
            sort(u.a + 1, u.a + u.len + 1);
            u.d = u.a[u.len];
        }
        for(int i = id[l] + 1; i < id[r]; i ++)
            blk[i].d = min(blk[i].d, x);
    }
}

bool check(int l, int r, int k, int x)     //  在[l, r]是否存在k个<=x的数
{
    int res = 0;
    if(id[l] == id[r])
    {
        if(blk[id[l]].d <= x)  return r - l + 1 >= k;
        for(int i = l; i <= r; i ++)
            if(a[i] <= x)  res ++;
        return res >= k;
    }

    if(blk[id[l]].d <= x)  res += blk[id[l]].r - l + 1;
    else
    {
        for(int i = l; i <= blk[id[l]].r; i ++)
        {
            a[i] = min(a[i], blk[id[i]].d);
            if(a[i] <= x)  res ++;
        }
    }

    if(blk[id[r]].d <= x)  res += r - blk[id[r]].l + 1;
    else
    {
        for(int i = blk[id[r]].l; i <= r; i ++)
        {
            a[i] = min(a[i], blk[id[i]].d);
            if(a[i] <= x)  res ++;
        }
    }

    for(int i = id[l] + 1; i < id[r]; i ++)
    {
        if(blk[i].d <= x)  res += blk[i].len;
        else  res += lower_bound(blk[i].a, blk[i].a + blk[i].len + 1, x + 1) - blk[i].a - 1;
    }
    return res >= k;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]);

    build();

    while(m --)
    {
        int op, x, y, k;
        scanf("%d%d%d%d", &op, &x, &y, &k);
        if(op == 1)  modify(x, y, k);
        else
        {
            int l = 1, r = n;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(check(x, y, k, mid))  r = mid;
                else  l = mid + 1;
            }
            printf("%d\n", l);
        }
        //for(int i = 1; i <= n; i ++)  printf("%d ", a[i]);  puts("");
        //for(int i = 1; i <= cnt; i ++)  printf("[%d, %d].d = %d\n", blk[i].l, blk[i].r, blk[i].d);
    }
    return 0;
}