https://codeforces.com/gym/103055

F. Fair Distribution

 

题意：给定 n,mn,m，nn 只能减少，mm 只能增加，问要使得 mm 是 nn 的倍数，两者变化量的绝对值之和最小是多少？1≤n,m≤1081 \le n, m \le 10^8

整除分块

暴力的做法是枚举 nn，再计算 mm 的最少改变量。这其中会有很多无效的枚举。

对于 ⌊mx⌋\lfloor\frac{m}{x}\rfloor 相同的这一段 xx，这一段的最小值或最大值处一定存在这一段的最优解（虽然其它位置可能也有）。所以其实整除分块后，每一块只需要计算两个端点处即可。

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 <bits/stdc++.h>

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 5005;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

int T;
int n, m;

int cal(int x, int y) {
    if (y % x == 0)return 0;
    else return x - y % x;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        if (n >= m) {
            printf("%d\n", n - m);
            continue;
        }
        int ans = INF;
        for (int l = 1, r; l <= n; l = r + 1) {
            r = min(n, m / (m / l));
            ans = min(ans, n - l + cal(l, m));
            ans = min(ans, n - r + cal(r, m));
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

D. Shortest Path Query

 

题意：给定一张带边权无向图，且保证对于每条边 (u,v,w)(u,v,w)，uu 的二进制表示一定是 vv 的二进制表示的前缀。多次询问，每次给定 s,ts,t，问两点的最短路径长度。

最短路+Trie

建字典树，每点只会与祖先连边。

枚举每个点，只保留两端点都在它的子树中的边。求单源最短路。

查询时，遍历 s,ts,t 的所有公共祖先，计算 ss 到这个公共祖先的距离 + tt 到这个公共祖先的距离，取最小值。

在枚举节点求最短路时，虽然子树中的点可能连到这个子树外，但是只需要两端点都在子树中的边求最短路，因为最终查询时是要枚举所有祖先的，必定存在某一个祖先处，需要的所有边都在它的子树内。

由于一条边只会被保留 O(log⁡n)\mathcal{O}(\log n) 次，所以求最短路的总复杂度为 O(mlog⁡2n)\mathcal{O}(m\log^2n)。

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
#include <bits/stdc++.h>

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int n, m, q;
ll d[N][20];
int len[N];
int ss[N], tt[N];
struct E {
    int v;
    ll w;
};
vector<E> G[N];

int f(int x, int p[]) {
    int n = 0;
    while (x) {
        p[n++] = x % 2;
        x >>= 1;
    }
    reverse(p, p + n);
    return n;
}

void bfs(int s) {
    priority_queue<pli, vector<pli>, greater<pli> > q;
    d[s][0] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().second;
        ll di = q.top().first;
        q.pop();
        if (di > d[u][len[u] - len[s]])continue;
        for (E &e:G[u]) {
            int v = e.v;
            ll w = e.w;
            if (v > s && d[v][len[v] - len[s]] > di + w) {
                d[v][len[v] - len[s]] = di + w;
                q.push({di + w, v});
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)len[i] = f(i, ss);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; i++)bfs(i);
    scanf("%d", &q);
    while (q--) {
        int s, t;
        scanf("%d%d", &s, &t);
        f(s, ss);
        f(t, tt);
        int j = 0;
        ll ans = inf;
        while (ss[j] == tt[j] && j < min(len[s], len[t])) {
            ans = min(ans, d[s][len[s] - j - 1] + d[t][len[t] - j - 1]);
            j++;
        }
        if (ans == inf)puts("-1");
        else printf("%lld\n", ans);
    }
    return 0;
}

 

B. Restore Atlantis

 

题意：给定 nn 个矩形，qq 次询问，每次s定 l,rl,r，问编号在 [1,l)∪(r,n][1,l)\cup(r,n] 的矩形的并的面积。1≤n,q≤100 000,0≤xai<xbi≤2 000,0≤yai<ybi≤2 0001 \leq n,q \leq 100\,000,0\le xa_i<xb_i\leq 2\,000,0\le ya_i<yb_i\leq 2\,000

扫描线+线段树+树状数组

坐标范围很小，考虑每一个 1×11\times 1 的小正方形是否在所求面积内。

由于每次去掉的都是连续的一个区间，所以如果至少存在一个包含这个小正方形的矩形不在这个区间内，那么这个小正方形就在所求面积中。

所以需要对于每个小正方形，求出包含它且编号最小的矩形，以及包含它且编号最大的矩形。

可以通过扫描线+线段树解决。

线段树维护纵向的2000个小方块，每个节点维护两个优先队列，一个记录包含它的矩形的最小编号，另一个记录最大编号。枚举每一列，当遇到矩形左边界时，把这个矩形的编号压入矩形上下边界构成的区间中所有的小方块的优先队列中；当遇到矩形右边界时，把矩形的 vis 数组置为 1，表明这个矩形不再使用，在之后询问中必须忽略它。当边界在这一列的所有矩形都处理完后进行查询操作，从树根开始向下走，同时维护矩形编号的区间，当到达叶节点时，当前维护的这个区间就是包含这个叶节点对应的小正方形的矩形的最小最大编号。

这里的更新其实是区间更新，而配合这里从根向下走的查询，就不需要push down了。之所以可行，还是因为区间左端点只会变小，右端点只会变大，使得lazy tag可以叠加而不存在新tag必须覆盖旧tag的问题。

且使用优先队列则可以配合使用 vis 数组，这样相当于是有有效期的lazy tag，当矩形的有效期过了，就直接pop掉就好了。

第二部分的问题就变为有多个线段，多次询问，每次询问给出一个区间，问没有被完全包含的线段的个数。

这个问题可以通过主席树在线解决，与 [SDOI2009]HH的项链 有些类似。大致是每次查询时在第 rr 个版本的线段树上查询 [l,r][l,r] 区间内的线段左端点个数，得到的就是完全被 [l,r][l,r] 包含的线段的个数，从总线段个数中减掉后就是答案。

也可以通过扫描线+树状数组离线解决。把询问和线段都按照右端点排序，对于一个询问，插入所有右端点小于询问区间右端点的线段，再用树状数组求出在询问区间 [l,r][l,r] 内的左端点的个数，就是完全被询问区间包含的线段的个数。

下面的代码是用扫描线+树状数组离线。

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>

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int n, q;

struct X {
    int p, yu, yd, id, op;

    bool operator<(const X &b) const {
        return p < b.p;
    }
};

vector<X> vc;
int vis[N];
#define mid ((l+r)>>1)
#define lson l, mid, rt<<1
#define rson mid+1,r,rt<<1|1
priority_queue<int> trmx[2010 << 2];
priority_queue<int, vector<int>, greater<int> > trmn[2010 << 2];

void upd(int ql, int qr, int id, int l, int r, int rt) {
    if (ql <= l && qr >= r) {
        trmn[rt].push(id);
        trmx[rt].push(id);
        return;
    }
    if (ql <= mid)upd(ql, qr, id, lson);
    if (qr > mid)upd(ql, qr, id, rson);
}

vector<pii> v;

void qry(int L, int R, int l, int r, int rt) {
    while (!trmn[rt].empty() && vis[trmn[rt].top()])trmn[rt].pop();
    while (!trmx[rt].empty() && vis[trmx[rt].top()])trmx[rt].pop();
    if (!trmn[rt].empty())L = min(L, trmn[rt].top());
    if (!trmx[rt].empty())R = max(R, trmx[rt].top());
    if (l == r) {
        if (R >= L)v.push_back({R, L});
        return;
    }
    qry(L, R, lson);
    qry(L, R, rson);
}

struct Q {
    int l, r, qid;

    bool operator<(const Q &b) const {
        return r < b.r;
    }
} qq[N];

int ans[N];
int sum[N];

void add(int q, int x) {
    for (int i = q; i <= n; i += (i & -i)) {
        sum[i] += x;
    }
}

int qsum(int r) {
    int ans = 0;
    for (int i = r; i; i -= (i & -i))ans += sum[i];
    return ans;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        int xa, ya, xb, yb;
        scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
        xa++;
        ya++;
        xb++;
        yb++;
        vc.push_back({xa, ya, yb, i, 1});
        vc.push_back({xb, ya, yb, i, -1});
    }
    sort(vc.begin(), vc.end());
    int t = 0;
    for (int i = 1; i <= 2000; i++) {
        while (t < (int) vc.size() && vc[t].p <= i) {
            if (vc[t].op == 1) {
                upd(vc[t].yu, vc[t].yd - 1, vc[t].id, 1, 2000, 1);
            } else {
                vis[vc[t].id] = 1;
            }
            t++;
        }
        qry(n, 1, 1, 2000, 1);
    }
    sort(v.begin(), v.end());
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &qq[i].l, &qq[i].r);
        qq[i].qid = i;
    }
    sort(qq + 1, qq + q + 1);
    t = 0;
    for (int i = 1; i <= q; i++) {
        while (t < (int) v.size() && v[t].first <= qq[i].r) {
            add(v[t].second, 1);
            t++;
        }
        ans[qq[i].qid] = (int) v.size() - (qsum(qq[i].r) - qsum(qq[i].l - 1));
    }
    for (int i = 1; i <= q; i++)printf("%d\n", ans[i]);
    return 0;
}