T1 线段树优化DP

[COCI2015-2016#1] RELATIVNOST

题目描述

您是一位计数大师，有一天您的朋友 Luka 出了一道问题来刁难您。

Luka 是一位勤劳的画家，他的画很好，所以会有 \(n\) 个人来买他的画。

画分两种，黑白画与彩色画。

Luka 十分勤劳，所以他有无穷多的画。

Luka 讨厌出售黑白画，所以他希望至少有 \(c\) 个人会买走一张彩色画。

第 \(i\) 个人会至多购买 \(a_i\) 张彩色画，\(b_i\) 张黑白画，且它们会至少购买一幅画。

但是，客户们只能单独购买彩色画或黑白画。

客户们会不断改变 \(a_i\) 与 \(b_i\)，这种改变会持续 \(q\) 次。

客户以 \(1\sim n\) 编号。

您需要求出在每次改变之后，Luka 会有几种方案满足所有需求。

为了防止输出太大，Luka 只需要您告诉他方案数 \(\bmod\ 10^4+7\) 的值。

输入格式

第一行为两个整数 \(n,c\)。

第二行为 \(n\) 个整数 \(a_i\)。

第三行为 \(n\) 个整数 \(b_i\)。

第四行为一个整数 \(q\)。

接下来 \(q\) 行，一行三个整数 \(p_i,a_{p_i},b_{p_i}\)，第 \(i\) 行表示标号 \(p_i\) 的顾客将 \(a_i\) 和 \(b_i\) 更换成 \(a_{p_i}\) 和 \(b_{p_i}\)。

输出格式

共 \(q\) 行，一行一个整数，第 \(i\) 行的值表示进行了第 \(i\) 次改变后，满足条件的方案数 \(\bmod\ 10^4+7\) 的值。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

4
4

样例 #3

样例输入 #3

样例输出 #3

提示

样例 1 说明

第一次改变后，我们只有唯一的一种方案，就是向两位用户都出售一张彩色画。

数据范围及限制

对于 \(30\%\) 的数据，保证 \(n,q\le 10^3\)。
对于 \(100\%\) 的数据，保证 \(1\le n,q\le 10^5\)，\(1\le c\le 20\)，\(1\le a_i,b_i,a_{p_i},b_{p_i}\le 10^9\)，\(1\le p_i\le n\)。

说明

本题满分 \(140\) 分。

本题译自 Croatian Open Competition in Informatics 2015/2016 Contest #1 T5 RELATIVNOST。

分析

线段树，DP
这题能想到线段树，基本就对了一半了
每个人作为根节点，有彩画或黑白画两种可能
选彩色为 \(1\)
选黑白为 \(0\)
要最终选到 \(c\) 个，只需要让起始节点有 \(c\) 个即可
在 \(pushup\) 的过程中
\(dp[i][j]\) 定义为在节点 \(i\) 选了 \(j\) 个的方案数
有 \(dp[u][min(i+j,c)] += dp[u<<1][i]*dp[u<<1|1][j]\)
那么最终答案就是 \(dp[1][c]\)

细节

本题空间限制很小，复杂度为 \(O(c^2q logN)\) 手写取模

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>

using namespace std;

const int mod = 10007;
const int N = 150010;

template<typename T>void read(T &x)
{
	x=0;char c=getchar();T neg=0;
	while(!isdigit(c))neg|=!(c^'-'),c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(neg)x=(~x)+1;
}
template<typename T>void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar((x-x/10*10)^48);
	return ;
}
int n,c;
int b[N],a[N];
struct node{
	int l,r;
	int dp[21];
}re[N<<1];

void push_up(int x)
{
	for(int i=0;i<=c;i++) re[x].dp[i]=0;
	for(int i=0;i<=c;i++)
		for(int j=0;j<=c;j++)
			re[x].dp[min(i+j,c)]=(re[x].dp[min(i+j,c)]+1ll*re[x<<1].dp[i]*re[x<<1|1].dp[j])-(re[x].dp[min(i+j,c)]+1ll*re[x<<1].dp[i]*re[x<<1|1].dp[j])/mod*mod;
}

void build(int x,int l,int r)
{
	re[x].l=l; re[x].r=r;
	if(l==r)
	{
		re[x].dp[0]=b[l];
		re[x].dp[1]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	push_up(x);
}
void upd(int x,int pos,int a,int b)
{
	int l=re[x].l, r=re[x].r;
	if(l==r) 
	{
		re[x].dp[0]=b;// or dont pick
		re[x].dp[1]=a;// pick
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) upd(x<<1,pos,a,b);
	else upd(x<<1|1,pos,a,b);
	push_up(x);
}
signed main()
{
	read(n); read(c);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(b[i]);;
	build(1,1,n);
	int p;
	read(p);
	for(int i=1;i<=p;i++)
	{
		int q,A,B;
		read(q);
		read(A),read(B);
		
		upd(1,q,A,B);
		wr(re[1].dp[c]),putchar('\n');
	}
	return 0;
}

10.17 - llwwll - 博客园