CF题解(杂)

题目传送门

E. Store

二维数据结构
树套树即可
也可以分治一维,另一维用数据结构维护

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
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
template<class T> struct node {
T val;
int cl, cr;
void clear() {
val = 0;
cl = cr = 0;
}
};
template<class T> struct SegBit {
node<T> f[maxn * 100];
int limx, limy, tot;
void init(int x, int y) {
tot = limx = x;
limy = y;
for(int i = 1; i <= limx; i++) f[i].clear();
}
void update(int t, int l, int r, int x, T v) {
if(l == r) {
f[t].val += v; // 单点更新
return;
}
int mid = (l + r) >> 1;
if(x <= mid) {
if(!f[t].cl) {
f[t].cl = ++tot;
f[tot].clear();
}
update(f[t].cl, l, mid, x, v);
} else {
if(!f[t].cr) {
f[t].cr = ++tot;
f[tot].clear();
}
update(f[t].cr, mid + 1, r, x, v);
}
f[t].val = 0;
if(f[t].cl) f[t].val += f[f[t].cl].val;
if(f[t].cr) f[t].val += f[f[t].cr].val;
}
T query(int t, int l, int r, int ll, int rr) {
if(ll <= l && r <= rr) return f[t].val;
int mid = (l + r) >> 1;
T res = 0;
if(f[t].cl && ll <= mid) res += query(f[t].cl, l, mid, ll, rr);
if(f[t].cr && rr > mid) res += query(f[t].cr, mid + 1, r, ll, rr);
return res;
}
void update(int x, int y, int v) {
for(; x <= limx; x += (x & -x)) update(x, 1, limy, y, v);
}
T query(int x, int y1, int y2) {
T res = 0;
for(; x > 0; x -= (x & -x)) res += query(x, 1, limy, y1, y2);
return res;
}
T query(int x1, int x2, int y1, int y2) {
return query(x2, y1, y2) - query(x1 - 1, y1, y2);
}
};
struct fnode {
int op, x1, x2, y1, y2;
};
vector<P> id[maxn];
vector<fnode> fq[maxn];
int ans[maxn];
SegBit<int> S;
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int x, y, z, n, m, k, i, a, b, c;
int xl, xr, yl, yr, zl, zr;
scanf("%d%d%d%d%d%d", &x, &y, &z, &n, &m, &k);
xl = x;
xr = 0;
yl = y;
yr = 0;
zl = z;
zr = 0;
for(i = 0; i < n; i++) {
scanf("%d%d%d", &a, &b, &c);
xl = min(xl, a);
xr = max(xr, a);
yl = min(yl, b);
yr = max(yr, b);
zl = min(zl, c);
zr = max(zr, c);
}
for(i = 0; i < m; i++) {
scanf("%d%d%d", &a, &b, &c);
if(xl <= a && a <= xr && yl <= b && b <= yr && zl <= c && c <= zr) {
puts("INCORRECT");
return 0;
}
id[a].push_back(P(b, c));
}
puts("CORRECT");
int fxl, fxr, fyl, fyr, fzl, fzr;
for(i = 1; i <= k; i++) {
scanf("%d%d%d", &a, &b, &c);
if(xl <= a && a <= xr && yl <= b && b <= yr && zl <= c && c <= zr) ans[i] = -1;
else {
fxl = min(xl, a);
fxr = max(xr, a);
fyl = min(yl, b);
fyr = max(yr, b);
fzl = min(zl, c);
fzr = max(zr, c);
fq[fxl - 1].push_back(fnode{-i, fyl, fyr, fzl, fzr});
fq[fxr].push_back(fnode{i, fyl, fyr, fzl, fzr});
}
}
S.init(y, z);
for(i = 1;i <= x; i++) {
for(auto e:id[i]) S.update(e.fi, e.se, 1);
for(auto e:fq[i]) ans[abs(e.op)] += (e.op > 0 ? 1 : -1) * S.query(e.x1, e.x2, e.y1, e.y2);
}
for(i = 1;i <= k; i++) {
if(ans[i] == -1) puts("OPEN");
else if(ans[i] == 0) puts("UNKNOWN");
else puts("CLOSED");
}
return 0;
}

题目传送门

G. Allowed Letters

枚举当前位置的字符是什么
利用二维前缀和和$bitmarks$就可以很快的确定当前位置能不能填这个值

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
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
char s[maxn], fs[55], ans[maxn];
int mk[maxn], cnt[64], dm[64];
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n, m, i, j, k, x;
scanf("%s", s + 1);
n = strlen(s + 1);
for(i = 1; i <= n; i++) cnt[1 << (s[i] - 'a')]++;
for(i = 1; i <= n; i++) mk[i] = 63;
scanf("%d", &m);
while(m--) {
scanf("%d %s", &i, fs);
k = strlen(fs);
for(x = j = 0; j < k; j++) x |= 1 << (fs[j] - 'a');
mk[i] = x;
}
for(i = 1; i <= n; i++) dm[mk[i]]++;
for(i = 0; i < 6; i++) {
for(j = 0; j < 64; j++) {
if((j >> i) & 1) {
cnt[j] += cnt[j ^ (1 << i)];
dm[j] += dm[j ^ (1 << i)];
}
}
}
for(i = 1; i <= n; i++) {
x = mk[i];
for(k = 0; k < 64; k++) {
if((k & x) == x) dm[k]--;
}
for(j = 0; j < 6; j++) {
if((x >> j) & 1) {
if(!cnt[1 << j]) continue;
for(k = 0; k < 64; k++) {
if((k >> j) & 1) cnt[k]--;
}
bool fg = 0;
for(k = 0; k < 64; k++) fg |= dm[k] > cnt[k];
if(!fg) {
ans[i] = 'a' + j;
break;
}
for(k = 1; k < 64; k++) {
if((k >> j) & 1) cnt[k]++;
}
}
}
if(j == 6) return puts("Impossible"), 0;
}
ans[n + 1] = 0;
printf("%s\n", ans + 1);
return 0;
}

题目传送门

D. Cycles in product

$dp$维护两棵树上所有长度为$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
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int mod = 998244353;
const int maxn = 4005;
void add(int &x, int y) {
x += y;
if(x >= mod) x -= mod;
}
int mul(int x, int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
vector<int> g[maxn];
int f[maxn][40], pre[maxn][40], d[40], w[40], k;
int f1[40], f2[40], c[80][80];
void merge(int p[], int q[]) {
for(int i = 1;i <= k; i++) {
for(int j = 0;j < i; j++) add(p[i], mul(p[i - j - 1], q[j]));
}
}
void split(int p[], int q[]) {
for(int i = k;i > 0; i--) {
for(int j = 0;j < i; j++) add(p[i], mod - mul(p[i - j - 1], q[j]));
}
}
void pdfs(int u, int fa) {
memset(f[u], 0, sizeof(f[u]));
f[u][0] = 1;
for(auto v : g[u]) {
if(v == fa) continue;
pdfs(v, u);
}
memset(d, 0, sizeof(d));
for(auto v : g[u]) {
if(v == fa) continue;
for(int i = 0;i < k; i++) add(d[i], f[v][i]);
}
merge(f[u], d);
}
void dfs(int u, int fa) {
memcpy(d, pre[u], sizeof(d));
for(auto v : g[u]) {
if(v == fa) continue;
for(int i = 0;i < k; i++) add(d[i], f[v][i]);
}
memset(w, 0, sizeof(w));
w[0] = 1;
merge(w, d);
for(int i = 0; i <= k; i++) add(f1[i], w[i]);
for(auto v : g[u]) {
if(v == fa) continue;
for(int i = 0;i < k; i++) add(d[i], mod - f[v][i]);
memset(pre[v], 0, sizeof(pre[v]));
pre[v][0] = 1;
merge(pre[v], d);
for(int i = 0;i < k; i++) add(d[i], f[v][i]);
}
for(auto v : g[u]) {
if(v == fa) continue;
dfs(v, u);
}
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n1, n2, i, u, v, ans = 0;
for(i = 0;i < 80; i++) {
c[i][0] = 1;
for(v = 1;v <= i; v++) {
c[i][v] = c[i - 1][v - 1];
add(c[i][v], c[i - 1][v]);
}
}
scanf("%d%d%d", &n1, &n2, &k);
if(k & 1) return puts("0"), 0;
k >>= 1;
for(i = 1; i < n1; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
pdfs(1, 0);
dfs(1, 0);
memcpy(f2, f1, sizeof(f1));
memset(f1, 0, sizeof(f1));
memset(pre[1], 0, sizeof(pre[1]));
for(i = 1;i <= n1; i++) g[i].clear();
for(i = 1; i < n2; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
pdfs(1, 0);
dfs(1, 0);
for(i = 0;i <= k; i++) add(ans, mul(c[k * 2][i * 2], mul(f1[i], f2[k - i])));
printf("%d\n", ans);
return 0;
}

题目传送门

E. Good Subsegments

一个好的区间一定是等价于满足$max - min = r - l$
离线询问,从$1$枚举到$n$
利用栈维护出当前值作为最大值或最小值的区间长度
线段树维护$l - i + max - min$的值每次加上值为$0$的数的数量
因为这个值一定是$>= 0$的,所以等价于维护区间最小值就可以了

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
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int maxn = 120005;
struct node {
int ft, val, fmin, cnt;
LL sum;
void add(node &l, node &r) {
sum = l.sum + r.sum;
fmin = min(l.fmin, r.fmin);
cnt = 0;
if(fmin == l.fmin) cnt += l.cnt;
if(fmin == r.fmin) cnt += r.cnt;
}
void down(node &l, node &r) {
if(val) {
l.add(val);
r.add(val);
val = 0;
}
if(ft) {
if(fmin == l.fmin) l.addt(ft);
if(fmin == r.fmin) r.addt(ft);
ft = 0;
}
}
void add(int x) {
val += x;
fmin += x;
}
void addt(int x) {
ft += x;
sum += 1LL * x * cnt;
}
} f[maxn << 2];
int a[maxn], pmax[maxn], pmin[maxn];
LL ans[maxn];
vector<P> fq[maxn];
void build(int t, int l, int r) {
if(l == r) {
f[t].fmin = l;
f[t].cnt = 1;
return;
}
int mid = (l + r) >> 1;
build(t << 1, l, mid);
build(t << 1 | 1, mid + 1, r);
f[t].add(f[t << 1], f[t << 1 | 1]);
}
void update(int t, int l, int r, int ll, int rr, int x) {
if(ll <= l && r <= rr) {
f[t].add(x);
return;
}
int mid = (l + r) >> 1;
f[t].down(f[t << 1], f[t << 1 | 1]);
if(ll <= mid) update(t << 1, l, mid, ll, rr, x);
if(rr > mid) update(t << 1 | 1, mid + 1, r, ll, rr, x);
f[t].add(f[t << 1], f[t << 1 | 1]);
}
LL query(int t, int l, int r, int ll) {
if(l >= ll) return f[t].sum;
int mid = (l + r) >> 1;
f[t].down(f[t << 1], f[t << 1 | 1]);
LL res = query(t << 1 | 1, mid + 1, r, ll);
if(ll <= mid) res += query(t << 1, l, mid, ll);
f[t].add(f[t << 1], f[t << 1 | 1]);
return res;
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n, q, i, x, y;
scanf("%d", &n);
for(i = 1;i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
scanf("%d", &q);
for(i = 1;i <= q; i++) {
scanf("%d%d", &x, &y);
fq[y].push_back(P(x, i));
}
x = y = 0;
for(i = 1;i <= n; i++) {
f[1].add(-1);
while(x && a[pmax[x]] < a[i]) {
update(1, 1, n, pmax[x - 1] + 1, pmax[x], a[i] - a[pmax[x]]);
x--;
}
pmax[++x] = i;
while(y && a[pmin[y]] > a[i]) {
update(1, 1, n, pmin[y - 1] + 1, pmin[y], a[pmin[y]] - a[i]);
y--;
}
pmin[++y] = i;
f[1].addt(1);
for(auto e:fq[i]) ans[e.se] = query(1, 1, n, e.fi);
}
for(i = 1;i <= q; i++) printf("%lld\n", ans[i]);
return 0;
}