比赛 20160421x 评测结果 WWWWWWWWWW
题目名称 魔法传输 最终得分 0
用户昵称 Fmuckss 运行时间 0.674 s
代码语言 C++ 内存使用 14.02 MiB
提交时间 2016-04-21 16:14:24
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const int lcy = 1000000007;
const int maxn = 1e5+10;

int n, m; 

class seg_ment_tree {
private:
	struct node{
		int l, r;
		LL v;
		int lazy;
	}ns[maxn << 3];
public:
	void build(int i, int l, int r) {
		if(l == r) {
			ns[i].l = l;
			ns[i].r = r;
			ns[i].v = 0;
			return;
		}
		ns[i].l = l, ns[i].r = r;
		build(i << 1, l, (l+r) >> 1);
		build(i << 1 | 1, ((l+r) >> 1) + 1, r);
	}
	
	inline void update(int i) {
		if(!ns[i].l) return;
		ns[i].v = ns[i << 1].v + ns[i << 1 | 1].v;
		ns[i].v %= lcy;
	}
	
	inline void make_add(int i, int t) {
		if(!ns[i].l) return;
		ns[i].v += t * (ns[i].r - ns[i].l + 1);
		ns[i].v %= lcy;
		ns[i].lazy += t;
	}
	
	inline void push_down(int i) {
		if(!ns[i].l) return;
		if(ns[i].lazy) {
			make_add(i << 1, ns[i].lazy);
			make_add(i << 1 | 1, ns[i].lazy);
			
			ns[i].lazy = 0;
		}
	}
	
	int query(int i, int l, int r) {
		push_down(i);
		if(ns[i].l == l && ns[i].r == r) { return ns[i].v; }
		else if(r <= ns[i << 1].r) return query(i << 1, l, r);
		else if(l >= ns[i << 1 | 1].l) return query(i << 1 | 1, l, r);
		else if(l <= ns[i << 1].r && r >= ns[i << 1 | 1].l) return (query(i << 1, l, ns[i << 1].r) + 
																	query(i << 1 | 1, ns[i << 1 | 1].l, r)) % lcy;
		update(i);
	}
	
	void change(int i, int l, int r, int t) {
		push_down(i);
		if(ns[i].l == l && ns[i].r == r) { make_add(i, t); return; }
		else if(r <= ns[i << 1].r) change(i << 1, l, r, t);
		else if(l >= ns[i << 1 | 1].l) change(i << 1 | 1, l, r, t);
		else if(l <= ns[i << 1].r && r >= ns[i << 1 | 1].l) change(i << 1, l, ns[i << 1].r, t), 
															change(i << 1 | 1, ns[i << 1 | 1].l, r, t);
		update(i);
	}
}st;

inline char get_han() {
	char tmp = getchar();
	while(tmp != 'C' && tmp != 'Q') tmp = getchar();
	return tmp;
}

inline void solve() {
	scanf("%d %d", &n, &m);
	st.build(1, 1, n);
	int l, r;
	char han;
	for(int i = 1; i <= m; i++) {
		han = get_han();
		if(han == 'Q') {
			scanf("%d", &r);
			printf("%d\n", st.query(1, 1, r));
		} else {
			scanf("%d %d", &l, &r);
			st.change(1, l, r, 1);
		}
	}
}

int main() {
	freopen("magics.in", "r", stdin);
	freopen("magics.out", "w", stdout);
	solve();
	return 0;
}