题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(3 \leq n \leq 2 \times 10^5)$和三个长为$n$的数组$a$、$b$、$c$，元素范围$[1,10^6]$。保证三个数组的元素和都等于$tot$。

你需要找到三个不相交区间$[l_1,r_1]$, $[l_2,r_2]$, $[l_3,r_3]$，满足

1. $a$的$[l_1,r_1]$的子数组和$\geq ceil(\frac{tot}{3})$。
2. $b$的$[l_2,r_2]$的子数组和$\geq ceil(\frac{tot}{3})$。
3. $c$的$[l_3,r_3]$的子数组和$\geq ceil(\frac{tot}{3})$。

输出任意满足要求的$l_1,r_1,l_2,r_2,l_3,r_3$（下标从$1$开始）。如果无解，输出$-1$。注意三个区间没有位置顺序，例如$[l_1,r_1]$不一定在最左边。

输入样例

10
5
5 1 1 1 1
1 1 5 1 1
1 1 1 1 5
6
1 2 3 4 5 6
5 6 1 2 3 4
3 4 5 6 1 2
4
4 4 4 4
4 4 4 4
4 4 4 4
5
5 10 5 2 10
9 6 9 7 1
10 7 10 2 3
3
4 5 2
6 1 4
1 8 2
3
10 4 10
8 7 9
10 4 10
7
57113 65383 19795 53580 74452 3879 23255
12917 16782 89147 93107 27365 15044 43095
33518 63581 33565 34112 46774 44151 41756
6
6 3 1 8 7 1
10 2 6 2 2 4
10 9 2 1 2 2
5
5 5 4 5 5
1 6 3 8 6
2 4 1 9 8
10
1 1 1 1 1001 1 1 1001 1 1
1 1 1 1 1 1 2001 1 1 1
1 1 1 1 1 1001 1 1 1 1001

输出样例

1 1 2 3 4 5 
5 6 1 2 3 4 
-1
-1
1 1 3 3 2 2 
-1
1 2 3 4 5 7 
3 6 1 1 2 2 
1 2 3 4 5 5 
1 5 6 7 8 10 

算法

前后缀分解

这种三元组问题一般来说很容易想到前后缀分解，预处理出前后缀信息，然后枚举中间那一段进行统计和判断。但是本题的三个区间没有顺序要求，这就使得情况比较多，写起来很繁琐。

先把$a$、$b$、$c$三个数组处理成前缀和数组，然后遍历数组，枚举子数组的右端点$r$，对于以$r$结尾的子数组，由于数组中的元素都是正数，因此前缀和是单调递增的，具有单调性。对于给定的$r$，二分找到最近的左端点$l$，确保子数组$[l,r]$的累加和$\geq ceil(\frac{tot}{3})$，令$pre[r]=l$。同理，遍历子数组的左端点$l$，二分找到最近的右端点$r$，确保子数组$[l,r]$的累加和$\geq ceil(\frac{tot}{3})$，令$suf[l]=r$。还需要预处理出来两个数组$left$和$right$，$left[i]$表示前缀$[1,i]$中是否有符合题意的子数组，$right[i]$表示后缀$[i,n]$中是否有符合题意的子数组。

以$a$的区间在中间，$b$的区间在左边，$c$的区间在右边为例进行说明。$a$、$b$、$c$三个数组预处理出来的信息为$pre_1$、$suf_1$、$left_1$、$right_1$、$pre_2$、$suf_2$、$left_2$、$right_2$、$pre_3$、$suf_3$、$left_3$、$right_3$。枚举$a$的左端点$l$，只要满足$r=suf_1[l] \neq -1$有解，就检查$left_2[l-1]$和$right_3[r+1]$是否为真，为真就说明$[l,r]$的左右两边都存在符合条件的子数组，遍历一下$pre_2$和$suf_3$，把$b$和$c$的子数组找出来就行。

一共存在以下$6$种情况，从左往右分别是取出区间对应的数组。每种情况都要做以上的检查，有解就保留一个解，如果一个解都没找到就输出$-1$：

1. $bac$
2. $cab$
3. $abc$
4. $cba$
5. $acb$
6. $bca$

复杂度分析

时间复杂度

对$a$、$b$、$c$三个数组，预处理出$pre$和$suf$的时间复杂度是$O(nlog_2)$（遍历一个端点+二分查找另一个端点）。预处理出$left$、$right$的时间复杂度是线性的，为$O(n)$。最后穷举$6$种情况，通过前后缀分解找到答案，时间复杂度也为$O(n)$。

综上，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

对于$a$、$b$、$c$三个数组，都开辟了几个线性空间的辅助数组$pre$、$suf$、$left$、$right$。因此整个算法的额外空间复杂度可以看做是$O(n)$，只是常数比较大。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, pre1[N], suf1[N], pre2[N], suf2[N], pre3[N], suf3[N];
LL a[N], b[N], c[N];
bool l1[N], r1[N], l2[N], r2[N], l3[N], r3[N];

void solve(LL v[], int pre[], int suf[], bool left[], bool right[]) {
    for(int i = 1; i <= n; i++) {
        int l = i, r = n, index = -1;
        while(l <= r) {
            int mid = l + r >> 1;
            if(v[mid] - v[i - 1] >= (v[n] + 2)/3) {
                index = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        suf[i] = index;
        l = 1, r = i, index = -1;
        while(l <= r) {
            int mid = l + r >> 1;
            if(v[i] - v[mid - 1] >= (v[n] + 2)/3) {
                index = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        pre[i] = index;
    }
    left[0] = false;
    for(int i = 1; i <= n; i++) {
        left[i] = left[i - 1] || pre[i] != -1;
    }
    right[n + 1] = false;
    for(int i = n; i >= 1; i--) {
        right[i] = right[i + 1] || suf[i] != -1;
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            a[i] += a[i - 1];
            pre1[i] = suf1[i] = pre2[i] = suf2[i] = pre3[i] = suf3[i] = -1;
        }
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &b[i]);
            b[i] += b[i - 1];
        }
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &c[i]);
            c[i] += c[i - 1];
        }
        solve(a, pre1, suf1, l1, r1);
        solve(b, pre2, suf2, l2, r2);
        solve(c, pre3, suf3, l3, r3);
        bool ok = false;
        vector<array<int, 2>> ans;
        // a在中间
        for(int l = 2; l < n && !ok; l++) {
            int r = suf1[l];
            if(r != -1) {
                if(l3[l - 1] && r2[r + 1]) {
                    // c在左边，b在右边
                    ok = true;
                    ans.push_back({l, r});
                    for(int j = r + 1; j <= n; j++) {
                        if(suf2[j] != -1) {
                            ans.push_back({j, suf2[j]});
                            break;
                        }
                    }
                    for(int j = l - 1; j >= 1; j--) {
                        if(pre3[j] != -1) {
                            ans.push_back({pre3[j], j});
                            break;
                        }
                    }
                }
                if(!ok && l2[l - 1] && r3[r + 1]) {
                    // b在左边，c在右边
                    ok = true;
                    ans.push_back({l, r});
                    for(int j = l - 1; j >= 1; j--) {
                        if(pre2[j] != -1) {
                            ans.push_back({pre2[j], j});
                            break;
                        }
                    }
                    for(int j = r + 1; j <= n; j++) {
                        if(suf3[j] != -1) {
                            ans.push_back({j, suf3[j]});
                            break;
                        }
                    }
                }
            }
        }
        // b在中间
        for(int l = 2; l < n && !ok; l++) {
            int r = suf2[l];
            if(r != -1) {
                if(l1[l - 1] && r3[r + 1]) {
                    // a在左边，c在右边
                    ok = true;
                    for(int j = l - 1; j >= 1; j--) {
                        if(pre1[j] != -1) {
                            ans.push_back({pre1[j], j});
                            break;
                        }
                    }
                    ans.push_back({l, r});
                    for(int j = r + 1; j <= n; j++) {
                        if(suf3[j] != -1) {
                            ans.push_back({j, suf3[j]});
                            break;
                        }
                    }
                }
                if(!ok && l3[l - 1] && r1[r + 1]) {
                    // c在左边，a在右边
                    ok = true;
                    for(int j = r + 1; j <= n; j++) {
                        if(suf1[j] != -1) {
                            ans.push_back({j, suf1[j]});
                            break;
                        }
                    }
                    ans.push_back({l, r});
                    for(int j = l - 1; j >= 1; j--) {
                        if(pre3[j] != -1) {
                            ans.push_back({pre3[j], j});
                            break;
                        }
                    }
                }
            }
        }
        // c在中间
        for(int l = 2; l < n && !ok; l++) {
            int r = suf3[l];
            if(r != -1) {
                if(l1[l - 1] && r2[r + 1]) {
                    // a在左边，b在右边
                    ok = true;
                    for(int j = l - 1; j >= 1; j--) {
                        if(pre1[j] != -1) {
                            ans.push_back({pre1[j], j});
                            break;
                        }
                    }
                    for(int j = r + 1; j <= n; j++) {
                        if(suf2[j] != -1) {
                            ans.push_back({j, suf2[j]});
                            break;
                        }
                    }
                    ans.push_back({l, r});
                }
                if(!ok && l2[l - 1] && r1[r + 1]) {
                    // b在左边，a在右边
                    ok = true;
                    for(int j = r + 1; j <= n; j++) {
                        if(suf1[j] != -1) {
                            ans.push_back({j, suf1[j]});
                            break;
                        }
                    }
                    for(int j = l - 1; j >= 1; j--) {
                        if(pre2[j] != -1) {
                            ans.push_back({pre2[j], j});
                            break;
                        }
                    }
                    ans.push_back({l, r});
                }
            }
        }
        if(!ok) {
            puts("-1");
        }else {
            for(auto&rng: ans) {
                printf("%d %d ", rng[0], rng[1]);
            }
            puts("");
        }
    }
    return 0;
}