FJWC2016 线性代数 【线段树】

tonyfang posted @ 2016年2月20日 20:28 in 随笔 with tags C++ OI , 580 阅读
# 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;
}
pavzi.com 说:
2024年1月18日 16:48

Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


登录 *


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