Description
小C最近在学习线性函数，线性函数可以表示为：f(x) = kx + b。现在小C面前有n个线性函数fi(x)=kix+bi ，他对这n个线性函数执行m次操作，每次可以：
1.M i K B 代表把第i个线性函数改为：f i(x)=kx+b 。
2.Q l r x 返回f r(f r-1(...f l(x))) mod 10^9+7 。
Input
第一行两个整数n, m (1 <= n, m <= 200,000)。
接下来n行，每行两个整数ki, bi。
接下来m行，每行的格式为M i K B或者Q l r x。
Output
对于每个Q操作，输出一行答案。
Sample Input
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
Sample Output
1825 17 978 98
HINT
1 <= n, m <= 200,000，0 <= k, b, x < 1000,000,007
除草增加自信ing。。。
用棵线段树维护一下一次函数参数就行啦，合并也很简单。
#include#include #include #include #include #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define ren for(int i=first[x];i;i=next[i])using namespace std;const int BufferSize=1<<16;char buffer[BufferSize],*head,*tail;inline char Getchar() { if(head==tail) { int l=fread(buffer,1,BufferSize,stdin); tail=(head=buffer)+l; } return *head++;}inline int read() { int x=0,f=1;char c=Getchar(); for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; return x*f;}typedef long long ll;const int maxn=200010;const int mod=1000000007;struct Node { int k,b; Node operator + (const Node& B) const { return (Node){(ll)k*B.k%mod,((ll)B.k*b+B.b)%mod}; }}T[maxn*4];int n;void build(int o,int l,int r) { if(l==r) T[o]=(Node){read(),read()}; else { int mid=l+r>>1,lc=o<<1,rc=lc|1; build(lc,l,mid);build(rc,mid+1,r); T[o]=T[lc]+T[rc]; }}void update(int o,int l,int r,int p) { if(l==r) T[o]=(Node){read(),read()}; else { int mid=l+r>>1,lc=o<<1,rc=lc|1; if(p<=mid) update(lc,l,mid,p); else update(rc,mid+1,r,p); T[o]=T[lc]+T[rc]; }}Node ans;void query(int o,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) ans=ans+T[o]; else { int mid=l+r>>1,lc=o<<1,rc=lc|1; if(ql<=mid) query(lc,l,mid,ql,qr); if(qr>mid) query(rc,mid+1,r,ql,qr); }}int main() { int n=read(),m=read(); build(1,1,n); rep(i,1,m) { char c=Getchar(); while(!isalpha(c)) c=Getchar(); if(c=='M') update(1,1,n,read()); else { int ql=read(),qr=read(),v=read(); ans=(Node){1,0};query(1,1,n,ql,qr); printf("%d\n",((ll)v*ans.k+ans.b)%mod); } } return 0;}