FJWC2016 线性代数 【线段树】

tonyfang posted @ 2016年2月20日 20:28 in 随笔 with tags C++ OI , 414 阅读
# include <stdio.h>

using namespace std;

typedef long long ll;
const int M = 200010, XdsM = 2000100;
int n, m, k[M], b[M];
const ll MOD=1e9+7;

inline int read() {
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0' || ch>'9') {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9') {
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*f;
}

struct segt {
	ll k,b;
	int l,r;
}T[XdsM];

inline void pushup(int x) {
	T[x].k=(T[2*x+1].k*T[2*x].k)%MOD;
	T[x].b=(T[2*x+1].k*T[2*x].b%MOD+T[2*x+1].b)%MOD;
}

inline void build(int l,int r,int x) {
	T[x].l=l,T[x].r=r;
	if(l==r) {
		T[x].k=k[l]%MOD;
		T[x].b=b[l]%MOD;
		return;
	}
	int mid=l+r>>1;
	build(l,mid,2*x);
	build(mid+1,r,2*x+1);
	pushup(x);
}

inline void modify(int pos,int x,int ks,int bs) {
	int l=T[x].l,r=T[x].r;
	if(l==r) {
		T[x].k=ks%MOD;
		T[x].b=bs%MOD;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) modify(pos,2*x,ks,bs);
	if(pos>mid) modify(pos,2*x+1,ks,bs);
	pushup(x);
}

ll ansK=1,ansB=0;
inline void query(int L,int R,int x) {
	int l=T[x].l,r=T[x].r;
	if(L<=l && r<=R) {
		ansB=(ansB+ansK*T[x].b%MOD)%MOD;
		ansK=(ansK*T[x].k)%MOD;
		return;
	}
	int mid=l+r>>1;
	if(R<=mid) query(L,R,2*x);
	else if(L>=mid+1) query(L,R,2*x+1);
	else {
		query(mid+1,R,2*x+1);
		query(L,mid,2*x);
	} 
}

int main() {
	
	freopen("func.in", "r", stdin);
	freopen("func.out", "w", stdout);
	
	n=read(), m=read();
	for (int i=1; i<=n; ++i) k[i]=read(), b[i]=read();
	build(1,n,1);
	char opt[5]; int i,kx,bx,l,r,x;
	while(m--) {
		scanf("%s",opt);
		if(opt[0]=='M') {
			i=read(), kx=read(), bx=read();
			modify(i,1,kx,bx);
		} else {
			ansK=1,ansB=0;
			l=read(), r=read(), x=read();
			query(l,r,1);
			ansK=ansK*x%MOD,ansK=(ansK+ansB)%MOD;
			printf("%d\n",(int)ansK);
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter