USACO19DEC Pt

T1

长度为 $n$ 的序列上有 $m$ 个区间，每个区间有一个权值，若一组区间存在一种顺序使得：按顺序依次插入区间的过程中，每个区间都不被已有的区间的并集完全包含，则这组区间合法。求所有合法区间组的最大权值和。
$n\leq300,m\leq\frac{n(n+1)}{2}$

看到数据范围是 $300$ 当然要想区间dp啊。。
我们考虑一组合法的区间是如何产生的，这有助于帮助我们确定状态和转移。
对于一组 $k$ 个合法区间的最后一个区间，它一定至少覆盖了之前没有覆盖过的一个位置 $p$ 。这时前 $k-1$ 个区间就有不能覆盖 $p$ 位置的限制，于是它们一定会被划分为 $p$ 左侧的区间和 $p$ 右侧的区间，因为不可能跨过。那么对于左侧和右侧的区间就都缩小了范围，成为了一个子问题。
那么其实状态和转移就很显然了：
$f[i][j]$ 表示选的区间全部包含在 $i$ 到 $j$ 位置内时的最大权值和。
$f[i][j]=\max_{i\leq k\leq j}f[i][k-1]+f[k+1][j]+mx[i][k][j]$
其中 $mx[i][k][j]=\max_{i\leq l\leq k\leq r\leq j}a[l][r]$ ，即包含在 $[i,j]$ 内且包含 $k$ 的区间权值的最大值。这个东西也可以 $n^3$ 求（利用 $l,r$ 范围的单调性）。

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n,m,a[N][N],mx[N][N][N],f[N][N];
void cmax(int &x,int y){y>x?x=y:0;}
int main(){
    freopen("pieaters.in","r",stdin);
    freopen("pieaters.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,x,l,r;i<=m;i++)scanf("%d%d%d",&x,&l,&r),cmax(a[l][r],x);
    for(int i=n;i;i--)for(int j=i;j<=n;j++)for(int k=i;k<=j;k++)
        mx[i][k][j]=max(a[i][j],max(mx[i+1][k][j],mx[i][k][j-1]));
    for(int i=n;i;i--)for(int j=i;j<=n;j++)for(int k=i;k<=j;k++)
        cmax(f[i][j],f[i][k-1]+mx[i][k][j]+f[k+1][j]);
    printf("%d\n",f[1][n]);
}

T2

有一棵有根树，初始所有节点都没有颜色，有两种操作。
1.把 $x$ 子树内所有节点染上颜色 $c$ （颜色不会覆盖）
2. $z$ 节点的颜色数设为 $f(z)$ ，求 $x$ 子树内所有 $z$ 的 $f(z)$ 求和。
$n,q\leq 10^5$

这个题我一直在想常规数据结构的做法，什么动态开点线段树之类的TAT

考虑 $x$ 子树内的贡献可以分为两类。一类是全部染成了某种颜色 $c$ ，这时贡献为这样的颜色数乘上 $x$ 子树的大小。还有一类是有些点被染成了颜色 $c$ ，有些点没被染。因为每次染一棵子树，所以这样的颜色的形态应该是 $x$ 子树内的子树。

这样好像还是没法维护，关键在于可能一个点被重复染好多次，这时就不知该如何统计了。

考虑因为每种颜色在树上的形态都是一些子树，所以只有这些子树的根才有用（称为关键节点）。我们考虑维护这些关键节点。

每次给 $x$ 的子树染 $c$ 颜色时，如果发现它在 $c$ 的某个关键节点子树内，那么它一定不是关键节点，这次操作也没有用，可以直接无视。否则我们去找 $x$ 子树内有多少 $c$ 的关键节点，把它们撤销掉，把 $x$ 设为关键节点。

有这些关键节点有什么用呢？这时就有一个性质，每个节点到根的路径上固定颜色的关键节点最多只有一个，且关键节点子树内不会有同颜色的关键节点。所以我们就可以简单地用树状数组维护上面两类贡献啦！
时间复杂度 $O(q(logn+logq))$ ，因为每一次修改操作最多是插入一个关键节点和被撤销一次关键节点。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+50;
int n,q,ver[N*2],nxt[N*2],head[N],tot,dfn[N],rr[N],cnt,idfn[N],st[N],tp,sz[N];
int read(){
	int x=0,c;
	while(!isdigit(c=getchar()));
	while(isdigit(c))x=x*10+c-48,c=getchar();
	return x;
}
struct node{
	LL f[N];
	void add(int x,int y){for(;x<=n;x+=x&-x)f[x]+=y;}
	LL ask(int x){int y=0;for(;x;x-=x&-x)y+=f[x];return y;}
}F,G;
set<int>s[N];
set<int>::iterator it;
void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void dfs(int x,int ff){
	idfn[dfn[x]=++cnt]=x;
	for(int i=head[x],y;i;i=nxt[i])
		if((y=ver[i])!=ff)dfs(y,x);
	rr[x]=cnt;sz[x]=rr[x]-dfn[x]+1;
}
void upd(int x,int y){
	F.add(dfn[x],y);F.add(rr[x]+1,-y);
	G.add(dfn[x],y*sz[x]);
}
int main(){
	freopen("snowcow.in","r",stdin);
	freopen("snowcow.out","w",stdout);
	n=read();q=read();
	for(int i=1,x,y;i<n;i++){
		x=read();y=read();
		add(x,y);add(y,x);
	}
	dfs(1,0);
	for(int i=1,op,x,c;i<=q;i++){
		op=read();x=read();
		if(op==1){
			c=read();it=s[c].upper_bound(dfn[x]);
			if(it!=s[c].begin()){if(rr[idfn[*--it]]>=dfn[x])continue;it++;}
			while(it!=s[c].end()&&*it<=rr[x])
				upd(idfn[*it],-1),st[++tp]=*it++;
			upd(x,1);s[c].insert(dfn[x]);
			while(tp)s[c].erase(st[tp--]);
		}
		else printf("%lld\n",F.ask(dfn[x])*sz[x]+G.ask(rr[x])-G.ask(dfn[x]));
	}
	return 0;
}

T3

这个题确实很神。~~lgm jiangly都没做出来~~

$d_i(a)$ 表示对排列 $a$ 建出小根的笛卡尔树后第 $i$ 个数在树上的深度（到根的节点数）。给定 $n,k$ ，对所有 $i$ 求出：所有逆序对数为 $k$ 的排列 $a$ 的 $d_i(a)$ 之和。
$n\leq 300,k\leq\frac{n(n-1)}{2}$

考虑笛卡尔树的性质，点 $i$ 的每个祖先 $j$ 都满足 $a_j$ 是 $i$ 到 $j$ 子区间的最小值（画图易得）。
所以有这么一个式子：

d_i(a)=1+\sum_{1\le j<i}(a[j] == \min(a[j\ldots i]))+\sum_{i<j\le n}(a[j] == \min(a[i\ldots j]))

这三部分分别考虑。
对于 $1$ 的求和？
就是求出逆序对数为 $k$ 的排列个数。这是一个经典的前缀和优化的dp。
对于第二部分的求和：
考虑每个 $(j,i)$ 对的贡献吧。。
如果固定了 $j,i$ ，我们要求出有多少个排列满足逆序对数为 $k$ 且 $a[j] == \min(a[j\ldots i])$ 。
骚操作来了：

考虑用生成函数来理解求逆序对数的背包dp过程。加入第 $i$ 个数时可以产生 $0$ 到 $i-1$ 个逆序对，于是式子就显然了。

F=\prod_{i=1}^n\sum_{j=0}^{i-1}x^j

这个是不加任何限制的排列关于逆序对的生成函数。
而上面相当于是限制了 $a[j]<min(a[j+1\dots i])$ ，即 $j$ 不能与 $j+1\dots i$ 产生逆序对，这时我们试图修改我们的生成函数。
式子变为：

(\prod_{i=1}^n\sum_{j=0}^{i-1}x^j)\cdot\frac{1}{\sum_{j=0}^{i-j}x^j}

这是为什么？我们考虑更换元素加入的顺序，变成先加入 $a[i],a[i-1]...a[j+1]$ ，接着加入 $a[j]$ 的时候不能产生任何逆序对，然后再正常加入其他的元素。

发现这个东西可以表示成

F\cdot f(i-j)

于是我们处理出全局的生成函数 $F$ ，再对 $d\in[1,n-1]$ 求出 $F\cdot f(d)$ ，然后把这些贡献加到对应的位置上即可。
对于第三部分的求和类似，只是 $g(d)=f(d)\cdot x^d$ ，因为是限制了第 $j$ 个元素插入时要与前面 $j-i$ 个元素都产生逆序对。

所以我们现在的问题变成了要快速求出这些 $F\cdot f(d)$ 。因为我们已经可以用前缀和优化dp求出 $F$ ，现在的问题就是给 $F$ 成一个逆元。我们如果直接求逆需要带一个log。想要去掉这个log需要注意到乘逆元就是前缀和dp的逆变换，直接倒着推回去即可。这里用到了背包计数删物品时倒着减掉贡献的思想。用生成函数的思想可以更好地理解为什么这样做是对的，因为乘法具有交换率。

这道题告诉我们，对于生成函数推的题目，不一定要用多项式科技，也可以观察式子的性质直接dp可能会更优。比如这里做到了 $O(n)$ 的“多项式乘法”。

于是时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。
事实证明 $O(n^3)$ 都会被卡常，带log更是不可能的qwq

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n,k,a[N*N],s[N*N],sz,mod,b[N],c[N],d[N*N];
void add(int x){
	sz+=x-1;
	for(int i=1;i<=sz;i++)s[i]=(s[i-1]+a[i])%mod;
	for(int i=1;i<=sz;i++)a[i]=(s[i]-(i>=x?s[i-x]:0))%mod;
}
void sub(int x){
	for(int i=1;i<=sz;i++)
		a[i]=(0ll+a[i]-s[i-1]+(i>=x?s[i-x]:0))%mod,
		s[i]=(s[i-1]+a[i])%mod;
}
int main(){
	freopen("treedepth.in","r",stdin);
	freopen("treedepth.out","w",stdout);
	scanf("%d%d%d",&n,&k,&mod);a[0]=s[0]=1;
	for(int i=1;i<=n;i++)add(i);
	memcpy(d,a,sizeof(a));
	for(int i=1;i<=min(n-1,k);i++)
		memcpy(a,d,sizeof(a)),sub(i+1),b[n-i]=a[k-i];
	for(int i=n-1;i;i--)(b[i]+=b[i+1])%=mod;
	for(int i=1;i<n;i++)
		memcpy(a,d,sizeof(a)),sub(i+1),c[i+1]=(a[k]+c[i])%mod;
	for(int i=1;i<=n;i++)printf("%d",((0ll+b[i]+c[i]+d[k])%mod+mod)%mod),i<n&&putchar(' ');
	return 0;
}

Prutekoi's blog

T1

T2

T3

伯努利数