首页 > 代码库 > BZOJ 4499 线性函数
BZOJ 4499 线性函数
SB线段树。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 200050 #define mod 1000000007 using namespace std; long long n,m,x[maxn],y[maxn],tot=0,ls[maxn<<2],rs[maxn<<2],root; long long type,a,b,c,d; char s[2]; struct line { long long k,b; line (long long k,long long b):k(k),b(b) {} line () {} }val[maxn<<2]; line comb(line x,line y) { line now; now.k=x.k*y.k%mod;now.b=(x.b*y.k%mod+y.b)%mod; return now; } void build(long long &now,long long left,long long right) { now=++tot; if (left==right) { val[now]=line(x[left],y[left]); return; } long long mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); val[now]=comb(val[ls[now]],val[rs[now]]); } void modify(long long now,long long left,long long right,long long pos,line x) { if (left==right) {val[now]=x;return;} long long mid=(left+right)>>1; if (pos<=mid) modify(ls[now],left,mid,pos,x); else modify(rs[now],mid+1,right,pos,x); val[now]=comb(val[ls[now]],val[rs[now]]); } line ask(long long now,long long left,long long right,long long l,long long r) { if ((left==l) && (right==r)) return val[now]; long long mid=(left+right)>>1; if (r<=mid) return ask(ls[now],left,mid,l,r); else if (l>=mid+1) return ask(rs[now],mid+1,right,l,r); else return comb(ask(ls[now],left,mid,l,mid),ask(rs[now],mid+1,right,mid+1,r)); } int main() { scanf("%lld%lld",&n,&m); for (long long i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]); build(root,1,n); for (long long i=1;i<=m;i++) { scanf("%s",s); if (s[0]==‘M‘) { scanf("%lld%lld%lld",&a,&b,&c); modify(root,1,n,a,line(b,c)); } else { scanf("%lld%lld%lld",&a,&b,&c); line now=ask(root,1,n,a,b); printf("%lld\n",(now.k*c%mod+now.b)%mod); } } return 0; }
BZOJ 4499 线性函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。