跳转至

250717 模拟赛

T2 phi

给定 \(n\) 个数字 \(a_i\)，请你求出

\[ \sum_{S\subseteq \{1,2,\cdots,n\}}\varphi\left(\prod_{i\in S}a_i\right) \]

\(n\le 2000,\ a_i\le 3000\)

由于欧拉函数是积性函数，因此我们可以将 \(\prod a_i\) 的所有质因子分开处理，再相乘。

注意到 \(a_i\le 3000\)，考虑根号分治，大于 \(53\) 的质因子最多只有一个。注意到转移时我们只关心每个质因子是否出现过，因此考虑状压。记 \(p_{1,i}\) 表示 \(a_i\) 中小质数的集合，\(p_{2,i}\) 表示 \(a_i\) 剩下的一个大质数是多少。我们状压前 \(16\) 个质数是否在 \(\prod a_i\) 中出现过，转移时考虑将 \(p_{2}\) 相同的数字放在一起处理。容易做到 \(O(n2^{16})\)。

代码 
  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
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 3010;
const int MOD = 998244353;

#define add(a, b) a = (a + b) % MOD;

int inv[N], w[N], sum[1 << 16], lg[1 << 16];
int pri[N], npri[N], cnt;

inline int calc(int p) { return p == 1 ? 1 : (p - 1) * inv[p] % MOD; }

int n;
int a[N];

int p1[N], p2[N];
int swp[N], tmp[N];

int f[2][1 << 16], g[1 << 16];

// #define FIO

signed main() {

    #ifdef FIO
    freopen("phi.in", "r", stdin);
    freopen("phi.out", "w", stdout);
    #endif

    inv[1] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;

    for(int i = 1; i < 16; i++) lg[1 << i] = i;

    for(int i = 2; i < N; i++) {
        if(!npri[i]) pri[++cnt] = i;
        for(int j = 1; j <= cnt; j++) {
            if(i * pri[j] >= N) break;
            npri[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }

    for(int i = 1; i <= cnt; i++) w[i] = (pri[i] - 1) * inv[pri[i]] % MOD;

    pri[0] = 1;
    w[0] = 1;

    sum[0] = 1;
    for(int i = 1; i < (1 << 16); i++) {
        sum[i] = sum[i ^ (i & -i)] * w[lg[i & -i] + 1] % MOD;
    }

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= n; i++) {
        int x = a[i];
        for(int j = 1; j <= 16; j++) {
            if(x % pri[j] == 0) p1[i] |= (1 << j - 1);
            while(x % pri[j] == 0) x /= pri[j];
        }
        p2[i] = lower_bound(pri, pri + 1 + cnt, x) - pri;
    }

    for(int i = 1; i <= n; i++) swp[i] = i;
    sort(swp + 1, swp + 1 + n, [](int a, int b) { return p2[a] < p2[b]; } );

    for(int i = 1; i <= n; i++) tmp[i] = p1[i];
    for(int i = 1; i <= n; i++) p1[i] = tmp[swp[i]];
    for(int i = 1; i <= n; i++) tmp[i] = p2[i];
    for(int i = 1; i <= n; i++) p2[i] = tmp[swp[i]];
    for(int i = 1; i <= n; i++) tmp[i] = a[i];
    for(int i = 1; i <= n; i++) a[i] = tmp[swp[i]];

    p2[n + 1] = -1;

    int lst = 1;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int s = (1 << 16) - 1; s >= 0; s--) {
            add(f[lst][s | p1[i]], f[lst][s] * a[i] % MOD);
            add(f[lst][s | p1[i]], f[lst ^ 1][s] * w[p2[i]] % MOD * a[i] % MOD);
        }
        if(p2[i] != p2[i + 1]) {
            for(int s = 0; s < (1 << 16); s++) add(f[lst][s], f[lst ^ 1][s]);
            lst ^= 1;
            for(int s = 0; s < (1 << 16); s++) f[lst][s] = 0;
        }
    }

    int ans = 0;
    for(int s = 0; s < (1 << 16); s++) {
        add(ans, f[lst ^ 1][s] * sum[s] % MOD);
    }

    cout << ans << endl;

    return 0;
}

T3 rec

给你 \(n\times m\) 网格图上的 \(k\) 个矩形，请你选出一些，使得它们的交非空并且包含点数最少。求该最小值。

\(n,m\le 2000,\ k\le 10^6\)

数据结构怎么你们了。

注意到原问题就是让我们对每个格子 \((i,j)\) 求出，包含它的所有矩形的交是多大，然后取 \(\min\) 即可。由于最终的形状一定是矩形，因此只需对每个格子求出，包含它的矩形中，上边界的最小值，下边界的最大值，右边界的最小值和左边界的最大值。

注意到四个方向是完全等价的，因此只需考虑一个方向，假设当前需要解决左边界的最大值。考虑扫描线，我们希望得到所有与当前行有交的矩形在当前行的投影区间，然后将每个区间的右端点挂在左端点处，这样问题就转化为对当前行上的每个点 \(j\) 求出其左边第一个大于它的值。可以使用单调栈求解。

还有一个问题，如果对于每行我们都把所有有效的矩形处理一遍，时间复杂度将达到 \(O(nk+nm)\)，不能通过。

注意到我们只关心投影区间左端点对应的右端点的最大值，并且这个最大值只会在扫描线经过矩形的上、下边界时发生变化。由于扫描线需要支持动态随机删除，因此这里对每列都维护一个 set（表示以该点为左端点，所有可能的右端点）即可。

对于当前行，我们求出每一列中 set 的最大值，然后用单调栈维护即可求出答案。时间复杂度 \(O(nm+k\log k)\)。

由于出题人只想放线性做法，因此需要卡常：加上快读，把 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
 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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
#include<ctype.h>
#include<bits/stl_algobase.h>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 2010;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;

char endl = '\n';

namespace io {
    struct istream {
        char ch;
        bool flag;
        inline istream &operator>>(int &x) {
            flag = 0;
            while(!isdigit(ch = getchar_unlocked())) (ch == '-') && (flag = 1);
            x = ch - '0';
            while(isdigit(ch = getchar_unlocked())) x = (x << 3) + (x << 1) + ch - '0';
            flag && (x = -x);
            return *this;
        }
    } cin;
    struct ostream {
        char buf[60];
        int top;
        inline ostream() : top(0) {}
        inline ostream &operator<<(int x) {
            if(x < 0) putchar_unlocked('-'), x = -x;
            do buf[++top] = x % 10 + '0', x /= 10; while(x);
            while(top) putchar_unlocked(buf[top--]);
            return *this;
        }
        inline ostream &operator<<(char c) {
            putchar_unlocked(c);
            return *this;
        }
        inline ostream &operator<<(const char s[]) {
            for(int i = 0; s[i]; i++) putchar_unlocked(s[i]);
            return *this;
        }
    } cout;
}

using io::cin;
using io::cout;

struct Rec {
    int x1, y1, x2, y2;
} a[M];

struct Op {
    int key, p, v, w;
    inline bool operator<(const Op &b) const {
        return key < b.key;
    }
};

template<typename _Comp>
struct myHeap {
    priority_queue<int, vector<int>, _Comp> que, del;
    inline void clear() {
        while(!que.empty()) que.pop();
        while(!del.empty()) del.pop();
    }
    inline bool empty() { return que.size() == del.size(); }
    inline void push(int x) { que.push(x); }
    inline int top() {
        while(!del.empty() && que.top() == del.top()) que.pop(), del.pop();
        return que.top();
    }
    inline void erase(int x) { del.push(x); }
    inline void pop() {
        while(que.top() == del.top()) que.pop(), del.pop();
        que.pop();
    }
};

int n, m, k;

vector<Op> op;
myHeap<less<int> > st1[N];
myHeap<greater<int> > st2[N];

int sta[N], top;
int t[N];

int mxy[N][N], mny[N][N], mxx[N][N], mnx[N][N];

int main() {

    // freopen("rec.in", "r", stdin);
    // freopen("rec.out", "w", stdout);

    cin >> n >> m >> k;
    for(int i = 1; i <= k; i++) cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;

    op.clear();
    for(int i = 1; i <= m; i++) st2[i].clear();
    for(int i = 1; i <= k; i++) {
        op.push_back({a[i].x1, a[i].y1, a[i].y2, 1});
        op.push_back({a[i].x2 + 1, a[i].y1, a[i].y2, -1});
    }
    sort(op.begin(), op.end());
    for(int i = 1, j = 0; i <= n; i++) {
        while(j < op.size() && op[j].key == i) {
            if(op[j].w == 1) st2[op[j].p].push(op[j].v);
            else st2[op[j].p].erase(op[j].v);
            ++j;
        }
        top = 0;
        sta[0] = INF;
        for(int j = 1; j <= m; j++) {
            while(top && t[sta[top]] < j) --top;
            if(st2[j].empty()) {
                mxy[i][j] = sta[top];
                continue;
            }
            t[j] = st2[j].top();
            while(top && t[sta[top]] <= t[j]) --top;
            sta[++top] = j;
            mxy[i][j] = j;
        }
    }

    op.clear();
    for(int i = 1; i <= m; i++) st1[i].clear();
    for(int i = 1; i <= k; i++) {
        op.push_back({a[i].x1, a[i].y2, a[i].y1, 1});
        op.push_back({a[i].x2 + 1, a[i].y2, a[i].y1, -1});
    }
    sort(op.begin(), op.end());
    for(int i = 1, j = 0; i <= n; i++) {
        while(j < op.size() && op[j].key == i) {
            if(op[j].w == 1) st1[op[j].p].push(op[j].v);
            else st1[op[j].p].erase(op[j].v);
            ++j;
        }
        top = 0;
        sta[0] = 0;
        for(int j = m; j >= 1; j--) {
            while(top && t[sta[top]] > j) --top;
            if(st1[j].empty()) {
                mny[i][j] = sta[top];
                continue;
            }
            t[j] = st1[j].top();
            while(top && t[sta[top]] >= t[j]) --top;
            sta[++top] = j;
            mny[i][j] = j;
        }
    }

    op.clear();
    for(int i = 1; i <= n; i++) st2[i].clear();
    for(int i = 1; i <= k; i++) {
        op.push_back({a[i].y1, a[i].x1, a[i].x2, 1});
        op.push_back({a[i].y2 + 1, a[i].x1, a[i].x2, -1});
    }
    sort(op.begin(), op.end());
    for(int i = 1, j = 0; i <= m; i++) {
        while(j < op.size() && op[j].key == i) {
            if(op[j].w == 1) st2[op[j].p].push(op[j].v);
            else st2[op[j].p].erase(op[j].v);
            ++j;
        }
        top = 0;
        sta[top] = INF;
        for(int j = 1; j <= n; j++) {
            while(top && t[sta[top]] < j) --top;
            if(st2[j].empty()) {
                mxx[j][i] = sta[top];
                continue;
            }
            t[j] = st2[j].top();
            while(top && t[sta[top]] <= t[j]) --top;
            sta[++top] = j;
            mxx[j][i] = j;
        }
    }

    op.clear();
    for(int i = 1; i <= n; i++) st1[i].clear();
    for(int i = 1; i <= k; i++) {
        op.push_back({a[i].y1, a[i].x2, a[i].x1, 1});
        op.push_back({a[i].y2 + 1, a[i].x2, a[i].x1, -1});
    }
    sort(op.begin(), op.end());
    for(int i = 1, j = 0; i <= m; i++) {
        while(j < op.size() && op[j].key == i) {
            if(op[j].w == 1) st1[op[j].p].push(op[j].v);
            else st1[op[j].p].erase(op[j].v);
            ++j;
        }
        top = 0;
        sta[top] = 0;
        for(int j = n; j >= 1; j--) {
            while(top && t[sta[top]] > j) --top;
            if(st1[j].empty()) {
                mnx[j][i] = sta[top];
                continue;
            }
            t[j] = st1[j].top();
            while(top && t[sta[top]] >= t[j]) --top;
            sta[++top] = j;
            mnx[j][i] = j;
        }
    }

    int ans = INF;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(mxx[i][j] <= mnx[i][j] && mxy[i][j] <= mny[i][j]) {
                ans = min(ans, (mnx[i][j] - mxx[i][j] + 1) * (mny[i][j] - mxy[i][j] + 1));
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

T4 cip

有 \(n\) 天时间，第 \(i\) 天可以买到质量为 \(a_i\) 的原料，原料每经过一天，质量都会下降 \(1\)。当满足 \(a'\ge b_i\) 时，你可以选择在第 \(i\) 天对原料进行加工，产生 \(a'c_i\) 的价值，并消耗掉原料。

你会在第一天，以及每次加工之后的第二天（最后一天除外）开始时（加工之前）购买当天的原料一件。第 \(n\) 天结束时，你手上不能有原料。

求最大价值。

（保证 \(c_i\) 单调不降，该条件在单 \(\log\) 做法中使用）

\(n\le 2\times 10^5,\ 0\le a_i,c_i\le 5\times 10^4, -n\le b_i\le 5\times 10^4\)

设 \(f_i\) 表示前 \(i\) 天的答案，钦定第 \(i\) 天进行了加工。不难写出转移：

\[ f_i\gets f_j+\big(a_{j+1}-(i-j-1)\big)c_i\quad \text{for }j<i\wedge a_{j+1}-(i-j-1)\ge b_i \]

为了简化式子，执行：

\[ a_i\gets a_{i+1}+i+1\\ b_i\gets b_i+i \]

这样，转移式就变为

\[ f_i\gets f_j+a_jc_i-ic_i\quad \text{for }j<i\wedge a_j\ge b_i \]

如果没有 \(b_i\) 的约束，那么使用李超线段树即可。考虑用 cdq 处理掉一维限制。由于 cdq 优化 dp 需要保证本轮分治的转移过程中 \(j\) 的 dp 值已经计算完毕，因此不能分治 \(a_j,b_i\) 维度（不能保证 \(j\) 在转移 \(i\) 时 \(j\) 已经是最新，因为 \(b_j\) 可能也在左半区间）。

这里我们将所有 \(a_i\) 和 \(b_i\) 分成两个点，一个转移别人，一个接受转移。我们按 \(a_j\) 或 \(b_i\) 排序后，对下标维度进行分治。现在我们无须考虑下标维度，问题转化为一个一维 dp 问题。由于加点的斜率不具有单调性，因此需要使用李超线段树。

cdq 只能维护偏序

在进行 cdq 分治的过程中，必须保证 \([l,mid]\) 和 \([mid+1,r]\) 的贡献是单向的。尤其是像本题一样，一个 \(f_i\) 具有两个关键字，要注意这两个关键字之间也是会产生贡献的。

代码 
  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
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define ld long double
using namespace std;
const int N = 2e5 + 10;
const int V = 5e4 + 10 + N;
const int INF = 0x3f3f3f3f3f3f3f3f;

inline void gmax(int &a, int b) { a = max(a, b); }

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

int n;
int a[N], c[N], b[N];

int f[N];

namespace SegT {
    struct Line {
        int k, b;
        inline void clear(int _p1 = 0, int _p2 = 0) { k = _p1, b = _p2; }
    } pool[N];
    int nn;
    int s[4 * (V + 5)];
    int t[4 * (V + 5)], cur;
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void clear() {
        nn = 0;
        cur ^= 1;
    }
    inline void flush(int p) {
        if(t[p] != cur) {
            t[p] = cur;
            s[p] = 0;
        }
    }
    inline int calc(int id, int x) {
        if(!id) return -INF;
        return pool[id].b + pool[id].k * x;
    }
    void move_tag(int p, int l, int r, int id) {
        flush(p);
        if(!s[p]) {
            s[p] = id;
            return;
        }
        int mid = (l + r) >> 1;
        if(calc(id, mid) > calc(s[p], mid)) swap(s[p], id);
        if(calc(id, l) > calc(s[p], l)) move_tag(lc(p), l, mid, id);
        if(calc(id, r) > calc(s[p], r)) move_tag(rc(p), mid + 1, r, id);
    }
    int query(int p, int l, int r, int q) {
        flush(p);
        if(l == r) return calc(s[p], q);
        int mid = (l + r) >> 1;
        if(q <= mid) return max(calc(s[p], q), query(lc(p), l, mid, q));
        else return max(calc(s[p], q), query(rc(p), mid + 1, r, q));
    }
    void insert(Line x) {
        pool[++nn] = x;
        move_tag(1, 1, V, nn);
    }
    int query(int x) { return query(1, 1, V, x); }
}

void cdq(int l, int r, vector<Op> &op) {
    if(op.empty()) return;
    if(l == r) return;
    int mid = (l + r) >> 1;
    vector<Op> lop, rop;
    for(Op &o : op) {
        if(o.id <= mid) lop.push_back(o);
        else rop.push_back(o);
    }
    cdq(l, mid, lop);
    SegT::clear();
    for(Op &o : op) {
        if(o.id <= mid && o.tp == 1) {
            SegT::insert({a[o.id], f[o.id]});
        }
        if(o.id > mid && o.tp == 0) {
            gmax(f[o.id], SegT::query(c[o.id]) - o.id * c[o.id]);
        }
    }
    cdq(mid + 1, r, rop);
}

vector<Op> op;

// #define FIO

signed main() {

    #ifdef FIO
    freopen("cip.in", "r", stdin);
    freopen("cip.out", "w", stdout);
    #endif

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i <= n; i++) cin >> b[i];

    for(int i = 0; i < n; i++) a[i] = a[i + 1] + i + 1;
    for(int i = 1; i <= n; i++) b[i] = b[i] + i;

    for(int i = 0; i < n; i++) {
        op.push_back({1, i, a[i]});
        op.push_back({0, i + 1, b[i + 1]});
    }
    sort(op.begin(), op.end());

    for(int i = 1; i <= n; i++) f[i] = -INF;

    cdq(0, n, op);

    if(f[n] == -INF) cout << "Impossible\n";
    else cout << f[n] << '\n';

    return 0;
}