LGP6144题解

冲了50分钟外加10分钟厕所才冲出来，请问我还有救吗。

看上去像是金组题目的加强版，实际上是金组题目的魔改版。

还是考虑像弱化版那样按照左端点排序，并且记录答案的 \(0\sim k\) 次幂和。

然后考虑新增的贡献。仍然是右端点不超过自身构成的贡献。但是我们将这部分写成一个集合 \(|S|\)，我们在这里约定后面枚举的 \(x\) 都属于这个 \(|S|\)。那么贡献就是 \(\sum(x+1)^k=\sum_{i=0}^k\binom{k}{i}\sum x^k\)。

这一部分很平凡，但是我们应该怎么维护贡献呢。。。

我们只要把这一部分线段拉出来做一遍原问题不就好了

考虑将这些线段丢到一个序列上，按照左端点排序。（别忘了右端点是不超过某个值的）

假设对于第 \(i\) 条线段，多出的贡献是 \(f_i\)，那么这一车线段的答案应该是 \(\sum_{i=1}^m2^{m-i}f_i\)。

然后是加入一条新的线段。

首先先把这条线段的贡献直接丢到序列上。

这条线段的贡献是不是“右端点不大于最外层枚举线段左端点且不大于自身左端点的线段”构成个集合的贡献？

看一眼，好像就是最外层问题的贡献啊？直接插进来。

对于自身对其他线段的贡献，找到右端点，然后在序列上二分出一个后缀，满足这些后缀的左端点都比加入的新线段大。

然后让这个后缀的贡献全部加上“自身贡献+1”就行了。

对于系数，只需要每次乘上 \(2\) 就好了。

然后怎么把这些线段放到正确的位置上，只需对右端点排序就行了。

复杂度 \(O(k^2n+kn\log n)\)，可以通过。

upd:上面下饭了

考虑右端点不超过左端点的答案，其实只需要把每个节点的答案丢到右端点上即可。。。

然后统计的时候直接做和。。。

但是这样会漏掉右端点在 \([l,r]\) 中的部分。这部分是可以直接加到答案里面去的。

然后右端点在 \((r,2n]\) 的线段，明显使其答案翻了倍。

所以只需要单点修改，区间乘，区间和即可。。。

#include<cstdio>

#include<vector>

typedef unsigned ui;

const ui M=1e5+5,mod=1e9+7;

ui n,k,C[11][11],l[M],r[M],num[M],pw2[M],id[M<<1],delta[M][11];

ui f[11],g[11],tag[M<<3],sum[M<<3][11];bool v1[M<<1],v2[M<<1],vis[M<<3];

inline void update(const ui&u){

	for(ui i=0;i<=k;++i)sum[u][i]=(sum[u<<1][i]+sum[u<<1|1][i])%mod;

}

inline void pushdown(const ui&u){

	if(tag[u]){

		tag[u<<1]+=tag[u];tag[u<<1|1]+=tag[u];

		for(ui i=0;i<=k;++i)sum[u<<1][i]=1ull*pw2[tag[u]]*sum[u<<1][i]%mod;

		for(ui i=0;i<=k;++i)sum[u<<1|1][i]=1ull*pw2[tag[u]]*sum[u<<1|1][i]%mod;

		tag[u]=0;

	}

}

inline void Mdf1(const ui&u,const ui&x,const ui&L=0,const ui&R=(n<<1)){

	if(L==R){

		for(ui i=0;i<=k;++i)sum[u][i]=f[i];return;

	}

	const ui mid=L+R>>1;pushdown(u);

	if(x<=mid)Mdf1(u<<1,x,L,mid);

	else Mdf1(u<<1|1,x,mid+1,R);

	update(u);

}

inline void Mdf2(const ui&u,const ui&x,const ui&L=0,const ui&R=(n<<1)){

	if(x>R)return;

	if(x<=L){

		for(ui i=0;i<=k;++i)sum[u][i]=2*sum[u][i]%mod;++tag[u];return;

	}

	const ui mid=L+R>>1;pushdown(u);

	Mdf2(u<<1,x,L,mid);Mdf2(u<<1|1,x,mid+1,R);

	update(u);

}

inline void Qry(const ui&u,const ui&l,const ui&r,const ui&L=0,const ui&R=(n<<1)){

	if(l>R||L>r)return;

	if(l<=L&&R<=r){

		for(ui i=0;i<=k;++i)f[i]=(f[i]+sum[u][i])%mod;return;

	}

	const ui mid=L+R>>1;pushdown(u);

	Qry(u<<1,l,r,L,mid);Qry(u<<1|1,l,r,mid+1,R);

	update(u);

}

signed main(){

	ui ans(0);

	scanf("%u%u",&n,&k);pw2[0]=1;C[0][0]=1;f[0]=1;Mdf1(1,0);

	for(ui i=1;i<=n;++i)pw2[i]=2*pw2[i-1]%mod;

	for(ui i=1;i<=k;++i){

		C[i][0]=1;

		for(ui j=1;j<=i;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

	}

	for(ui i=1;i<=n;++i)scanf("%u%u",l+i,r+i),id[l[i]]=i;

	for(ui i=1;i<=(n<<1);++i)if(id[i]){

		const ui&Id=id[i],L=l[Id],R=r[Id];

		for(ui i=0;i<=k;++i)f[i]=0;Qry(1,0,L-1);

		for(ui i=0;i<=k;++i){

			unsigned long long sum(0);

			for(ui j=0;j<=i;++j)sum+=1ull*C[i][j]*f[j];

			g[i]=sum%mod;

		}

		for(ui i=0;i<=k;++i)f[i]=0;Qry(1,L,R-1);

		for(ui i=0;i<=k;++i)f[i]=(f[i]+g[i])%mod;

		Mdf1(1,R);Mdf2(1,R+1);

	}

	printf("%u",sum[1][k]);

}

巴特西

LGP6144题解

upd:上面下饭了

最新文章

热门文章