Introduction

This is Problem E from AtCoder Beginner Contest 457. I did not finish implementing it during the contest. When reviewing it afterward, I realized that the bottleneck was more than knowing how to use a Fenwick tree: first, I needed to break the condition “the two pieces of cloth cover exactly the query interval” into structures that could be tested.

Initially, I mainly thought about joining intervals from the left and right endpoints, but I had not clearly handled the case of combining the full interval [S,T] with an interval contained in it. After the review, I split all valid arrangements into two cases and handled them with endpoint groups plus binary search and an offline Fenwick tree, respectively. The overall logic became much clearer.

This article records the complete derivation, from modeling the statement and identifying the structural cases to implementing the final data structures.

Modeling the Problem

We are given $N$ cells arranged in a horizontal row and $M$ pieces of cloth. Piece $i$ covers a closed interval:

There are then $Q$ queries, each specifying a target interval:

We need to determine whether we can choose exactly two pieces of cloth from the $M$ pieces so that:

• Every cell from $S$ to $T$ is covered by at least one piece;
• No cell outside $[S,T]$ is covered;
• Exactly two pieces must be chosen; choosing only one is not allowed.

Viewing each piece of cloth as an interval gives the equivalent question:

Are there two intervals belonging to different pieces of cloth whose union is exactly $[S,T]$?

In other words, do two pieces of cloth $A$ and $B$ exist such that:

This reformulation makes several necessary conditions clear:

• Neither piece may extend beyond $[S,T]$;
• The left endpoint $S$ must be covered;
• The right endpoint $T$ must be covered;
• The two pieces must be distinct pieces of cloth.

All the tests that follow revolve around these conditions.

Starting from the Endpoint Constraints

If the union of two intervals is exactly $[S,T]$, the left endpoint $S$ must be covered.

Nothing to the left of $S$ may be covered, so the piece covering $S$ must start at $S$. It has the form:

Similarly, the right endpoint $T$ must be covered. Since nothing to the right of $T$ may be covered, the piece covering $T$ must end at $T$. It has the form:

For there to be no gap between these two pieces, we need:

A natural test is therefore:

• Find a piece starting at $S$ whose right endpoint is as far right as possible;
• Find a piece ending at $T$ whose left endpoint is as far left as possible;
• Check whether they continuously cover the whole interval $[S,T]$.

There is one detail, though: we cannot simply allow the full interval $[S,T]$ to serve as both the left piece and the right piece.

A piece exactly equal to $[S,T]$ both starts at $S$ and ends at $T$. But the problem requires exactly two distinct pieces, so we cannot use that same piece twice.

For the ordinary left-and-right joining test, we can therefore add the requirements:

The left piece must not reach $T$ on its own, and the right piece must not start at $S$. This naturally excludes the invalid case of reusing the same full interval.

Classifying the Valid Structures

The endpoint analysis above divides all valid arrangements for a query $[S,T]$ into two cases.

Joining a Left Interval and a Right Interval

There are two pieces:

and:

satisfying:

Here, $x<T$ and $y>S$ exclude using the full interval $[S,T]$ twice as if it were two pieces. The final condition, $x+1\ge y$, guarantees that the pieces leave no gap and cover the entire target interval.

A Full Interval Plus a Contained Interval

In the other case, one piece is already the full interval:

Once such a piece exists, the other piece only needs to lie entirely within $[S,T]$. That is, the other interval $[L_i,R_i]$ only needs to satisfy:

We then necessarily have:

Since the problem requires two distinct pieces, there must be at least $2$ pieces entirely contained in $[S,T]$.

This $2$ includes the full interval $[S,T]$ itself. In other words, if $[S,T]$ exists and the number of contained intervals is greater than $1$, there is another piece we can choose together with the full interval.

Queries for Joining the Left and Right Intervals

To test the first structure quickly, precompute two arrays grouped by endpoint:

1

vector<int> L[maxn], R[maxn];

Here:

• L[x] stores the right endpoints of all pieces with left endpoint x;
• R[x] stores the left endpoints of all pieces with right endpoint x.

When reading a piece $[l,r]$:

1
2

L[l].push_back(r);
R[r].push_back(l);

Then sort each L[i] and R[i].

For a query $[S,T]$, joining the left and right intervals requires finding:

• The largest right endpoint $x$ in L[S] that is strictly less than $T$;
• The smallest left endpoint $y$ in R[T] that is strictly greater than $S$.

For the former, use:

1

auto it_r = lower_bound(L[S].begin(), L[S].end(), T);

lower_bound returns the first position greater than or equal to $T$. Moving back one position therefore gives the largest right endpoint strictly less than $T$.

For the latter, use:

1

auto it_l = upper_bound(R[T].begin(), R[T].end(), S);

upper_bound returns the first position greater than $S$, which is the smallest left endpoint $y$ we need.

If both exist and satisfy:

the intervals can be joined.

The corresponding function is:

1
2
3
4
5
6
7
8
9
10
11
12

bool Joint(int l, int r) {
    if (L[l].empty() || R[r].empty()) {
        return false;
    }
    auto it_r = lower_bound(L[l].begin(), L[l].end(), r);
    auto it_l = upper_bound(R[r].begin(), R[r].end(), l);
    if (it_r == L[l].begin() || it_l == R[r].end()) {
        return false;
    }
    --it_r;
    return *it_r + 1 >= *it_l;
}

This part tests only the first structure: two intervals, neither equal to the whole target, joining from the left and right ends.

Queries for the Full and Contained Intervals

The second structure requires checking two things together:

1. Whether the full interval $[S,T]$ exists;
2. Whether at least two pieces are entirely contained in $[S,T]$.

First, handle the first check.

When reading each piece, encode its interval $[L,R]$ as a long long and place it in a set:

1
2
3

ll Key(int l, int r) {
    return 1ll * l * maxn + r;
}

In this problem, $L,R\le 2\times 10^5$, and maxn is greater than every possible right endpoint, so this encoding uniquely represents an interval.

On input:

1

exact_LR.insert(Key(l, r));

For a query:

1

exact_LR.count(Key(S, T))

This determines whether a piece exactly equal to $[S,T]$ exists.

Next, handle the second check: count the pieces entirely contained in $[S,T]$.

For a query $[S,T]$, we need the number of pieces satisfying:

and:

This is a two-dimensional dominance-counting problem. Enumerating all pieces for each query would take $O(MQ)$, which clearly cannot pass.

Consider processing the queries offline.

Sort all queries by $S$ in descending order. When processing the current query $[S,T]$, add to the Fenwick tree every piece that has not yet been added and whose left endpoint satisfies:

To add a piece $[L_i,R_i]$, increment position $R_i$ in the Fenwick tree:

1

bit.add(R_i);

The Fenwick tree then maintains:

The distribution of right endpoints among all pieces whose left endpoints already satisfy $L_i\ge S$.

At this point, querying:

1

bit.query(T)

returns the number of pieces already added that satisfy:

Since adding these pieces already guaranteed:

bit.query(T) counts exactly the pieces satisfying:

That is precisely the number of pieces entirely contained in $[S,T]$.

The corresponding sweep is:

1
2
3
4
5
6
7
8
9
10
11
12
13

Fenwick bit(n);
int cur_L = n;

for (Query qy : Q) {
    while (cur_L >= qy.l) {
        for (int r : L[cur_L]) {
            bit.add(r);
        }
        cur_L--;
    }

    // 此时 bit.query(qy.r) 就是 insideCount(qy.l, qy.r)
}

The comment in the sweep says that bit.query(qy.r) now equals insideCount(qy.l, qy.r).

The test for the second structure is therefore:

1

exact_LR.count(Key(l, r)) && bit.query(r) > 1

Here, bit.query(r) > 1 means that at least two pieces are entirely contained in $[l,r]$. The full interval $[l,r]$ itself already counts as one, so a count greater than $1$ guarantees another distinct contained piece.

The Final Decision

Combining the two structures, for each query $[S,T]$ we only need to check:

1
2
3
4
5

if (Joint(S, T) || Exact(S, T)) {
    ans = true;
} else {
    ans = false;
}

Here:

• Joint(S,T) tests whether a left-and-right joining arrangement exists;
• Exact(S,T) tests whether the full interval $[S,T]$ exists and the number of contained intervals is greater than $1$.

The Exact function is implemented as:

1
2
3
4
5
6

bool Exact(int l, int r, const Fenwick &bit) {
    if (!exact_LR.count(Key(l, r))) {
        return false;
    }
    return bit.query(r) > 1;
}

The complete processing procedure is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void Solve() {
    Fenwick bit(n);
    int cur_L = n;

    for (Query qy : Q) {
        while (cur_L >= qy.l) {
            for (int r : L[cur_L]) {
                bit.add(r);
            }
            cur_L--;
        }

        if (Joint(qy.l, qy.r) || Exact(qy.l, qy.r, bit)) {
            ans[qy.id] = true;
        }
    }
}

Since we reordered the queries, we must retain each query’s original id and finally output the answers in their original order.

Complexity Analysis

Preprocessing L and R requires sorting the arrays within each endpoint group.

The total number of elements across the arrays is $M$, so the total sorting complexity can be viewed as:

For each query, the joining test performs two binary searches, taking:

For all queries:

In the offline Fenwick-tree part, each piece is added once and each query is answered once, giving:

The total time complexity is therefore:

We store all intervals, all queries, the endpoint groups, the Fenwick tree, and the answer array, so the space complexity is:

The constraints are:

This is sufficient to pass.

Submission Record and Accepted Code

The submission record is shown below.

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

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

constexpr ll maxn = 2e5 + 5;

struct Query {
    int l, r, id;
};

struct Fenwick {
    int n;
    vector<int> c;

    Fenwick(int _n) : n(_n), c(n + 1, 0) {
    }

    static int lowbit(int x) {
        return x & -x;
    }

    void add(int x) {
        for (int i = x; i <= n; i += lowbit(i)) {
            c[i]++;
        }
    }

    [[nodiscard]] int query(int x) const {
        int sum = 0;
        for (int i = x; i; i -= lowbit(i)) {
            sum += c[i];
        }
        return sum;
    }
};

int n, m, q;
bool ans[maxn];
vector<int> L[maxn], R[maxn];
vector<Query> Q;
unordered_set<ll> exact_LR;

void init() {
    for (int i = 1; i <= n; i++) {
        if (!L[i].empty()) {
            sort(L[i].begin(), L[i].end());
        }
        if (!R[i].empty()) {
            sort(R[i].begin(), R[i].end());
        }
    }
    sort(Q.begin(), Q.end(), [](const Query &a, const Query &b) {
        return a.l > b.l;
    });
}

ll Key(int l, int r) {
    return 1ll * l * maxn + r;
}

bool Joint(int l, int r) {
    if (L[l].empty() || R[r].empty()) {
        return false;
    }
    auto it_r = lower_bound(L[l].begin(), L[l].end(), r);
    auto it_l = upper_bound(R[r].begin(), R[r].end(), l);
    if (it_r == L[l].begin() || it_l == R[r].end()) {
        return false;
    }
    --it_r;
    return *it_r + 1 >= *it_l;
}

bool Exact(int l, int r, const Fenwick &bit) {
    if (!exact_LR.count(Key(l, r))) {
        return false;
    }
    return bit.query(r) > 1;
}

void Solve() {
    Fenwick bit(n);
    int cur_L = n;
    for (Query qy: Q) {
        while (cur_L >= qy.l) {
            for (int r: L[cur_L]) {
                bit.add(r);
            }
            cur_L--;
        }
        if (Joint(qy.l, qy.r) || Exact(qy.l, qy.r, bit)) {
            ans[qy.id] = true;
        }
    }
}

void printANS() {
    for (int i = 1; i <= q; i++) {
        cout << (ans[i] ? "Yes\n" : "No\n");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        L[l].push_back(r);
        R[r].push_back(l);
        exact_LR.insert(Key(l, r));
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int s, t;
        cin >> s >> t;
        Q.push_back({s, t, i});
    }
    init();
    Solve();
    printANS();
    return 0;
}

Closing Thoughts

The key to this problem is to separate the valid coverage structures clearly before reaching for a Fenwick-tree template.

“The union of two pieces is exactly $[S,T]$” splits into:

• Joining a left interval and a right interval;
• Combining a full interval with a contained interval.

The former uses endpoint groups and binary search. The latter becomes a two-dimensional dominance count with conditions:

which an offline Fenwick tree can answer.

The lesson I take from interval problems like this is to identify the structure first, then choose the data structure. Once the valid arrangements are separated clearly enough, the binary searches, Fenwick tree, and offline processing all follow much more naturally.