题解说明

问题背景：
给定一个长度为 $n$ 的数组，需要判断是否能将其分成 $k$ 段，并输出一组满足条件的分割点。程序通过前缀最小值与后缀最大值的判定，在不同的 $k$ 情况下构造解或判定不可行。

核心思路：
$1.$ 预处理：

• 计算前缀最小值数组 $b[i]$，表示区间 $[1,i]$ 的最小值。
• 计算后缀最大值数组 $c[i]$，表示区间 $[i,n]$ 的最大值。

$2.$ 情况 $k=2$：

• 遍历分割点 $i \in [1,n-1]$，若 $b[i] \ge c[i+1]$，则存在合法分割，输出 $i$。

$3.$ 情况 $k=3$：

• 遍历中间点 $i \in [2,n-1]$，若 $b[i-1] \ge a[i]$ 或 $a[i] \ge c[i+1]$，可取分割点为 $i-1,i$。

$4.$ 情况 $k \ge 4$：

• 找到任意相邻非递增位置 $i$ 满足 $a[i] \ge a[i+1]$。
• 输出核心分割点 $i-1,i,i+1$，其余补足 $k-4+(i=1)+(i=n-1)$ 个任意位置，使总分割点数为 $k-1$。
• 若不存在这样的 $i$，则不可行。

正确性直觉：

• 对于 $k=2,3$，通过前缀最小与后缀最大构造单点或双点分割的充分条件。
• 对于 $k \ge 4$，存在相邻非递增即可作为“转折”中心，三点切分保证两侧满足，剩余分割点可随意补齐。若全局严格递增则无法构造。

复杂度分析：

• 预处理与判定均为线性，时间复杂度 $O(n)$，空间复杂度 $O(n)$。

#include <bits/stdc++.h>
using namespace std;

#define ll long long  // 定义ll为long long类型，简化代码书写
const int SZ = 1 << 20;  // 快速读入缓冲区大小（2^20，约1MB，适配大规模输入）
char buf[SZ], *p1, *p2;  // 快速读入缓冲区指针，p1指向当前读取位置，p2指向缓冲区末尾

// 读取一个字符的宏定义：若缓冲区已读完，从stdin补充读取；否则取当前位置字符
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++)

/**
 * 快速读入整数函数
 * 功能：高效读取正负整数，避免cin/scanf在大数据量下的速度瓶颈
 * 返回值：读取到的整数（long long类型，支持大数值）
 */
ll read() {
    ll n = 0;          // 存储读取结果
    bool m = 0;        // 标记是否为负数（m=1表示输入为负）
    char c = gc();     // 从缓冲区读取第一个字符

    // 跳过非数字字符，同时判断是否为负号
    while (c < '0' || c > '9') {
        m = c == '-';  // 若遇到'-'，将负数标记设为1
        c = gc();
    }

    // 读取数字字符，转换为整数（n<<3 + n<<1 等价于 n*10，位运算效率更高）
    while (c >= '0' && c <= '9') {
        n = (n << 3) + (n << 1) + (c ^ '0');  // c^'0' 等价于 c-'0'，转换字符为数字
        c = gc();
    }

    return m ? -n : n;  // 根据负数标记返回最终结果（负则取反，正则直接返回）
}

const int N = 500005;    // 数组最大长度（5e5+5，适配题目数据规模）
const int inf = 0x7fffffff;  // 定义无穷大（int类型最大值）
int n, k;                // n：数组长度；k：需要分成的段数
int a[N];                // 存储原始输入数组
int b[N];                // 前缀最小值数组：b[i]表示a[1..i]中的最小值
int c[N];                // 后缀最大值数组：c[i]表示a[i..n]中的最大值

int main() {
    // 读取数组长度n和目标分段数k
    n = read(), k = read();

    // 读取原始数组a（从索引1开始存储，符合日常分段逻辑）
    for (int i = 1; i <= n; i++)
        a[i] = read();

    // 计算前缀最小值数组b：b[0]初始为无穷大（作为第一个元素的比较基准）
    b[0] = inf;
    for (int i = 1; i <= n; i++)
        b[i] = min(a[i], b[i - 1]);  // 每一步取当前元素与前序最小值的较小值

    // 计算后缀最大值数组c：从后往前遍历，c[n+1]默认0（不影响最后一个元素比较）
    for (int i = n; i; i--)
        c[i] = max(a[i], c[i + 1]);  // 每一步取当前元素与后序最大值的较大值

    // 情况1：k=2（需将数组分成2段，找1个分割点i，1<=i<n）
    if (k == 2) {
        // 遍历所有可能的分割点i：前i个为第一段，后n-i个为第二段
        for (int i = 1; i < n; i++) {
            // 条件：第一段的最小值 >= 第二段的最大值（满足分段合法性）
            if (b[i] >= c[i + 1]) {
                puts("TAK");          // 输出"TAK"表示存在合法分段
                printf("%d", i);      // 输出分割点i
                return 0;             // 程序结束
            }
        }
        puts("NIE");  // 遍历完无合法分割点，输出"NIE"
        return 0;
    }

    // 情况2：k=3（需将数组分成3段，找2个分割点i-1和i，2<=i<n）
    if (k == 3) {
        // 遍历中间元素i：分割点为i-1和i，三段分别为1..i-1、i..i、i+1..n
        for (int i = 2; i < n; i++) {
            // 条件：第一段最小值>=中间段值 或 中间段值>=第三段最大值（满足分段合法性）
            if (b[i - 1] >= a[i] || a[i] >= c[i + 1]) {
                puts("TAK");                  // 输出"TAK"
                printf("%d %d", i - 1, i);    // 输出两个分割点
                return 0;
            }
        }
        puts("NIE");  // 无合法分割点，输出"NIE"
        return 0;
    }

    // 情况3：k>=4（需将数组分成k段，找k-1个分割点）
    // 核心逻辑：先找相邻元素非递增的位置i（a[i]>=a[i+1]），以此为中心构造分割点
    for (int i = 1; i < n; i++) {
        // 找到相邻非递增的位置i
        if (a[i] >= a[i + 1]) {
            // 计算需要额外补充的分割点数量x：
            // k-4是基础补充量，i=1或i=n-1时多补1个（因边界位置可选择的分割点少）
            int x = k - 4 + (i == 1) + (i == n - 1);
            puts("TAK");  // 输出"TAK"

            // 输出k-1个分割点：优先输出i-1、i、i+1（围绕非递增位置的核心分割点）
            // 剩余分割点从其他位置补充，直到凑够k-1个
            for (int j = 1; j < n; j++) {
                // 优先输出核心分割点（i-1、i、i+1）
                if (j == i - 1 || j == i || j == i + 1)
                    printf("%d ", j);
                // 补充剩余分割点（x>0时输出其他位置j）
                else if (x) {
                    printf("%d ", j);
                    x--;  // 补充一个，x减1
                }
            }
            return 0;  // 程序结束
        }
    }

    // k>=4时未找到相邻非递增位置，无法构造足够分割点，输出"NIE"
    puts("NIE");
    return 0;
}