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
2 2
1 1
1 1
1
1 1 1
样例输出 #1
1
样例 #2
样例输入 #2
2 2
1 2
2 3
2
1 2 2
2 2 2
样例输出 #2
4
4
样例 #3
样例输入 #3
4 2
1 2 3 4
1 2 3 4
1
4 1 1
样例输出 #3
66
提示
样例 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;
}