Codeforces Round #526[CF1083]

发表于 分类于

题目链接

A. The Fair Nut and the Best Path

树形DP模板。

B. The Fair Nut and Strings

先来看看给定 $k$ 个长度为 $n$ 的字符串，然后问你有多少个非空字符串是他们中至少一个的前缀。

把这 $k$ 个串建出一个Trie，那么Trie的节点个数-1就是满足条件的字符串个数。

那么把 $a,b$ 两个串建成Trie，然后在Trie树上数数每一层夹在他们中间的节点个数就好了。

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,k;
char s1[500010],s2[500010];
ll ans,now;
int main()
{
	scanf("%d%d",&n,&k);
	scanf("%s%s",s1,s2);
	now=1;
	ff(i,0,n)
	{
		now<<=1;
		if(s1[i]=='b') now--;
		if(s2[i]=='a') now--;
		if(now>=k) {ans+=1ll*k*(n-i); break;}
		else ans+=now;
	}
	printf("%lld",ans);
	return 0;
}

C. Max Mex

题意

给出一棵树，树上点的点权为一个 $[0,n-1]$ 的排列。

支持交换两点点权，以及求树上路径权值Mex的最大值。

$n\leq 2\times 10^5$。

题解

首先这个东西可以去二分找到最大值。

然后变成判断是否存在一条最短的路径使得某个区间上所有的数都在这条路径上。

考虑合并两个区间的答案。对于某两个区间 $[a,b],[b+1,c]$，假设对这两个区间都存在一条最短的路径，设为 $(A_x,A_y),(B_x,B_y)$，那么区间 $[a,c]$ 有解当且仅当这两条路径的并是一条路径。

那么枚举 $A_x,A_y,B_x,B_y$ 中的两个，看是否能作为合并后路径的端点即可。

判断很简单，需要用到lca。

然后在线段树上二分找到这个最大值即可。

时间复杂度 $O((n+6q)\log 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
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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200010;
namespace T{
	vector<int> adj[N];
	int m,fir[N],dep[N],f[N<<1][20],l2[N<<1];
	inline void add(int x,int y) {adj[x].pb(y);}
	void dfs(int u,int pre)
	{
		dep[u]=dep[pre]+1;
		f[++m][0]=u; fir[u]=m;
		for(auto v:adj[u])
		{
			dfs(v,u);
			f[++m][0]=u;
		}
	}
	inline int getmin(int x,int y)
	{
		return dep[x]>dep[y]?y:x;
	}
	inline int lca(int x,int y)
	{
		x=fir[x]; y=fir[y];
		if(x>y) swap(x,y);
		int k=l2[y-x+1];
		return getmin(f[x][k],f[y-(1<<k)+1][k]);
	}
	inline int dis(int x,int y)
	{
		return dep[x]+dep[y]-(dep[lca(x,y)]<<1);
	}
	inline void work()
	{
		dfs(1,0);
		fo(i,2,m) l2[i]=l2[i>>1]+1;
		fo(j,1,l2[m])
			fo(i,1,m)
			{
				f[i][j]=f[i][j-1];
				if(i+(1<<j)-1<=m) f[i][j]=getmin(f[i][j],f[i+(1<<(j-1))][j-1]);
			}
	}
}
using T::dis;
struct node{
	int x,y;
};
inline bool check(int x,int y,int z)
{
	return dis(x,y)==dis(x,z)+dis(z,y);
}
inline node merge(const node &A,const node &B)
{
	if(A.x==-1||B.x==-1) return (node){-1,-1};
	if(check(A.x,A.y,B.x)&&check(A.x,A.y,B.y)) return A;
	if(check(B.x,B.y,A.x)&&check(B.x,B.y,A.y)) return B;
	if(check(A.x,B.x,A.y)&&check(A.x,B.x,B.y)) return (node){A.x,B.x};
	if(check(A.y,B.y,A.x)&&check(A.y,B.y,B.x)) return (node){A.y,B.y};
	if(check(A.x,B.y,A.y)&&check(A.x,B.y,B.x)) return (node){A.x,B.y};
	if(check(A.y,B.x,A.x)&&check(A.y,B.x,B.y)) return (node){A.y,B.x};
	return (node){-1,-1};
}
int n,p[N],_p[N];
namespace SGT{
	#define lc (u<<1)
	#define rc (u<<1|1)
	#define ls lc,l,mid
	#define rs rc,mid+1,r
	node t[N<<2];
	void build(int u,int l,int r)
	{
		if(l==r) return (void)(t[u]=(node){_p[l],_p[l]});
		int mid=l+r>>1;
		build(ls); build(rs);
		t[u]=merge(t[lc],t[rc]);
	}
	void update(int u,int l,int r,int p)
	{
		if(l==r) return (void)(t[u]=(node){_p[l],_p[l]});
		int mid=l+r>>1;
		(p<=mid)?update(ls,p):update(rs,p);
		t[u]=merge(t[lc],t[rc]);
	}
	int ask(int u,int l,int r,node &A)
	{
		if(t[u].x>=0)
		{
			if(A.x>=0)
			{
				node B=merge(A,t[u]);
				if(B.x>=0) {A=B; return r+1;}
			}
			else {A=t[u]; return r+1;}
		}
		if(l==r) return l;
		int mid=l+r>>1;
		int ans=ask(ls,A);
		if(ans>mid) return ask(rs,A);
		else return ans;
	}
}
using namespace SGT;
int main()
{
	n=read();
	fo(i,1,n) p[i]=read()+1;
	fo(i,1,n) _p[p[i]]=i;
	fo(i,2,n) T::add(read(),i);
	T::work();
	build(1,1,n);
	int x,y;
	node u;
	CASET
	{
		if(read()==1)
		{
			x=read(),y=read();
			swap(_p[p[x]],_p[p[y]]);
			swap(p[x],p[y]);
			update(1,1,n,p[x]);
			update(1,1,n,p[y]);
		}
		else
		{
			u=(node){-1,-1};
			printf("%d\n",ask(1,1,n,u)-1);
		}
	}
	return 0;
}

D. The Fair Nut’s getting crazy

这题还是比较套路的。枚举区间的交 $[i,j]$，看有多少贡献。

设 $pre_i$ 表示值和 $a_i$ 相同的最大的比 $i$ 小的下标，$nex_i$ 表示值和 $a_i$ 相同的最小的比 $i$ 大的下标。

再设 $f_{i,j}=\max_{k\in[i,j]} pre_k+1,g_{i,j}=\min_{k\in[i,j]} nex_k-1$。

枚举一个 $i$，那么合法的 $j$ 是一段连续的区间，设此时这个 $j$ 为 $mx_j$。

那么一个 $i$ 的贡献就是：$\sum_{j=i}^{mx_j}(i-f_{i,j})\times (g_{i,j}-j)$。

化简一下得到：$i\sum_{j=i}^{mx_j}g_{i,j}-i\sum_{j=i}^{mx_j}j-\sum_{j=i}^{mx_j}f_{i,j}g_{i,j}+\sum_{k=i}^{mx_j}jf_{i,j}$。

考虑倒序枚举 $i$，那么每次会修改一些 $g_{i,j}$ 和 $f_{i,j}$，也就是对 $[i,n]$ 取一个 $\min$ 或者 $\max$。

这个用一个单调栈，转换成区间赋值。

那么相当于维护两个序列，支持对这两个序列区间赋值，求 $\sum_{i}g_i,\sum_{i}f_ig_i,\sum_{i}if_i$。

用线段维护若干个区间和即可。

时间复杂度 $O(n\log 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
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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=1e9+7;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
inline ll calc(int x)
{
	return 1ll*x*(x+1)/2%mod;
}
inline ll calc(int x,int y)
{
	return (calc(y)-calc(x-1)+mod)%mod;
}
const int N=1e5+5;
#define lc (u<<1)
#define rc (lc|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
ll s[N<<2][4],tag[N<<2][2];
inline void pushtag(int u,int l,int r,int opt,int x)
{
	s[u][2]=s[u][opt^1]*x%mod;
	s[u][opt]=1ll*(r-l+1)*x%mod;
	tag[u][opt]=x;
	if(opt==0) s[u][3]=1ll*calc(l,r)*x%mod;
}
inline void pushdown(int u,int l,int r)
{
	int mid=l+r>>1;
	fo(i,0,1)
		if(tag[u][i])
		{
			pushtag(ls,i,tag[u][i]);
			pushtag(rs,i,tag[u][i]);
			tag[u][i]=0;
		}
}
inline void pushup(int u)
{
	fo(i,0,3) s[u][i]=(s[lc][i]+s[rc][i])%mod;
}

void update(int u,int l,int r,int L,int R,int opt,int x)
{
	if(L<=l&&r<=R) return pushtag(u,l,r,opt,x);
	pushdown(u,l,r);
	int mid=l+r>>1;
	if(L<=mid) update(ls,L,R,opt,x);
	if(mid<R)  update(rs,L,R,opt,x);
	pushup(u);
}
ll sum[4];
void ask(int u,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
	{
		fo(i,1,3) sum[i]+=s[u][i];
		return;
	}
	pushdown(u,l,r);
	int mid=l+r>>1; ll ans=0;
	if(L<=mid) ask(ls,L,R);
	if(mid<R)  ask(rs,L,R);
}
int n,a[N],b[N],m;
int las[N],pre[N],nex[N],st[N],top;
ll ans;
int f1[N],f2[N];
int main()
{
	n=read();
	fo(i,1,n) b[i]=a[i]=read();
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	fo(i,1,n) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	fo(i,1,n) pre[i]=las[a[i]]+1,las[a[i]]=i;
	fo(i,1,n) las[i]=n+1;
	fd(i,n,1) nex[i]=las[a[i]]-1,las[a[i]]=i;
	st[top=0]=n+1;
	fd(i,n,1)
	{
		for(;top&&pre[i]>pre[st[top]];top--);
		f1[i]=st[top]-1; st[++top]=i;
	}
	st[top=0]=n+1;
	fd(i,n,1)
	{
		for(;top&&nex[i]<nex[st[top]];top--);
		f2[i]=st[top]-1; st[++top]=i;
	}
	fo(i,1,n) las[i]=0;
	int j=n;
	fd(i,n,1)
	{
		update(1,1,n,i,f1[i],0,pre[i]);
		update(1,1,n,i,f2[i],1,nex[i]);
		las[a[i]]++;
		for(;las[a[i]]>=2;las[a[j]]--,j--);
		fo(k,1,3) sum[k]=0;
		ask(1,1,n,i,j);
		fo(k,1,3) sum[k]%=mod;
		(ans+=1ll*i*(sum[1]-calc(i,j))-sum[2]+sum[3])%=mod;
	}
	printf("%lld",(ans+mod)%mod);
	return 0;
}

E. The Fair Nut and Rectangles

Div 1.E就这难度？？？

把点按照 $x$ 排序，然后DP，然后斜率优化即可。

时间复杂度 $O(n\log 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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline ll read()
{
	ll x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=1e6+5;
struct node{
	ll x,y,a;
	friend inline bool operator<(const node &A,const node &B)
	{
		return A.x<B.x;
	}
}p[N];
ll f[N],ans;
int n,st[N],l,r;
inline db K(int x,int y)
{
	return (db)(f[y]-f[x])/(p[y].x-p[x].x);
}
int main()
{
	n=read();
	fo(i,1,n)
	{
		p[i].x=read(),p[i].y=read(),p[i].a=read();
	}
	sort(p+1,p+n+1);
	l=1; r=0;
	fo(i,1,n)
	{
		f[i]=p[i].x*p[i].y-p[i].a;
		for(;l<r&&K(st[l],st[l+1])>=p[i].y;l++);
		if(l<=r) f[i]=max(f[i],p[i].x*p[i].y-p[i].a+f[st[l]]-p[st[l]].x*p[i].y);
		for(;l<r&&K(st[r-1],i)>K(st[r-1],st[r]);r--);
		st[++r]=i;
		ans=max(ans,f[i]);
	}
	printf("%lld",ans);
	return 0;
}