比赛 |
2025.5.24 |
评测结果 |
WWWWWWWWWW |
题目名称 |
魔法传输 |
最终得分 |
0 |
用户昵称 |
李奇文 |
运行时间 |
0.963 s |
代码语言 |
C++ |
内存使用 |
7.07 MiB |
提交时间 |
2025-05-24 11:16:31 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Maxn=1e5+5,mod=1000000007;
struct tree {
ll l,r,tb,lazy;
} f[Maxn*4];
ll n,m;
void build(ll p,ll l,ll r) {
f[p].l=l,f[p].r=r;
if(l==r) {
f[p].tb=0;
return;
}
ll mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
f[p].tb=f[p*2].tb+f[p*2+1].tb;
return;
}
void pushlazy(ll p){
if(!f[p].lazy){
return;
}else{
ll lp=p*2,rp=p*2+1;
f[lp].lazy+=f[p].lazy;
f[rp].lazy+=f[p].lazy;
ll mid=(f[p].l+f[p].r)>>1;
f[lp].tb+=(mid-f[p].l+1)*f[p].lazy%mod;
f[rp].tb+=(f[p].r-mid)*f[p].lazy%mod;
f[p].lazy=0;
}
return;
}
ll ptt(ll p,ll x,ll y) {
if(x<=f[p].l&&f[p].r<=y) {
return f[p].tb;
}
pushlazy(p);
ll mid=(f[p].l+f[p].r)/2,sum=0;
if(x<=mid) {
sum=(sum%mod+ptt(p*2,x,y)%mod)%mod;
}
if(mid<y) {
sum=(sum%mod+ptt(p*2+1,x,y)%mod)%mod;
}
return sum;
}
void change(ll p,ll l,ll r,ll k){
if(l<=f[p].l&&f[p].r<=r){
f[p].lazy+=k;
f[p].tb+=(f[p].r-f[p].l+1)*k;
return;
}else{
pushlazy(p);
ll mid=(f[p].l+f[p].r)/2;
if(l<=mid) change(p*2,l,r,k);
if(mid<r) change(p*2+1,l,r,k);
f[p].tb=f[p*2].tb+f[p*2+1].tb;
}
return;
}
void ddc(ll p,ll x,ll k) {
if(f[p].l==f[p].r) {
f[p].tb-=k;
return;
}
ll mid=(f[p].l+f[p].r)/2;
if(x<=mid) {
ddc(p*2,x,k);
} else {
ddc(p*2+1,x,k);
}
f[p].tb=f[p*2].tb+f[p*2+1].tb;
return;
}
int main() {
freopen("magics.in","r",stdin);
freopen("magics.out","w",stdout);
std::cin>>n>>m;
build(1,1,n);
for(ll i=1; i<=m; i++) {
ll x,k;
char c;
std::cin>>c>>x;
if(c=='C') {
std::cin>>k;
change(1,x,k,1);
ddc(1,k+1,k-x+1);
} else {
std::cout<<ptt(1,1,x)<<endl;
}
}
return 0;
}