http://codeforces.com/gym/101991
A. Awesome Shawarma
题意：给定一棵树，问有几种添加一条边的方式，使得新图上的桥的数量在 [L,R]。新图不能有自环，可以有重边。
树上点分治
容易发现问题其实是求距离在 [n−1−L,n−1−R] 的点对个数。
这是经典的树上点分治问题。
找到重心，分割成若干棵子树，同一子树中的点对继续递归，枚举这棵树被分割前的所有点，找到不在同一子树的点对。由于每次分割后点数都变少了，所以总的点数为 O(nlog(n))，由于找点对个数时还要排序，所以最终为 O(nlog2(n))。
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
| #include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, r, l) for (int i = l, i##end = r; i >= i##end; --i)
bool dbg = false;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
#define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__);
using namespace std;
typedef pair<int, int> Pair;
typedef long long ll;
typedef long long LL;
typedef long double LD;
const ll mod = 998244353;
const int maxn = 2e5 + 5, inf = 0x3f3f3f3f;
const int N = maxn;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
#define Assert(x) while(!(x));
int T;
int n,L,R;
vector<int>G[N];
bool vis[N];
int siz[N];
ll ans;
int get_sz(int u, int _fa){
siz[u] = 1;
for(int v:G[u]){
if(v==_fa||vis[v])continue;
siz[u]+=get_sz(v, u);
}
return siz[u];
}
typedef pair<int,int>pii;
pii get_rt(int u, int _fa,int tot){
pii res = pii(INF, -1);
int s=1,m=0;
for(int v:G[u]){
if(v==_fa||vis[v])continue;
res = min(res, get_rt(v, u, tot));
m = max(m, siz[v]);
s+=siz[v];
}
m = max(m, tot - s);
res = min(res, pii(m, u));
return res;
}
void enu_paths(int u, int _fa, int d, vector<int>& ds){
ds.push_back(d);
for(int v:G[u]){
if(v==_fa||vis[v])continue;
enu_paths(v, u, d+1, ds);
}
}
ll count_pairs(vector<int>& ds, int K){
ll res = 0;
sort(ds.begin(), ds.end());
int j = ds.size();
for(int i=0;i<ds.size();i++){
while(j > 0 && ds[i] + ds[j - 1] > K) --j;
res += j - (j > i ? 1 : 0);
}
return res / 2;
}
void solve(int u, int K){
get_sz(u, -1);
int rt = get_rt(u, -1, siz[u]).second;
vis[rt] = 1;
for(int v:G[rt]){
if(vis[v])continue;
solve(v, K);
}
vector<int>ds;
ds.push_back(0);
for(int v:G[rt]){
if(vis[v])continue;
vector<int>tds;
enu_paths(v, rt, 1, tds);
ans-=count_pairs(tds, K);
ds.insert(ds.end(),tds.begin(),tds.end());
}
ans+=count_pairs(ds, K);
vis[rt]=0;
}
ll cal(int x){
if(x<0)return 0;
ans=0;
solve(1, x);
debug(ans)
return ans;
}
int main() {
freopen("awesome.in", "r", stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&L,&R);
for(int i=1;i<=n;i++)G[i].clear();
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
printf("%lld\n",cal(n-1-L)-cal(n-1-R-1));
}
return 0;
}
|
题意：给定 n 个字符串，n 个长度等于对应字符串长度的数组 Ai，要求选出一个子串 Sj,ki，代表这个子串是第 i 个字符串的 [j⋯k]，最大化 Q(i,j,k)=popularity(Sj,ki)×Aki×∣Sj,ki∣，其中 popularity(Sj,ki) 给定字符串中以串 Sj,ki 为前缀的串的个数，Aki 代表数组 Ai 的第 k 个元素，∣Sj,ki∣ 代表串 Sj,ki 的长度。输出最大的 Q 值。
AC自动机
注意到答案只会受到某个字符串的前缀的影响，所以考虑枚举所有前缀。
把所有字符串插入AC自动机，在插入时记录每个节点的 popularity×∣s∣，记为 h[u]。在建立自动机时还必须处理出当前节点的fail链上的 h[u] 的最大值，因为 fail 指针指向的虽然不是当前串的前缀，但可能是其他串的前缀，所以仍然要比较。
最后枚举每个串，对每个串从前往后沿着自动机跳，即枚举前缀。
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
| #include <bits/stdc++.h>
#define debug(x) 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;
int tr[N][26], tot;
ll h[N];
int e[N], fail[N];
void insert(string s) {
int u = 0;
for (int i = 0; s[i]; i++) {
if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;
u = tr[u][s[i] - 'a'];
e[u]++;
h[u] = max(h[u], 1ll * e[u] * (i + 1));
}
}
queue<int> q;
void build() {
for (int i = 0; i < 26; i++)
if (tr[0][i]) q.push(tr[0][i]);
while (q.size()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
if (tr[u][i]) {
fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
h[tr[u][i]] = max(h[tr[u][i]], h[fail[tr[u][i]]]);
}
else
tr[u][i] = tr[fail[u]][i];
}
}
}
int T;
int n, m;
string s[N];
vector<ll>a[N];
int main() {
freopen("exciting.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++)cin >> s[i], a[i].clear();
for (int i = 1; i <= n; i++) {
m = s[i].length();
for (int j = 1; j <= m; j++) {
ll x;
cin >> x;
a[i].push_back(x);
}
}
for (int i = 1; i <= n; i++) {
insert(s[i]);
}
build();
ll ans = 0;
for (int i = 1; i <= n; i++) {
int u = 0, m = s[i].length();
for (int j = 0; j < m; j++) {
u = tr[u][s[i][j] - 'a'];
ans = max(ans, h[u] * a[i][j]);
}
}
printf("%lld\n", ans);
for (int i = 0; i <= tot; i++) {
e[i] = fail[i] = h[i] = 0;
for (int j = 0; j < 26; j++)tr[i][j] = 0;
}
tot = 0;
}
return 0;
}
|
G. Greatest Chicken Dish
题意：给定数列 A，Q 次询问，每次询问给定 L,R,D，问区间 [L,R] 中有几个连续子区间的 gcd 为 D.
二分+ST表+线段树
首先处理出所有的 gcd。对于右端点相同都为为 R 的区间，最多有 logA[R] 个不同的 gcd，因为左端点在向左移动的过程中，每次 gcd 改变必定是从之前的 gcd 中除掉一个因子，而初始 gcd 最多被除 logA[R] 次。
遍历右端点，对于一个右端点，要找出所有的 gcd 变化时的区间左端点，可以通过二分左端点，若 \gcd[mid,R]!=\text{old_gcd}，则再向右找。这里面的区间询问 gcd 需要通过预处理出 ST表，再 O(1) 询问得到。
离线询问，对于每个 gcd 单独处理，gcd 相同的询问按照右端点升序排序。把上一步处理出的区间也按照右端点排序，和询问放在一起，遍历所有这些区间，每次遇到上一步处理出的区间，则update这个区间的影响，若是询问则查询出答案。
现在只考虑 gcd 为 G 的区间，假设对于固定的右端点 R，左端点位于 [L1,L2]，则在线段树上对 [L1,L2] 进行区间+1，代表每个左端点位于 [L1,L2] 且 gcd 等于 G 的区间个数都+1.
遇到询问时，已经更新了所有右端点小于等于询问的右端点的影响，则直接线段树上查询 [L,R] 的和，即左端点位于 [L,R] 的区间的值之和。
当改变 gcd 值时，通过类似懒标记的方法清除整棵线段树。
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
| #include <bits/stdc++.h>
#define debug(x) 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;
const int maxm = 1e6 + 10;
int T;
int n, q;
int a[N];
int g[N][25];
int _gcd(int a, int b) {
if (a < b)swap(a, b);
return b == 0 ? a : _gcd(b, a%b);
}
void ini(int n) {
for (int i = 1; i <= n; i++) {
g[i][0] = a[i];
}
for (int i = 1; i < 25; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
g[j][i] = _gcd(g[j][i - 1], g[j + (1 << (i - 1))][i - 1]);
}
}
}
int gcd(int a, int b) {
int len = log2(b - a + 1);
return _gcd(g[a][len], g[b - (1 << len) + 1][len]);
}
struct X
{
int l1, l2, r, qid;
bool operator<(const X& b)const {
if (r != b.r)return r < b.r;
return qid < b.qid;
}
};
vector<X>vc[maxm];
ll ans[N];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll tr[N << 2], laz[N << 2], clr[N << 2];
void up(int rt) {
tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
void build(int l, int r, int rt) {
tr[rt] = laz[rt] = clr[rt] = 0;
if (l == r)return;
build(lson);
build(rson);
}
void down(int l, int r, int rt) {
ll& x = laz[rt];
if (clr[rt]) {
tr[rt << 1] = tr[rt << 1 | 1] = 0;
laz[rt << 1] = laz[rt << 1 | 1] = 0;
clr[rt << 1] = clr[rt << 1 | 1] = 1;
clr[rt] = 0;
}
if (x) {
int md = (l + r) / 2;
laz[rt << 1] += x;
laz[rt << 1 | 1] += x;
tr[rt << 1] += x * (md - l + 1);
tr[rt << 1 | 1] += x * (r - md);
x = 0;
}
}
void upd(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r) {
laz[rt]++;
tr[rt] += r - l + 1;
return;
}
down(l, r, rt);
if (ql <= mid)upd(ql, qr, lson);
if (qr > mid)upd(ql, qr, rson);
up(rt);
}
ll qry(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r)return tr[rt];
down(l, r, rt);
ll ans = 0;
if (ql <= mid)ans += qry(ql, qr, lson);
if (qr > mid)ans += qry(ql, qr, rson);
return ans;
}
int main() {
freopen("gcdrng.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
ini(n);
for (int i = 1; i <= n; i++) {
int pt = i;
while (pt) {
int gc = gcd(pt, i);
int L = 1, R = pt;
while (L < R) {
int md = (L + R) / 2;
if (gcd(md, i) != gcd(pt, i))L = md + 1;
else R = md;
}
vc[gc].push_back({ L,pt,i,0 });
pt = L - 1;
}
}
for (int i = 1; i <= q; i++) {
int l, r, d;
scanf("%d%d%d", &l, &r, &d);
vc[d].push_back({ l,0,r,i });
}
build(1, n, 1);
for (int i = 1; i < maxm; i++) {
sort(vc[i].begin(), vc[i].end());
tr[1] = laz[1] = 0; clr[1] = 1;
for (X& p : vc[i]) {
if (!p.qid) {
upd(p.l1, p.l2, 1, n, 1);
}
else {
ans[p.qid] = qry(p.l1, p.r, 1, n, 1);
}
}
vc[i].clear();
}
for (int i = 1; i <= q; i++)printf("%lld\n", ans[i]);
}
return 0;
}
|
