CFR-844(Div.1+2)解题报告

发表于 更新于 分类于

比赛传送门

A. Parallel Projection

题意：有一个 w×d×hw\times d\times h 的长方体，顶面和底面有两个点，只能走直线且不能穿过长方体，求最短距离。

显然曼哈顿距离必须要走。多出来绕弯的距离一定是选一个点，到边缘的最短距离 ×2\times 2。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
signed main() {
    int t;
    cin>>t;
    while(t-->0) {
        int x,y,z,a,b,c,d;
        cin>>x>>y>>z>>a>>b>>c>>d;
        cout<<z+abs(a-c)+abs(b-d)+min({a,b,c,d,x-a,x-c,y-b,y-d})*2<<endl;
    }
    return 0;
}

B. Going to the Cinema

题意：有 nn 个人，每人有一个要求 aia_i，表示他愿意去电影院当且仅当其他人中有至少 aia_i 个去。问全部满足要求的方案数。

首先对 aa 从小到大排序，枚举总共去几个人。假设去 xx 个人，则一定是 aia_i 最小的 xx 个人去。考虑第 xx 个人是否愿意去，以及第 x+1x+1 个人是否愿意不去即可。

By IceYukino

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int T,n,a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1);
        int ans=1;
        if(a[1]!=0) ans++;
        for(int i=1;i<n;i++){
            if(a[i]>i-1||a[i+1]<=i) continue;
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

C. Equal Frequencies

给你一个小写字母字符串，求更改字母的方案，使得让所有出现过的字母的出现次数都相同，且次数尽可能少。

可以枚举需要总共出现几个字母，进而得到每个字母的出现次数 xx。对于每个次数超过 xx 的字母需要砍掉多余的改成其他字母；对于次数不超过 xx 的字母，需要将一些填成 xx，一些砍掉。显然让出现尽可能多的字母填成 xx 最优。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
struct node{
    int val,num;
} tt[26];
int cnt[26];
signed main() {
    int t;
    cin>>t;
    while(t--) {
        memset(tt,0,sizeof(tt));
        memset(cnt,0,sizeof(cnt));
        int n;
        string s;
        cin>>n>>s;
        for(int i=0;i<n;i++)
            tt[s[i]-'a'].val++;
        for(int i=0;i<26;i++)
            tt[i].num=i;
        sort(tt,tt+26,[](node p,node q) {
            return p.val<q.val;
        });
        int minx=1e9,mini;
        for(int i=1;i<=26;i++) {
            if(n%i!=0) continue;
            int x=n/i,sum=0,ans=0;
            for(int j=25;j>=0;j--) {
                if(tt[j].val>x) sum+=tt[j].val-x,ans+=tt[j].val-x;
                else if(26-j<=i) ans+=x-tt[j].val;
                else ans+=tt[j].val;
            }
            if(ans<minx) minx=ans,mini=i;
        }
        int x=n/mini;
        for(int j=25;j>=0;j--) {
            if(tt[j].val>x) cnt[tt[j].num]=x-tt[j].val;
            else if(26-j<=mini) cnt[tt[j].num]=x-tt[j].val;
            else cnt[tt[j].num]=-tt[j].val;
        }
        vector<int> add;
        for(int j=0;j<26;j++)
            while(cnt[j]>0) add.push_back(j),cnt[j]--;
        for(int i=0;i<n;i++)
            if(cnt[s[i]-'a']<0)
                cnt[s[i]-'a']++,s[i]=add.back()+'a',add.pop_back();
        cout<<minx/2<<endl<<s<<endl;
    }
    return 0;
}

D. Many Perfect Squares

题意：有一个不重复的正整数数组 aa，你需要找到一个 xx，使得每个元素加上 xx 后出现尽可能多的完全平方数。

显然答案至少为 11。如果答案超过 22，可以枚举钦定两个变成完全平方数的数 p,q(p<q)p,q(p<q)，则有 a2=p+x,b2=q+xa^2=p+x,b^2=q+x，得出 b2−a2=q−pb^2-a^2=q-p，即 (b+a)(b−a)=q−p(b+a)(b-a)=q-p。对 q−pq-p 枚举因数，求得 a,ba,b，进而得到 xx，即可算出此时的完全平方数个数。

By IceYukino

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int T,n,a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int mx=1;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++){
                int del=a[j]-a[i];
                for(int k=1;k<=sqrt(del);k++){
                    if(del%k!=0) continue;
                    int c=k,b=del/k;
                    if((c+b)%2==1) continue;
                    int tmp=(c+b)/2,y=(c-b)/2;
                    if(tmp*tmp>=a[j]&&y*y>=a[i]&&tmp*tmp-a[j]==y*y-a[i]){
                        int x=tmp*tmp-a[j],sum=0;
                        for(int l=1;l<=n;l++){
                            int u=a[l]+x;
                            int oo=sqrt(u);
                            if(oo*oo==u) sum++;
                        }
                        mx=max(mx,sum);
                    }
                }
            }
        cout<<mx<<endl;
    }
    return 0;
}

有一个优化的技巧，当找到一个确定的 xx 时，不立刻计算数量更新答案，而是存起来，到最后去重后再计算。由于同一个 xx 可能会被多对不同的元素、因数找到，所以优化非常显著。

By noimi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int main() {
    TEST {
        INT(n);
        VEC(ll, a, n);
        vl cand;
        rep(i, n) rep(j, i + 1, n) {
            ll d = a[j] - a[i];
            fore(l, divisor(d)) {
                ll r = d / l;
                if(l > r) continue;
                if((l + r) & 1) continue;
                ll x = (r - l) / 2, y = (r + l) / 2;
                // dump(l, r, x, y, d);
                cand.eb(x * x - a[i]);
            }
        }
        ll ans = 1;
        // rep(i, 0, 100) cand.eb(i);
        fore(e, cand) {
            if(e < 0) continue;
            int now = 0;
            fore(x, a) {
                ll t = x + e;
                ll s = sqrtl(t);
                if(s * s == t) now++;
            }
            // if(now == 2) dump(e);
            chmax(ans, now);
        }
        OUT(ans);
    }
}

枚举因数的过程同样可以通过分解质因数，用 DFS 合并来实现。首先存下每个质因数以及次数，DFS 合并时依此搜索每个质因数，枚举该质因数选几次，进入下一个质因数搜索。由于一个质因数的次数不同，因数就不同，所以一定不重不漏。

By 18Michael

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
inline void init()
{
    for(int i=2;i<=Mx;++i)
    {
        if(!u[i])p[++p_t]=i;
        for(int j=1;j<=p_t && p[j]*i<=Mx;++j)
        {
            u[p[j]*i]=1;
            if(!(i%p[j]))break;
        }
    }
    //printf("%d\n",p_t);
}
inline void solve(int x)
{
    //printf("  solve %d\n",x);
    int w=Z/x;
    if((x^w)&1)return ;
    /*a+b=w
	b-a=x*/
    LL A=(w-x)/2,X=A*A-tmp,y,z;
    if(X<0)return ;
    res=0;
    for(int i=1;i<=n;++i)
    {
        y=X+a[i];
        z=sqrt(y);
        res+=(z*z==y);
    }
    //printf(" X:%lld res:%d\n",X,res);
    ans=max(ans,res);
}
inline void dfs(int x,int y)
{
    //printf(" dfs %d %d\n",x,y);
    if(y>Z/y)return ;
    if(x>t)return solve(y);
    for(int j=0;j<=num[x];++j)
    {
        dfs(x+1,y);
        y*=val[x];
    }
}
inline void calc(int x,int y)
{
    //printf("calc %d %d\n",x,y);
    Z=a[y]-a[x];
    int z=Z;
    tmp=a[x],t=0;
    for(int i=1;i<=p_t && p[i]*p[i]<=z;++i)if(!(z%p[i]))
    {
        val[++t]=p[i],num[t]=0;
        for(;!(z%p[i]);z/=p[i])++num[t];
    }
    //printf("t:%d\n",t);
    if(z>1)val[++t]=z,num[t]=1;
    //printf("t:%d\n",t);
    //for(int i=1;i<=t;++i)printf("(%d,%d)",val[i],num[i]);
    //puts("");
    dfs(1,1);
}
int main()
{
    init(),read(Test_num);
    while(Test_num--)
    {
        read(n),ans=1;
        for(int i=1;i<=n;++i)read(a[i]);
        for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)calc(i,j);
        printf("%d\n",ans);
    }
    return 0;
}

E. Rectangle Shrinking

题意：在一个 2×1092\times 10^9 的网格中，放置了 nn 个矩形。对于每个矩形，你可以删掉也可以用一个子矩形代替。要求最后不能有矩形重叠，且面积尽可能大。

做法一

一个简单的猜测为，最终面积即为面积并，考虑如何构造。我们采用在线添加的方式，每次添加一个新矩形时保持矩面积为矩形面积并且不重叠。矩形用三个 set 动态维护，分别表示跨两行、只第一行和只第二行。这样 set 内只需要存矩形的左右边界和标号。

考虑添加的矩形有哪些情况：如果有被新矩形覆盖的，直接删掉；如果新矩形被某个旧矩形覆盖，直接不考虑新矩形。否则，情况一定只有矩形交而不存在矩形覆盖。具体实现上，对新矩形的行数分类讨论：

假设新矩形为一行，先处理与一行矩形的冲突：新覆盖旧则删掉，旧覆盖新则跳过，出现相交则把新矩形缩短到不相交。结束后，如果新矩形被缩到没有了（l>rl>r），同样直接跳过。接下来处理与两行矩形的冲突：旧覆盖新同样跳过，但新不能完全覆盖旧（行数不够）。如果新在区间上覆盖了旧（即覆盖了旧的其中一行），则将旧的被覆盖的一行删掉，两行矩形改为一行矩形。如果新和旧只相交不包含，则将新矩形缩短到不相交即可。

假设新矩形为两行，先处理与两行矩形的冲突，与1-1冲突相同。接着处理与一行矩形的冲突：新覆盖旧则删掉，旧覆盖新的一整行时，将新矩形改为一行矩形，转到一行矩形处理方式。如果只相交不包含，则将旧的一行矩形缩短到不相交。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
struct node {
    mutable int l,r,num;
    bool operator<(const node &o) const {
        return r<o.r;
    }
};
struct vv {
    int u,l,d,r;
} ans[200010];
signed main() {
    int t;
    cin>>t;
    while(t--) {
        set<node> s[3];
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            ans[i]={0,0,0,0};
        for(int i=1;i<=n;i++) {
            int u,l,d,r;
            cin>>u>>l>>d>>r;
            if(u==d) {
                auto tmp=s[u].lower_bound({l,l,0});
                bool flag=1;
                while(tmp!=s[u].end()) {
                    if(tmp->l<=l&&tmp->r>=r) {
                        flag=0;
                        break;
                    }
                    if(tmp->l>=l&&tmp->r<=r)
                        tmp=s[u].erase(tmp);
                    else if(tmp->l>r) break;
                    else if(tmp->l<l) l=tmp->r+1,tmp++;
                    else if(tmp->r>r) r=tmp->l-1,tmp++;
                }
                if(l>r||flag==0) continue;
                auto tt=s[0].lower_bound({l,l,0});
                while(tt!=s[0].end()) {
                    if(tt->l<=l&&tt->r>=r) {
                        flag=0;
                        break;
                    }
                    if(tt->l>=l&&tt->r<=r) {
                        s[3-u].insert({tt->l,tt->r,tt->num});
                        tt=s[0].erase(tt);
                    }
                    else if(tt->l>r) break;
                    else if(tt->l<l) l=tt->r+1,tt++;
                    else if(tt->r>r) r=tt->l-1,tt++;
                }
                if(l>r||flag==0) continue;
                s[u].insert({l,r,i});
            }
            else {
                auto tmp=s[0].lower_bound({l,l,0});
                bool flag=1;
                while(tmp!=s[0].end()) {
                    if(tmp->l<=l&&tmp->r>=r) {
                        flag=0;
                        break;
                    }
                    if(tmp->l>=l&&tmp->r<=r)
                        tmp=s[0].erase(tmp);
                    else if(tmp->l>r) break;
                    else if(tmp->l<l) l=tmp->r+1,tmp++;
                    else if(tmp->r>r) r=tmp->l-1,tmp++;
                }
                if(l>r||flag==0) continue;
                for(int x=1;x<=2;x++) {
                    if(u==d) {
                        auto tt=s[u].lower_bound({l,l,0});
                        bool flg=1;
                        while(tt!=s[u].end()) {
                            if(tt->l<=l&&tt->r>=r) {
                                flg=0;
                                break;
                            }
                            if(tt->l>=l&&tt->r<=r)
                                tt=s[u].erase(tt);
                            else if(tt->l>r) break;
                            else if(tt->l<l) l=tt->r+1,tt++;
                            else if(tt->r>r) r=tt->l-1,tt++;
                        }
                        if(r<l||flg==0) flag=0;
                        continue;
                    }
                    auto tt=s[x].lower_bound({l,l,0});
                    while(tt!=s[x].end()) {
                        if(tt->l<=l&&tt->r>=r) {
                            u=d=3-x;
                            break;
                        }
                        if(tt->l>=l&&tt->r<=r)
                            tt=s[x].erase(tt);
                        else if(tt->l>r) break;
                        else if(tt->l<l) {
                            int ll=tt->l,rr=l-1,num=tt->num;
                            tt=s[x].erase(tt);
                            if(rr>=ll) {
                                s[x].insert({ll,rr,num});
                                tt=s[x].upper_bound({ll,rr,num});
                            }
                        }
                        else if(tt->r>r) {
                            tt->l=r+1;
                            if(tt->l>tt->r) tt=s[x].erase(tt);
                            else tt++;
                        }
                    }
                }
                if(l<=r&&flag) {
                    if(u==d) s[u].insert({l,r,i});
                    else s[0].insert({l,r,i});
                }
            }
        }
        int tot=0;
        for(auto [l,r,num]:s[0])
            ans[num]={1,l,2,r},tot+=(r-l+1)*2;
        for(auto [l,r,num]:s[1])
            ans[num]={1,l,1,r},tot+=r-l+1;
        for(auto [l,r,num]:s[2])
            ans[num]={2,l,2,r},tot+=r-l+1;
        cout<<tot<<endl;
        for(int i=1;i<=n;i++)
            cout<<ans[i].u<<" "<<ans[i].l<<" "<<ans[i].d<<" "<<ans[i].r<<endl;
    }
    return 0;
}

做法二

将矩形离线下来，按左端点排序，依次添加每个矩形，同时维护两行分别能到达的最右端点。由于添加一个矩形时，之前的矩形左端点都不超过当前矩形的左端点，所以只要最右端点超过当前矩形的右端点，则一定被包含。如果当前矩形的某一整行都被包含，则删掉该行，删空则跳过本矩形；如果当前矩形的左端点比两行最优端点的较小值还要小，则改为较小值 +1+1，这样，新矩形和原来的图形最多有一行重叠，将重叠的那一行的旧矩形缩短即可。

By KrK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> ii;

const int Maxn = 200005;

struct rec {
    int u, l, d, r;
};

int T;
int n;
rec R[Maxn];
int seq[Maxn];
ii reach[2];

bool Less(const int &a, const int &b)
{
    return R[a].l < R[b].l;
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d %d", &R[i].u, &R[i].l, &R[i].d, &R[i].r);
            R[i].u--; R[i].d--;
            seq[i] = i;
        }
        sort(seq, seq + n, Less);
        reach[0] = reach[1] = ii(0, -1);
        for (int z = 0; z < n; z++) {
            int ind = seq[z];
            int mn = min(reach[0].first, reach[1].first);
            R[ind].l = max(R[ind].l, mn + 1);
            if (R[ind].l > R[ind].r) continue;
            if (reach[R[ind].u].first >= R[ind].r)
                R[ind].u++;
            if (R[ind].u > R[ind].d) continue;
            if (reach[R[ind].d].first >= R[ind].r)
                R[ind].d--;
            if (R[ind].u > R[ind].d) continue;
            for (int h = R[ind].u; h <= R[ind].d; h++) {
                if (reach[h].first >= R[ind].l)
                    R[reach[h].second].r = R[ind].l - 1;
                reach[h] = ii(R[ind].r, ind);
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++)
            if (R[i].u > R[i].d || R[i].l > R[i].r) {
                R[i].u = R[i].d = -1;
                R[i].l = R[i].r = 0;
            } else res += (R[i].d - R[i].u + 1) * (R[i].r - R[i].l + 1);
        printf("%d\n", res);
        for (int z = 0; z < n; z++)
            printf("%d %d %d %d\n", R[z].u + 1, R[z].l, R[z].d + 1, R[z].r);
    }
    return 0;
}

做法三

我们发现，一行和一行的冲突非常容易计算，两行和两行的冲突和很容易算，复杂的是一行和两行的部分，有较多分类讨论。于是考虑将第三种转化为第一种。

首先同样将所有矩形分成三类，每一类内部可以很方便地处理到不重叠。然后将两行的矩形拆成第一行的一个矩形和第二行的一个矩形，重新处理新的第一行和新的第二行。由于之前每类内部都处理完了，新第一行和第二行的冲突全部为一行矩形和“原两行矩形”的冲突。如果一个包含了另一个，则直接将被包含的删掉：如果删掉的为原两行矩形，则等价于把两行矩形缩成一行矩形。否则则为相交且不包含，由于原两行矩形不方便缩短（需要考虑另一行），所以我们要求让原一行矩形缩短即可。

这种做法虽然在代码实现上较做法二稍长，但分类讨论极少，不容易写错。

By orzdevinwang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
using namespace std;
const int N = 1e6 + 7;
int n, u[N], d[N], l[N], r[N];
bool vis[N];
vector < int > S[3];
void solve(vi &a, int rp = -1) {
    sort(a.begin(), a.end(), [&] (int x, int y) {
        return r[x] == r[y] ? l[x] > l[y] : r[x] < r[y];
    });
    vi b;
    for(auto x : a) {
        while(sz(b) && l[b.back()] >= l[x]) {
            if(rp == -1) vis[b.back()] = false;
            else if(rp == 0) ++u[b.back()];
            else assert(rp == 1), --d[b.back()];
            b.pop_back();
        }
        if(sz(b) && r[b.back()] >= l[x]) {
            int y = b.back();
            int lenx = d[x] - u[x] + 1;
            int leny = d[y] - u[y] + 1;
            if(leny <= lenx) r[y] = l[x] - 1;
            else l[x] = r[y] + 1;
        }
        b.emplace_back(x);
    }
    a = b;
}
void Main() {
    cin >> n;
    S[0].clear();
    S[1].clear();
    S[2].clear();
    L(i, 1, n) {
        cin >> u[i] >> l[i] >> d[i] >> r[i];
        vis[i] = true;
        int op = -1;
        if(u[i] == 1 && d[i] == 1) op = 0;
        if(u[i] == 2 && d[i] == 2) op = 1;
        if(u[i] == 1 && d[i] == 2) op = 2;
        assert(op != -1);
        S[op].emplace_back(i);
    }
    L(i, 0, 2) solve(S[i]);
    for(auto u : S[2]) L(i, 0, 1) S[i].emplace_back(u);
    L(i, 0, 1) solve(S[i], i);

    int sumsz = 0;
    L(i, 1, n) if(vis[i]) {
        int siz = (d[i] - u[i] + 1) * (r[i] - l[i] + 1);
        if(siz < 0) {
            cout << "jingya\n";
            assert(false);
        }
        if(!siz) vis[i] = false;
        sumsz += siz;
    }
    cout << sumsz << '\n';
    L(i, 1, n)
        if(vis[i]) cout << u[i] << ' ' << l[i] << ' ' << d[i] << ' ' << r[i] << '\n';
        else cout << 0 << ' ' << 0 << ' ' << 0 << ' ' << 0 << '\n';
}
int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--) Main();
    return 0;
}

做法四

思路与做法三类似，但实现上更为巧妙。

考虑开两个 set 分别维护第一行的矩形和第二行的矩形。实现一个“插入矩形”函数，仅支持插入一个一行的矩形，且产生冲突时优先缩短新矩形而让旧矩形不变（包含则正常删除）。这可以用 set 很轻松地实现。

与做法三相同，在两行矩形与一行矩形产生冲突时，应优先更改一行矩形，对应在这里，则为先插入所有两行矩形再插入所有一行矩形。对于两行矩形，只需要将其拆成两个一行矩形插入，该插入函数自然会正确处理冲突。然后依次插入一行矩形即可。统计答案时要注意两行矩形如果有一行被包含、删除了，则改为一行矩形输出。

By yuto1115

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
template<class T>
class range_set {
    using iterator = typename set<tuple<T, T, int>>::iterator;

    set<tuple<T, T, int>> st;

    // return the least range which intersects with [x, inf)
    iterator least_intersecting_range(T x) {
        auto it = st.lower_bound({x, x, -1});
        if (it == st.begin() or ::get<1>(*prev(it)) <= x) return it;
        return prev(it);
    }

public:
    range_set() {}

    set<tuple<T, T, int>> get() { return st; }

    void insert(T l, T r, int id) {
        assert(l < r);
        auto it = least_intersecting_range(l);
        if (it != st.end() and ::get < 0 > (*it) < l) {
            auto [nl, nr, _] = *it;
            if (nr >= r) return;
            l = nr;
            ++it;
        }
        while (it != st.end() and ::get < 1 > (*it) <= r) {
            it = st.erase(it);
        }
        if (it != st.end() and ::get < 0 > (*it) < r) {
            auto [nl, nr, _] = *it;
            r = nl;
        }
        assert(l <= r);
        if (l == r) return;
        st.insert({l, r, id});
    }

    template<class U>
    friend ostream &operator<<(ostream &, const range_set<U> &);
};

template<class T>
ostream &operator<<(ostream &os, const range_set<T> &st) { return os << st.st; }

void solve() {
    INT(n);
    vi u(n), l(n), d(n), r(n);
    rep(i, n) scan(u[i], l[i], d[i], r[i]);
    vector<range_set<int>> st(2);
    rep(i, n) {
        if (u[i] == 1 and d[i] == 2) {
            st[0].insert(l[i], r[i] + 1, i);
        }
    }
    st[1] = st[0];
    rep(i, n) {
        if (u[i] == 1 and d[i] == 1) {
            st[0].insert(l[i], r[i] + 1, i);
        }
    }
    rep(i, n) {
        if (u[i] == 2 and d[i] == 2) {
            st[1].insert(l[i], r[i] + 1, i);
        }
    }
    vi nu(n, 3), nl(n), nd(n), nr(n);
    int ans = 0;
    for (auto [L, R, i]: st[0].get()) {
        chmin(nu[i], 1);
        chmax(nd[i], 1);
        ans += R - L;
        nl[i] = L;
        nr[i] = R - 1;
    }
    for (auto [L, R, i]: st[1].get()) {
        chmin(nu[i], 2);
        chmax(nd[i], 2);
        ans += R - L;
        nl[i] = L;
        nr[i] = R - 1;
    }
    print(ans);
    rep(i, n) {
        if (nu[i] == 3) nu[i] = 0;
        print(nu[i], nl[i], nd[i], nr[i]);
    }
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}