#P18687. Canvas

    ID: 18023 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-逆向思考队列Kosaraju 算法缩点

Canvas

Canvas

有一个长度为 nn 的序列,最初所有元素均为 00。还有 mm 次操作:第 ii 次操作会将序列中第 lil_i 个元素的值改为 xix_i,同时将第 rir_i 个元素的值改为 yiy_i。每次操作都必须恰好执行一次。

请找出执行这些操作的最优顺序,使所有操作执行完毕后,序列中所有元素的和最大。

输入格式

输入包含多组测试用例。第一行包含一个整数 TT,表示测试用例数。

对于每个测试用例:

第一行包含两个整数 n,mn,m(2≤n,m≤5×1052\le n,m\le5\times10^5),分别表示序列长度和操作次数。

接下来 mm 行,第 ii 行包含四个整数 li,xi,ri,yil_i,x_i,r_i,y_i(1≤li<ri≤n1\le l_i<r_i\le n,1≤xi,yi≤21\le x_i,y_i\le2),表示第 ii 次操作。

保证整个输入中所有测试用例的 nn 之和不超过 5×1055\times10^5,所有测试用例的 mm 之和也不超过 5×1055\times10^5。

输出格式

对于每个测试用例,首先输出一行,包含一个整数,表示所有操作执行完毕后,序列中所有元素之和的最大值。

然后输出一行,包含 mm 个用空格分隔的整数 a1,a2,…,ama_1,a_2,\ldots,a_m,表示最优的操作执行顺序,其中 aia_i 是第 ii 个执行的操作的编号。11 到 mm 中的每个整数都必须恰好出现一次。

如果存在多个合法答案,输出任意一个即可。

样例 1 输入

2
4 4
1 1 2 2
3 2 4 1
1 2 3 2
2 1 4 1
4 2
3 2 4 1
1 2 3 1

样例 1 输出

7
4 1 3 2
5
2 1

样例说明

对于第一组测试用例,按照 4,1,3,24,1,3,2 的顺序执行操作后,序列变为 {2,2,2,1}\{2,2,2,1\},所有元素的和为 77。

对于第二组测试用例,按照 2,12,1 的顺序执行操作后,序列变为 {2,0,2,1}\{2,0,2,1\},所有元素的和为 55。