首页 > 代码库 > 一次函数

一次函数


【题目描述】
fqk 退役后开始补习文化课啦, 于是他打开了数学必修一开始复习
函数, 他回想起了一次函数都是f(x)=k*x+b的形式, 现在他给了你 n 个
一次函数fi(x)=ki*x+bi,然后将给你 m 个操作, 操作将以如下格式给出:
1.M  i k b ,把第 i 个函数改为fi(x)=k*x+b
2.Q  l r x ,询问 fr(fr-1(……f(1)))mod 1000000007 的值。
【输入格式】
第一行两个整数 n , m ,代表一次函数的数量和操作的数量。
接下来 n 行,每行两个整数,表示 ki,bi
接下来 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

/*
  观察式子,我们可以知道f2(f1(x))=k2(k1*x+b1)*b2,
展开式子得:ans=k2*k1*x+k2*b1*b2,所以新的k=k2*k1,b=k2*b1*b2,
利用这个原理建立两棵线段树,一棵维护k,一棵维护b。
*/ #include<cstdio> #include<iostream> #define N 200010 #define mod 1000000007 #define ll long long #define lson l,mid,now*2 #define rson mid+1,r,now*2+1 #define lc now*2 #define rc now*2+1 #ifdef unix #define LL "%lld\n" #else #define LL "%I64d\n" #endif using namespace std; ll K[N*4],B[N*4];int n,m; int read() { int num=0,flag=1;char c=getchar(); while(c<0||c>9){if(c==-)flag=-1;c=getchar();} while(c>=0&&c<=9){num=num*10+c-0;c=getchar();} return num*flag; } void insert(int l,int r,int now,int pos,int k,int b) { if(l==r) { K[now]=(ll)k;B[now]=(ll)b;return; } int mid=(l+r)/2; if(pos<=mid)insert(lson,pos,k,b); else insert(rson,pos,k,b); K[now]=K[lc]*K[rc]%mod;B[now]=(K[rc]*B[lc]%mod+B[rc])%mod; } ll kquery(int l,int r,int now,int x,int y) { if(l>=x&&r<=y)return K[now]; int mid=(l+r)/2; ll k1=1,k2=1; if(x<=mid)k1=kquery(lson,x,y); if(y>mid)k2=kquery(rson,x,y); return k1*k2%mod; } ll bquery(int l,int r,int now,int x,int y) { if(l>=x&&r<=y)return B[now]; int mid=(l+r)/2; ll b1=0,b2=0; if(x<=mid)b1=bquery(lson,x,y); if(y>mid) { b2=bquery(rson,x,y); b1*=kquery(rson,x,y); } return (b1%mod+b2)%mod; } int main() { freopen("fx.in","r",stdin); freopen("fx.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++) { int k=read(),b=read(); insert(1,n,1,i,k,b); } for(int i=1;i<=m;i++) { char c;cin>>c; if(c==M) { int p=read(),k=read(),b=read(); insert(1,n,1,p,k,b); } else { int l=read(),r=read(),x=read(); ll k=kquery(1,n,1,l,r); ll b=bquery(1,n,1,l,r); printf(LL,(k*x%mod+b)%mod); } } return 0; }

 

一次函数