CF1140

Posted on | Edited on | Views:

$Div.2$

CF1140C Playlist

  • 将元素按 $b$ 从大到小排序,然后从后往前依次加入,每加入一个元素时它的 $b$ 都是当前最小的.
  • 此时需要钦定选择这个元素作为最小的 $b$ ,并在已有元素中选出 $k-1$ 个 $t$ 值最大的.
  • 这个东西用个堆维护一下当前前 $k-1$ 大的 $t$ 值就好了.

CF1140D Minimum Triangulation

  • 肯定会有一个很直观的想法:全部都以 $1$ 为一个顶点,然后 $(1,2,3),(1,3,4) \dots (1,n-1,n)$ 这样来剖.

  • 这样做的确是正确的,即权值一定是最小的.为什么呢?

  • 考虑若有 $x<y$ ,那么把方案 $(1,n,x),(n,x,y)$ 换成 $(1,n,y),(1,x,y)$ ,总权值会减小.

  • 于是可以直接将 $x$ 换到 $n-1$ ,然后将 $(1,n-1,n)$ 这个三角形直接割掉,对剩下的 $n-1$ 边形继续做上述操作.

  • 这样做的话,所有的方案就一定是 $(1,2,3),(1,3,4) \dots (1,n-1,n)$ 这样的形式了.

另一个做法是 $O(n^3)$ 的区间 $dp$ ?

CF1140E Palindrome-less Arrays

  • 任意位置都不能出现长度 $\geq 3$ 的奇回文串,其实也就等价于不出现长度为 $3$ 的回文串.
  • 也就是说总有 $a_i\not=a_{i+2}$ .这样显然可以奇偶分开算,将两个序列各自的合法方案数目乘起来.
  • 把奇(偶)数位置拿出来,就是要求相邻两个位置都不同的方案数.
  • 把连续的一段 $-1$ 看成一块,考虑每一块 $(a,-1,-1,\dots,-1,b)$ 怎么算方案数.首尾可能会出现没有 $a,b$ 的情况,枚举第一个/最后一个元素,算中间的就可以了(其实这部分细节挺多的?).所以下面都假定 $a,b$ 存在.
  • 每块的方案数只与 $-1$ 的个数 $x$ 以及 $a,b$ 是否相等有关.记 $f(x)$ 表示 $a\not =b$ 时的方案数, $g(x)$ 表示相等时.
  • 若 $x$ 为奇,枚举最中间的元素,就有:
    $g(x)=g(x/2)^2+(k-1)f(x/2)^2,f(x)=2f(x/2)g(x/2) + (k-2)f(x/2)^2$ .
  • 若 $x$ 为偶,枚举第一个元素即可将 $x$ 变为奇.
    $g(x)=(k-1)f(x-1),f(x)=g(x-1)+(k-2)f(x-1)$ .
  • 边界显然有 $f(0)=1,g(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
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=2e5+10;
int k;
int f[MAXN],g[MAXN];
int F(int);
int G(int);
int calc(int l,int r,int *a,int n)
{
	if(r>=n)
	{
		int len=r-l-1,res=1;
		if(l<0)
			--len,res=k;
		if(len==0)
			return res;
		int fx=F(len-1),gx=G(len-1);
		return mul(res,add(gx,mul(k-1,fx)));
	}
	if(l<0)
	{
		if(r-l==1)
			return 1;
		int fx=F(r-l-2),gx=G(r-l-2);
		return add(gx,mul(k-1,fx));
	}
	return a[l]==a[r]?G(r-l-1):F(r-l-1);
}
int solve(int *a,int n)
{
	int res=1,lst=-1;
	for(int i=0;i<n;++i)
	{
		if(a[i]==-1)
			continue;
		res=mul(res,calc(lst,i,a,n));
		lst=i;
	}
	res=mul(res,calc(lst,n,a,n));
	return res;
}
int n,a[MAXN],b[MAXN],siza,sizb;
int main()
{
	n=read();
	k=read();
	for(int i=1;i<=n;++i)
	{
		f[i]=g[i]=-1;
		int x=read();
		if(i&1)
			a[siza++]=x;
		else
			b[sizb++]=x;
	}
	int ans=1;
	ans=mul(ans,solve(a,siza));
	if(ans)
		ans=mul(ans,solve(b,sizb));
	cout<<ans<<endl;
	return 0;
}
int F(int x)
{
	if(!x)
		return 1;
	if(f[x]!=-1)
		return f[x];
	int &res=f[x];
	if(x&1)
	{
		res=mul(2,mul(F(x>>1),G(x>>1)));
		res=add(res,mul(k-2,mul(F(x>>1),F(x>>1))));
		return res;
	}
	else
		return res=add(G(x-1),mul(k-2,F(x-1)));
	
}
int G(int x)
{
	if(!x)
		return 0;
	if(g[x]!=-1)
		return g[x];
	int &res=g[x];
	if(x&1)
	{
		res=mul(G(x>>1),G(x>>1));
		res=add(res,mul(k-1,mul(F(x>>1),F(x>>1))));
		return res;
	}
	else
		return res=mul(k-1,F(x-1));
}

CF1140F Extending Set of Points

  • 可以发现它的 $Extend$ 操作就是将每三个点加一个点补成一个矩形,直到每个可补的位置都有点为止.这里的三个点必须要有两个点的连线是平行于坐标轴的.
  • 给每个 $x,y$ 坐标都建一个节点,加入 $(x,y)$ 就将对应的两个节点连起来,容易发现每个连通分量的贡献为不同的 $x$ 坐标个数乘上不同的 $y$ 坐标个数,此时的答案就是每个连通分量的贡献之和.
  • 这个东西用个并查集维护,插入点很简单,删除点似乎不太好做?此时可以想到线段树分治,用线段树给每个点影响的时间区间 $(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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
typedef pair<int,int> pii;
const int MAXN=6e5+10;
int siz[MAXN],sizx[MAXN],sizy[MAXN];
#define tot(x) 1LL*sizx[x]*sizy[x]
int fa[MAXN];
int Find(int x)
{
	return x==fa[x]?x:Find(fa[x]);
}
pii stk[MAXN];
int tp=0;
ll ans=0;
void Merge(int x,int y)
{
	x=Find(x),y=Find(y);
	if(x==y)
		return;
	if(siz[x]<siz[y])
		swap(x,y);
	ans-=tot(x);
	ans-=tot(y);
	fa[y]=x;
	siz[x]+=siz[y],sizx[x]+=sizx[y],sizy[x]+=sizy[y];
	ans+=tot(x);
	stk[++tp]=make_pair(x,y);
}
void Split(int x,int y)
{
	ans-=tot(x);
	fa[y]=y;
	siz[x]-=siz[y],sizx[x]-=sizx[y],sizy[x]-=sizy[y];
	ans+=tot(x);
	ans+=tot(y);
}
int n;
map<pii,int> mp;
vector<pii> Tree[MAXN<<1];
set<pii> s;
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
void modifiy(int o,int l,int r,int L,int R,pii c)
{
	if(l>R || L>r)
		return;
	if(L<=l && r<=R)
	{
		root.push_back(c);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)
		modifiy(o<<1,l,mid,L,R,c);
	if(R>mid)
		modifiy(o<<1|1,mid+1,r,L,R,c);
}
void solve(int o,int l,int r)
{
	int curt=tp;
	int sz=root.size();
	for(int i=0;i<sz;++i)
		Merge(root[i].first,root[i].second);
	if(l==r)
		printf("%I64d ",ans);
	else
	{
		int mid=(l+r)>>1;
		solve(o<<1,l,mid);
		solve(o<<1|1,mid+1,r);
	}
	while(tp>curt)
	{
		Split(stk[tp].first,stk[tp].second);
		--tp;
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		int x=read(),y=read()+300001;
		fa[x]=x,siz[x]=1,sizx[x]=1;
		fa[y]=y,siz[y]=1,sizy[y]=1;
		pii k=make_pair(x,y);
		if(s.find(k)==s.end())
		{
			mp[k]=i;
			s.insert(k);
		}	
		else
		{
			modifiy(1,1,n,mp[k],i-1,k);
			mp[k]=0;
			s.erase(k);
		}	
	}
	set<pii>::iterator it;
	for(it=s.begin();it!=s.end();++it)
	{
		pii k=*it;
		modifiy(1,1,n,mp[k],n,k);
	}
	solve(1,1,n);
	return 0;
}