题目链接https://codeforces.com/gym/105657/problem/H题目描述题解代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;constintN1000010;constintmod998244353;structnode{intl,r,d;// 从大到小排序booloperator(constnoderhs)const{returndrhs.d;}}arr[N];intfather[N];// 记录每个结点的父节点intn,k;voidsolve(){cinnk;for(inti1;ik;i){cinarr[i].larr[i].r;arr[i].darr[i].r-arr[i].l1;}// 只有一条直接返回if(k1){for(intiarr[1].l;iarr[1].r;i){father[i]i-1;}// root的父亲为0father[arr[1].l]0;for(inti1;in;i){coutfather[i] \n[in];}return;}sort(arr1,arrk1);// 不合法1: 全部大小相同boolflagtrue;for(inti1;ik;i){if(arr[i].d!arr[1].d){flagfalse;break;}}if(flag){coutIMPOSSIBLE\n;return;}// 不合法2: 最长链两个以上相同, 并且相差不超过1if(arr[1].darr[2].darr[1].d-arr[k].d1){coutIMPOSSIBLE\n;return;}// 合法1: 若最长链子只有一条if(arr[1].d!arr[2].d){for(inti1;ik;i){father[arr[i].l]arr[1].l;for(intjarr[i].l1;jarr[i].r;j){father[j]j-1;}}// root的父亲为0father[arr[1].l]0;}// 合法2else{for(inti1;ik;i){father[arr[i].l]arr[1].l;for(intjarr[i].l1;jarr[i].r;j){father[j]j-1;}}// root的父亲为0father[arr[1].l]0;// 把最短那条放到最长那条的第二个结点下father[arr[k].l]arr[1].l1;}// 输出答案for(inti1;in;i){coutfather[i] \n[in];}return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt1;cint;while(t--){solve();}return0;}