比赛 |
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;
}