跳转至

CF 杂题

CF1456E XOR-ranges

定义函数 \(f(x)=\sum_{i=0}^{k-1}c_i\bigl([2^i]x\big)\)，其中 \(0\le x\le 2^k-1\)。你需要构造一个长度为 \(n\) 的序列 \(a_{1\sim n}\)，满足 \(\forall i\in[1,n],~l_i\le a_i\le r_i\)（\(l,r\) 是给定的序列），同时 \(\sum_{i=1}^{n-1}f(a_i\oplus a_{i+1})\) 最小。输出最小值。

\(n\le 50,~k\le 50\)

对于一个 \(a_i\in [l_i,r_i]\)，在高位 \(l_i\) 和 \(r_i\) 的 \(\operatorname{LCP}\) 部分，它每一位的取值都是固定的；直到某一位 \([2^x]l_i<[2^x]r_i\)，此时 \(a_i\) 可以选择跟随下界 \(l_i\) 或者上界 \(r_i\)；再直到某一位 \([2^x]l_i=0\) 或者 \([2^x]r_i=1\)，\(a_i\) 在这一位可以解除最后的限制，后面的位就可以任意取了。

因此每个 \(a_i\) 形如跟随 \(l_i\) 或 \(r_i\) 高位的一段前缀，然后某一位脱离了限制，后面任取。其中脱离限制的那一位不能违反另一个界的限制。考察任取的位会对答案造成什么样的影响，假设当前位置左右两个元素的这一位都是固定的，那么发现我们无论填 0/1，贡献只和 \([2^x](a_{i-1}\oplus a_{i+1})\) 有关：当相邻两个元素这一位不同时，产生 \(c_x\) 的代价，否则没有代价。进一步的，不难推广到数组上连续的一段 \([l,r]\) 都有同一位任取的情况：只要 \(i\) 和 \(i-1\) 填的 0/1 一样，就相当于 \(a_{l-1}\) 和 \(a_{r+1}\) 相邻时产生的代价。

        高位
*---*---*---*---*---*---*---*
*---*---*---*---*---^---*---*
*---*---^---*---*-------^---*
*---^-------*---*-----------^
*-----------*---^
*-----------^
^
        低位
^ 表示解除限制的那一位，横线表示代价源于横线连接的两个 bit 的异或。

因此计算过程中，一个固定位较长的元素会把另一侧固定位较短的元素“挡住”；两个固定位较长的元素就会把中间固定位较短的元素“挡住”。由于是最优化问题，因此考虑区间 dp，钦定两侧的元素挡住了中间的元素。如果直接钦定区间两端点分别解除限制的位数，状态数会爆炸，因此一位一位考虑。设 \(f_{x,i,j,0/1,0/1}\) 表示考虑了高于或等于 \(x\) 的位，\(i-1\) 和 \(j+1\) 还没有解除限制，\([i,j]\) 之间元素的元素都已经解除限制（刚刚解除也算），内部的代价最小是多少。

考虑转移，分讨 \([i,j]\) 中是否存在第 \(x\) 位解除限制的元素，若没有，则直接从 \(f_{x+1}\) 转移；否则将区间划分为若干段，段的边界处在第 \(x\) 位解除限制，段内在更高位解除限制。这可以用另一个数组 \(g\) 辅助转移。答案就是 \(\sum_x f_{x,0,n+1}\)，转移的时候 \(0\) 和 \(n+1\) 的贡献要特判一下。

代码 
  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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int N = 55;
const int INF = 0x003f3f3f3f3f3f3f;

int n, k;
int l[N], r[N], lcp[N], c[N];

int f[N][N][N][2][2];
int g[N][N][N][2][2];

inline void ckmin(int &a, int b) { a = min(a, b); }

inline int calc(int x, int i, int j, int p, int q) {
    if(!i || j == n + 1) return 0;
    int a, b;
    if(p == 0) a = (l[i] >> x) & 1;
    else a = (r[i] >> x) & 1;
    if(q == 0) b = (l[j] >> x) & 1;
    else b = (r[j] >> x) & 1;
    return c[x] * (a != b);
}

inline int calc1(int x, int i, int j, int p, int q) {
    if(!i || j == n + 1) return 0;
    int a, b;
    if(p == 0) a = (l[i] >> x) & 1;
    else a = (r[i] >> x) & 1;
    if(q == 0) {
        b = (l[j] >> x) & 1;
        if(b == 1 || x >= lcp[j]) return INF;
        b = 1;
    } else {
        b = (r[j] >> x) & 1;
        if(b == 0 || x >= lcp[j]) return INF;
        b = 0;
    }
    return c[x] * (a != b);
}

inline int calc2(int x, int i, int j, int p, int q) {
    if(!i || j == n + 1) return 0;
    int a, b;
    if(p == 0) {
        a = (l[i] >> x) & 1;
        if(a == 1 || x >= lcp[i]) return INF;
        a = 1;
    } else {
        a = (r[i] >> x) & 1;
        if(a == 0 || x >= lcp[i]) return INF;
        a = 0;
    }
    if(q == 0) b = (l[j] >> x) & 1;
    else b = (r[j] >> x) & 1;
    return c[x] * (a != b);
}

inline int calc3(int x, int i, int j, int p, int q) {
    if(!i || j == n + 1) return 0;
    int a, b;
    if(p == 0) {
        a = (l[i] >> x) & 1;
        if(a == 1 || x >= lcp[i]) return INF;
        a = 1;
    } else {
        a = (r[i] >> x) & 1;
        if(a == 0 || x >= lcp[i]) return INF;
        a = 0;
    }
    if(q == 0) {
        b = (l[j] >> x) & 1;
        if(b == 1 || x >= lcp[j]) return INF;
        b = 1;
    } else {
        b = (r[j] >> x) & 1;
        if(b == 0 || x >= lcp[j]) return INF;
        b = 0;
    }
    return c[x] * (a != b);
}

signed main() {

    cin >> n >> k; k += 2;
    for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    for(int i = 2; i < k; i++) cin >> c[i];
    for(int i = 1; i <= n; i++) l[i] = l[i] * 4, r[i] = r[i] * 4 + 3;

    for(int i = 1; i <= n; i++) lcp[i] = __lg(l[i] ^ r[i]);

    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));

    for(int i = 0; i <= n; i++) {
        f[k][i][i + 1][0][0] = 0;
        f[k][i][i + 1][0][1] = 0;
        f[k][i][i + 1][1][0] = 0;
        f[k][i][i + 1][1][1] = 0;
        g[k][i][i + 1][0][0] = 0;
        g[k][i][i + 1][0][1] = 0;
        g[k][i][i + 1][1][0] = 0;
        g[k][i][i + 1][1][1] = 0;
    }

    for(int x = k - 1; x >= 0; x--) {
        for(int len = 2; len <= n + 2; len++) {
            for(int i = 0; i + len - 1 <= n + 1; i++) {
                int j = i + len - 1;
                f[x][i][j][0][0] = f[x + 1][i][j][0][0] + calc(x, i, j, 0, 0);
                f[x][i][j][0][1] = f[x + 1][i][j][0][1] + calc(x, i, j, 0, 1);
                f[x][i][j][1][0] = f[x + 1][i][j][1][0] + calc(x, i, j, 1, 0);
                f[x][i][j][1][1] = f[x + 1][i][j][1][1] + calc(x, i, j, 1, 1);
                g[x][i][j][0][0] = f[x + 1][i][j][0][0] + calc1(x, i, j, 0, 0);
                g[x][i][j][0][1] = f[x + 1][i][j][0][1] + calc1(x, i, j, 0, 1);
                g[x][i][j][1][0] = f[x + 1][i][j][1][0] + calc1(x, i, j, 1, 0);
                g[x][i][j][1][1] = f[x + 1][i][j][1][1] + calc1(x, i, j, 1, 1);
                for(int t = i + 1; t <= j - 1; t++) {
                    ckmin(f[x][i][j][0][0], g[x][i][t][0][0] + f[x + 1][t][j][0][0] + calc2(x, t, j, 0, 0));
                    ckmin(f[x][i][j][0][0], g[x][i][t][0][1] + f[x + 1][t][j][1][0] + calc2(x, t, j, 1, 0));
                    ckmin(f[x][i][j][0][1], g[x][i][t][0][0] + f[x + 1][t][j][0][1] + calc2(x, t, j, 0, 1));
                    ckmin(f[x][i][j][0][1], g[x][i][t][0][1] + f[x + 1][t][j][1][1] + calc2(x, t, j, 1, 1));
                    ckmin(f[x][i][j][1][0], g[x][i][t][1][0] + f[x + 1][t][j][0][0] + calc2(x, t, j, 0, 0));
                    ckmin(f[x][i][j][1][0], g[x][i][t][1][1] + f[x + 1][t][j][1][0] + calc2(x, t, j, 1, 0));
                    ckmin(f[x][i][j][1][1], g[x][i][t][1][0] + f[x + 1][t][j][0][1] + calc2(x, t, j, 0, 1));
                    ckmin(f[x][i][j][1][1], g[x][i][t][1][1] + f[x + 1][t][j][1][1] + calc2(x, t, j, 1, 1));

                    ckmin(g[x][i][j][0][0], g[x][i][t][0][0] + f[x + 1][t][j][0][0] + calc3(x, t, j, 0, 0));
                    ckmin(g[x][i][j][0][0], g[x][i][t][0][1] + f[x + 1][t][j][1][0] + calc3(x, t, j, 1, 0));
                    ckmin(g[x][i][j][0][1], g[x][i][t][0][0] + f[x + 1][t][j][0][1] + calc3(x, t, j, 0, 1));
                    ckmin(g[x][i][j][0][1], g[x][i][t][0][1] + f[x + 1][t][j][1][1] + calc3(x, t, j, 1, 1));
                    ckmin(g[x][i][j][1][0], g[x][i][t][1][0] + f[x + 1][t][j][0][0] + calc3(x, t, j, 0, 0));
                    ckmin(g[x][i][j][1][0], g[x][i][t][1][1] + f[x + 1][t][j][1][0] + calc3(x, t, j, 1, 0));
                    ckmin(g[x][i][j][1][1], g[x][i][t][1][0] + f[x + 1][t][j][0][1] + calc3(x, t, j, 0, 1));
                    ckmin(g[x][i][j][1][1], g[x][i][t][1][1] + f[x + 1][t][j][1][1] + calc3(x, t, j, 1, 1));
                }
            }
        }
    }

    int ans = INF;
    for(int x = k - 1; x >= 0; x--) {
        ans = min(ans, f[x][0][n + 1][0][0]);
    }

    cout << ans << '\n';

    return 0;
}

CF468D Tree

给定一棵大小为 \(n\) 的无根树，你需要构造一个长度为 \(n\) 的 \(1\sim n\) 的排列 \(p\)，使 \(\sum_{i=1}^{n}dis(i,p_i)\) 最大。并给出字典序最小的构造方案。

\(n\le 10^5\)

首先我们任意钦定一个根节点 \(rt\)，记节点 \(i\) 到根的距离为 \(d(i)\)，那么上式可以表示为 \(\sum_{i=1}^{n}2d(i)-\sum_{i=1}^{n}d(\operatorname{lca}(i,p_i))\)。并且不难说明这个式子的最小值不随根节点而改变。在固定一个根节点之后，式子的第一项不变，第二项有最大值 \(0\)，由此推出答案不能超过 \(\sum_{i=1}^{n}2d(i)\) 的最小值。

\(\sum_{i=1}^{n}2d(i)\) 在 \(rt\) 是重心时取最小值，此时尝试将第二项构造为 \(0\)。问题转化为：给定若干组元素，你需要将元素配对，使得每一对的两个元素都不在同一组中（配对是单向的）。

结论：上面这个问题，在每组元素数量不存在绝对众数时有解；

如果存在绝对众数，那么显然无解。否则，找到最大的两个组，各取一个元素进行匹配（双向匹配），仍然满足条件。发现当 \(rt\) 是重心时，各子树大小显然都不超过 \(\lceil\frac{n}{2}\rceil\)，因此不存在绝对众数，因而一定有解，答案可以取到上界 \(\sum_{i=1}^{n}d(i)\)。

那么如何构造使得字典序最小呢？考虑贪心处理，问题转化为判定一次单向匹配之后是否仍然有解。而这里产生的子问题是上面问题的强化版，可以刻画为一个二分图匹配问题：左部点和右部点各分为 \(k\) 组，当两个点 \(i,j\) 所在组的编号不同时，二者之间连一条边。那么根据霍尔定理，局面有解当且仅当对任意 \(i\in[1,k]\)，左右两边的第 \(i\) 组大小之和不超过节点数 \(n\)（二分图点数的一半）。

因此每次匹配先检查是否有一组节点数之和达到了 \(n\)，若是则强制匹配到这一组；否则找到全局最小值进行匹配。这里可以用堆维护全局抠掉一个点之后的答案。注意 \(rt\) 可以和自己进行匹配，这里注意特判。

代码 
  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
132
133
134
135
#include<iostream>
#include<queue>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, w, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, rt;
int dfn[N], id[N], dt;
int mxp[N], szt[N], anc[N];
int son[N], nn;
ll d[N], sum;

void dfs1(int u, int fa) {
    szt[u] = 1;
    dfn[u] = ++dt;
    id[dt] = u;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs1(v, u);
        szt[u] += szt[v];
        mxp[u] = max(mxp[u], szt[v]);
    }
    mxp[u] = max(mxp[u], n - szt[u]);
    if(mxp[u] < mxp[rt]) rt = u;
}

void dfs2(int u, int fa) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa) continue;
        d[v] = d[u] + w;
        if(!anc[u]) { son[++nn] = v; anc[v] = nn; }
        else anc[v] = anc[u];
        dfs2(v, u);
    }
}

template<typename _Tp>
struct myHeap {
    priority_queue<_Tp, vector<_Tp>, greater<_Tp> > que, del;
    inline void push(_Tp x) { que.push(x); }
    inline void erase(_Tp x) { del.push(x); }
    inline _Tp top() {
        while(!del.empty() && que.top() == del.top()) { que.pop(), del.pop(); }
        return que.top();
    }
    inline bool empty() { return que.size() == del.size(); }
    inline _Tp top(int eid) {
        if(eid == nn || top().id != eid) return top();
        _Tp tmp = top();
        que.pop();
        _Tp res = top();
        que.push(tmp);
        return res;
    }
};

struct Node1 {
    int id, mn;
    inline bool operator>(const Node1 &b) const { if(mn != b.mn) return mn > b.mn; return id > b.id; }
    inline bool operator==(const Node1 &b) const { return mn == b.mn && id == b.id; }
};

struct Node2 {
    int id, sz;
    inline bool operator>(const Node2 &b) const { if(sz != b.sz) return sz < b.sz; return id > b.id; }
    inline bool operator==(const Node2 &b) const { return sz == b.sz && id == b.id; }
};

priority_queue<int, vector<int>, greater<int> > pt[N];
myHeap<Node1> mn;
myHeap<Node2> sz;
int cs[N];

int ans[N];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    mxp[0] = INF;
    dfs1(1, 0);
    dfs2(rt, 0);

    for(int i = 1; i <= n; i++) sum += 2 * d[i];
    cout << sum << '\n';

    anc[rt] = ++nn;
    for(int i = 1; i <= n; i++) pt[anc[i]].push(i);
    for(int i = 1; i <= nn; i++) {
        mn.push({i, pt[i].top()});
        sz.push({i, cs[i] = pt[i].size() * 2});
    }

    for(int i = 1; i <= n; i++) {
        int p1 = anc[i], p2, j;
        sz.erase({p1, cs[p1]}); 
        sz.push({p1, --cs[p1]}); 
        if(sz.top().sz == n - i + 1 && sz.top().id != nn) p2 = sz.top().id;
        else p2 = mn.top(p1).id;
        j = pt[p2].top();
        ans[i] = j;
        mn.erase({p2, j});
        sz.erase({p2, cs[p2]});
        pt[p2].pop();
        if(!pt[p2].empty()) mn.push({p2, pt[p2].top()});
        sz.push({p2, --cs[p2]});
    }

    for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}

CF1977E Tensor

这是一道交互题。有一个包含 \(n\) 个节点的 DAG，保证：

  • 所有边都是从编号大的点连向编号小的点；
  • 图的最小链覆盖不超过 \(2\)；

你初始只知道图的点数 \(n\)。你需要向交互器提出不超过 \(2n\) 个询问，每次你可以询问图上 \(i,j\) 两个点，交互器会告诉你 \(j\) 能否到达 \(i\)。然后，你需要给出图的一种黑白染色方案，满足：颜色相同的点分布在同一条链上。

显然 DAG 形如两条链中间任意连了一些边。我开始 naive 了，以为只询问 \((i,i+1)\) 然后二分图染色就行。其实中间的边完全可以扰乱这个过程，使得你染出来的某一侧不能形成链。

考虑扫描 \(1\sim n\) 的点然后动态维护两条链的前缀。考虑加入一个新的点 \(i+1\)。如果加入的点始终只向其中一条链的链尾有连边，那么显然是容易的（上面那个算法也能过）。因为此时你可以保证两条链的链尾之间没有连边；根据题目限制，新加的点一定向两个链尾连至少一条边。

考虑如何处理同时向两个链尾连边的情况。发现如果不考虑后面的点是没法判断当前点应该加到哪条链后面的（第一种算法就假在这里）。因此考虑开第三条链维护这些不确定的点。

此时，再新加一个点，如果它向第三条链的链尾有连边，那么它的情况等价于同时向两个链尾连边，因此追加到第三条链末尾。否则，无论如何它不能合并到第三条链末尾，因此将它追加到原来的两条链之一，然后将第三条链直接拼接在另一条链后面。发现此时仍然满足两条链的末尾之间没有边相连。

发现可以将加入一个点的询问次数压缩在 \(2\) 次以内。

代码 
 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
#include<iostream>
using namespace std;
const int N = 110;

int T, n;
int ans[N];

int s2[N];
int t0, t1, t2;

bool query(int i, int j) {
    cout << "? " << i << ' ' << j << endl;
    cout.flush();
    string tmp;
    cin >> tmp;
    return tmp == "YES";
}

int main() {

    cin >> T;
    while(T--) {
        cin >> n;
        t0 = t1 = t2 = 0;
        t0 = 1;
        ans[1] = 0;
        for(int i = 2; i <= n; i++) {
            if(t2 && query(s2[t2], i)) s2[++t2] = i;
            else if(t0 && query(t0, i)) {
                if(!t2 && t1 && query(t1, i)) {
                    s2[++t2] = i;
                    continue;
                }
                t0 = i;
                ans[i] = 0;
                if(t2) t1 = s2[t2];
                while(t2) ans[s2[t2--]] = 1;
            } else {
                t1 = i;
                ans[i] = 1;
                if(t2) t0 = s2[t2];
                while(t2) ans[s2[t2--]] = 0;
            }
        }
        while(t2) { ans[s2[t2--]] = 0; }
        cout << "! ";
        for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
        cout << endl;
        cout.flush();
    }

    return 0;
}

CF1834E MEX of LCM

给定一个长为 \(n\) 的序列 \(a_{1\sim n}\)，求 \(\operatorname{mex}\bigl(\{\operatorname{lcm}_{i=l}^{r}a_i\mid 1\le l\le r\le n\}\big)\)。

\(n\le 3\times 10^5\)

注意到固定右端点之后，区间 \(\operatorname{lcm}\) 只有本质不同的 \(\log V\) 个，因此集合大小不超过 \(n\log V\)。考虑如何求出这个集合。

考虑动态维护每个前缀的后缀 \(\operatorname{lcm}\) 集合。发现在加入一个数字之后，只需把原先集合中的数字都和当前数字取 \(\operatorname{lcm}\)，再把太大的部分砍掉，时间复杂度就是对的。用 set 维护即可。

代码 
 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
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int N = 3e5 + 10;
const int LIM = 1e7;

int T, n;
int a[N];

set<int> ans, tmp;
long long sta[N], top;

inline long long lcm(int a, int b) {
    return (long long)a / __gcd(a, b) * b;
}

int main() {

    cin >> T;
    while(T--) {
        cin >> n;
        ans.clear(); tmp.clear();
        for(int i = 1; i <= n; i++) cin >> a[i];
        tmp.insert(a[1]); ans.insert(a[1]);
        for(int i = 2; i <= n; i++) {
            for(int j : tmp) sta[++top] = lcm(j, a[i]);
            tmp.clear();
            while(top) {
                if(sta[top] <= LIM) { tmp.insert(sta[top]); ans.insert(sta[top]); }
                --top;
            }
            tmp.insert(a[i]); ans.insert(a[i]);
        }
        for(int i = 1; i <= LIM; i++) {
            if(!ans.count(i)) { cout << i << '\n'; break; }
        }
    }

    return 0;
}

CF1935E Distance Learning Courses in MAC

给定一个长为 \(n\) 的有序二元组序列 \((l_i,r_i),~(i\in [1,n],~l_i\le r_i)\)。考虑一个序列 \(a_{1\sim n}\) 满足 \(a_i\in [l_i,r_i]\)。现在有 \(q\) 次询问，每次询问给定 \([x,y]\)，询问 \(\operatorname{OR}_{i=x}^{y}a_i\)（按位或）的最大值。

\(n,q\le 2\times 10^5\)

考察 \(a_i\) 和 \(r_i\) 的最长公共前缀，记其长度为 \(k\)。如果 \(a_i\) 从高往低数的第 \(k+1\) 位为 \(0\)，\(r_i\) 从高往低数的第 \(k+1\) 位是 \(1\)，那么从第 \(k+2\) 位往后就都可以取 \(1\) 了。

因此预处理 \(f_{i,j,k}\) 表示区间 \([i,j]\) 中 \(r_i\) 的第 \(k\) 位有多少个 \(1\)；\(g_{i,j,k}\) 表示区间 \([i,j]\) 中 \(r_i\) 的第 \(k\) 位有多少个 \(1\) 能变成 \(0\)（也就是在 \(l_i,r_i\) 的公共前缀后面并且值为 \(1\)，变成 \(0\) 之后可以把后面全填上 \(1\)）。对于每次询问，我们从高位往低位处理，考虑第 \(k\) 位，

  • 若 \(f_k=0\)，那么该位只可能是 \(0\)；
  • 若 \(f_k>0\)，那么必须优先保证当前位为 \(1\)，再去考虑后面的位；
    • 若 \(f_k\ge 2\wedge g_k\ge 1\)，那么选择一个 \(1\) 变成 \(0\)，后面的位都填 \(1\) 就行了，结束贪心；

\(f\) 和 \(g\) 容易在 \(O(n\log V)\) 的时间内预处理出来。因此总时间复杂度为 \(O\big((n+q)\log V\big)\)。

代码 
 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
#include<iostream>
using namespace std;
const int N = 2e5 + 10;

inline int lg(int x) {
    int res = -1;
    while(x) { ++res; x >>= 1; }
    return res;
}

int T, n, q;
int a[N], b[N];

int f[N][30], g[N][30];

void clear() {
    for(int i = 0; i <= n + 5; i++) {
        for(int j = 0; j < 30; j++) f[i][j] = g[i][j] = 0;
    }
}

int main() {

    cin >> T;
    while(T--) {
        cin >> n;
        clear();
        for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
        for(int i = 1; i <= n; i++) {
            int tmp = lg(a[i] ^ b[i]);
            for(int j = 0; j < 30; j++) {
                f[i][j] = f[i - 1][j] + ((b[i] >> j) & 1);
                g[i][j] = g[i - 1][j] + (((b[i] >> j) & 1) && (j <= tmp));
            }
        }
        cin >> q;
        while(q--) {
            int l, r, ans = 0;
            cin >> l >> r;
            for(int i = 29; i >= 0; i--) {
                if(f[r][i] - f[l - 1][i] == 0) continue;
                ans |= (1 << i);
                if(f[r][i] - f[l - 1][i] == 1) continue;
                if(g[r][i] - g[l - 1][i]) { ans += (1 << i) - 1; break; }
            }
            cout << ans << ' ';
        }
        cout << '\n';
    }

    return 0;
}