首页 > 代码库 > 一次函数(好难的一次函数)
一次函数(好难的一次函数)
一次函数
（fx.c/cpp/pas)
【题目描述】
fqk 退役后开始补习文化课啦， 于是他打开了数学必修一开始复习
函数， 他回想起了一次函数都是 b kx x f ? ? ) ( 的形式， 现在他给了你 n 个
一次函数
i i i
b x k x f ? ? ) ( ， 然后将给你 m 个操作， 操作将以如下格式给出：
M . 1 i k b ，把第 i 个函数改为 b kx x f i ? ? ) ( 。
Q . 2 l r x ，询问 ))) ( (... (
1
x f f f
l r r ?
mod 1000000007 的值。
【输入格式】
第一行两个整数 n ， m ，代表一次函数的数量和操作的数量。
接下来 n 行，每行两个整数，表示
i
k ，
i
b 。
接下来 m 行，每行的格式为 M i k b 或 Q l r x 。
【输出格式】
对于每个操作 Q ，输出一行表示答案。
【输入样例】
5 5
4 2
3 6
5 7
2 6
7 5
Q 1 5 1
Q 3 3 2
M 3 10 6
Q 1 4 3
Q 3 4 4
【输出样例】
1825
17
978
98
【数据范围】
对于 % 30 的数据， 1000 , ? m n 。
对于 % 100 的数据， 1000000007 , , , 200000 , ? ? x b k m n 。
【时空限制】
对于每个测试点，时间限制为 s 2 ,空间限制为 MB 512 。
思路：
刚开始先看数据范围（好习惯）
发现这是个暴力过不了的题
于是开始边推公式边码代码
推了一个小时公式终于推了出来
但是爆零了！
因为这个题里有一个mod条件
大于这个mod值就必须被mod
但是我的公式里有用到除法
所以就被整数不能被零除这种错误给RE了
最后还是ylf大神讲的思路
正解是线段树
题目里的操作M和Q正符合线段树的单点修改和区间查询
所以我开始着手写线段树
线段树要维护两个值
hyxzc告诉我要用数组比结构体要快
但是我还是用的结构体
在维护线段树的值得时候
维护k和b
具体是这样维护的
k2*(k1*x+b1)+b2
可以化成这种形式
k2*k1*x+k2*b1+b2
这样我们就可以得到新的值
k3=k2*k1,b3=k2*b1+b2
k3，b3就是一个小区间的值
这样我们就可以推出l到r的k于b
来，上代码：
#include<cmath>#include<cstdio>#include<iostream>#define mod 1000000007using namespace std;struct node { long long int l,r,kl,b;};struct node tree[10000001],cur;long long int n,m,jkl,ll,rr,dis;char ch,ch1;void qread(long long int &x){ x=0,jkl=1;ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘) jkl=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(int)(ch-‘0‘);ch=getchar();} x*=jkl;}void tree_up(long long int k){ tree[k].kl=(tree[k<<1].kl*tree[k<<1|1].kl)%mod; tree[k].b=((tree[k<<1].b*tree[k<<1|1].kl)%mod+tree[k<<1|1].b)%mod;}void tree_build(long long int k,long long int l,long long int r){ tree[k].l=l,tree[k].r=r; if(l==r) { qread(tree[k].kl),qread(tree[k].b); return ; } long long int mid=(l+r)>>1; tree_build(k<<1,l,mid),tree_build(k<<1|1,mid+1,r); tree_up(k);}void tree_change(long long int k,long long int to,long long int nk,long long int nb){ if(tree[k].l==tree[k].r&&tree[k].l==to) { tree[k].kl=nk,tree[k].b=nb; return ; } long long int mid=(tree[k].l+tree[k].r)>>1; if(to<=mid) tree_change(k<<1,to,nk,nb); else tree_change(k<<1|1,to,nk,nb); tree_up(k);}struct node tree_sum(long long int k,long long int l,long long int r){ if(l==tree[k].l&&r==tree[k].r) return tree[k]; long long int mid=(tree[k].l+tree[k].r)>>1; if(l>mid) return tree_sum(k<<1|1,l,r); else if(r<=mid) return tree_sum(k<<1,l,r); else { struct node now1,now2; now1=tree_sum(k<<1,l,mid); now2=tree_sum(k<<1|1,mid+1,r); now1.b=((now2.kl*now1.b)%mod+now2.b)%mod; now1.kl=(now1.kl*now2.kl)%mod; return now1; }}int main(){ qread(n),qread(m); tree_build(1,1,n); for(long long int i=1;i<=m;i++) { //scanf("%c %lld%lld%lld",&ch1,&ll,&rr,&dis); scanf("%c ",&ch1); qread(ll),qread(rr),qread(dis); if(ch1==‘M‘) tree_change(1,ll,rr,dis); else { cur=tree_sum(1,ll,rr); dis=((dis*cur.kl)%mod+cur.b)%mod; cout<<dis<<endl; } } return 0;}
附,祭奠我那逝去的公式=.=
：
#include<cstdio>#include<cstdlib>#include<iostream>#define mod 1000000007using namespace std;struct node { long long int k,b;};struct node function[2000002];long long int n,m,jkl,l,r,dis,cur,kol;long long int sumk[2000002],sumb[2000002],sumbb[2000002];char ch,ch1;bool ok=false;void qread(long long int &x){ x=0,jkl=1;ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘) jkl=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(int)(ch-‘0‘);ch=getchar();} x*=jkl;}void change(){ for(long long int j=1;j<=n;j++) { sumk[j]=(sumk[j-1]*function[j].k)%mod; //sumb[j]=((sumb[i-1]*function[i].k)%mod+function[i].b)%mod; } for(long long int j=1;j<=n;j++) { sumb[j]=(((function[j].b*sumk[n])%mod)/sumk[j])%mod; sumbb[j]=sumbb[j-1]+sumb[j]; } ok=false;}int main(){ sumk[0]=1; qread(n),qread(m); sumk[n+1]=1; for(long long int i=1;i<=n;i++) { qread(function[i].k),qread(function[i].b); sumk[i]=(sumk[i-1]*function[i].k)%mod; //sumb[i]=((sumb[i-1]*function[i].k)%mod+function[i].b)%mod; sumb[i]=function[i].b; } for(long long int i=1;i<=n;i++) { sumb[i]=(((sumb[i]*sumk[n])%mod)/sumk[i])%mod; sumbb[i]=sumbb[i-1]+sumb[i]; } for(long long int i=1;i<=m;i++) { scanf("%c",&ch1),qread(l),qread(r),qread(dis); //cout<<l<<" "<<r<<" "<<dis<<" "<<endl; if(ch1==‘M‘) { function[l].k=r,function[l].b=dis,ok=true; /*for(long long int j=1;j<=n;j++) { sumk[j]=(sumk[j-1]*function[j].k)%mod; //sumb[j]=((sumb[i-1]*function[i].k)%mod+function[i].b)%mod; } for(long long int j=1;j<=n;j++) { sumb[j]=(((function[j].b*sumk[n])%mod)/sumk[j])%mod; sumbb[j]=sumbb[j-1]+sumb[j]; }*/ } else { if(ok) change(); cur=dis; cur=((cur*sumk[r]%mod)/sumk[l-1])%mod; //cout<<cur<<endl; //kol=(sumb[r]-sumb[l-1]); /*if(sumk[n]/sumk[r]==0){ cout<<n<<" "<<r<<endl; cout<<sumk[n]<<" "<<sumk[r]<<endl; system("pause"); }*/ kol=((sumbb[r]-sumbb[l-1])/(sumk[n]/sumk[r])); //cout<<n<<" "<<r<<endl; //cout<<sumk[n]<<" "<<sumk[r]<<endl; //cout<<sumk[n]/sumk[r]<<endl<<(sumbb[r]-sumbb[l-1])<<endl<<kol<<endl; cur=(cur+kol)%mod; cout<<cur<<endl; } } return 0;}
一次函数(好难的一次函数)