牛客白月賽6 F発電(線分樹)
2204 ワード
テーマリンク:https://www.nowcoder.com/acm/contest/136/F
線分樹は区間の積を求めます.ポイント更新(1つの数で割る)時は必ずその逆を掛けます.そうでないとWAは続きません.どうやって分かりましたか?
線分樹は区間の積を求めます.ポイント更新(1つの数で割る)時は必ずその逆を掛けます.そうでないとWAは続きません.どうやって分かりましたか?
#include
#include
#define lson l ,mid ,t << 1
#define rson mid + 1 ,r ,t << 1 | 1
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll sum[50000*4+100];
ll inv(ll a) {
if(a==1) return 1;
return inv(MOD%a)*(MOD-MOD/a)%MOD;
}
void Pushup(int t) {
sum[t] = ((sum[t<<1] % MOD) * (sum[t<<1|1] % MOD)) % MOD;
}
void BuidTree(ll l ,ll r ,ll t) {
sum[t] = 1;
if(l == r) {
sum[t] %= MOD;
return;
}
ll mid = (l + r) >> 1;
BuidTree(lson);
BuidTree(rson);
Pushup(t);
}
void Update(ll l ,ll r ,ll t ,ll a ,ll b, ll flag) {
if(l == r) {
if(flag == 1) {
sum[t] = (sum[t]*b)%MOD;
} else {
sum[t] = (sum[t]*inv(b))%MOD;
}
return;
}
ll mid = (l + r) >> 1;
if(a <= mid) Update(lson ,a ,b, flag);
else Update(rson ,a ,b, flag);
Pushup(t);
}
ll Query(ll l ,ll r ,ll t ,ll a ,ll b) {
if(a <= l && b >= r)
return sum[t];
ll mid = (l + r) >> 1;
ll ans = 1;
if(a <= mid) ans = Query(lson ,a ,b) % MOD;
if(b > mid) ans *= Query(rson ,a ,b) % MOD;
return ans % MOD;
}
ll Scan() {
ll res = 0, flag = 0;
char ch;
if ((ch = getchar()) == '-') {
flag = 1;
}else if(ch >= '0' && ch <= '9') {
res = ch - '0';
}
while ((ch = getchar()) >= '0' && ch <= '9'){
res = res * 10 + (ch - '0');
}
return flag ? -res : res;
}
int main () {
ll n, m, a, b, c;
scanf("%lld %lld" ,&n, &m);
BuidTree(1 ,n ,1);
while(m--) {
a = Scan();
b = Scan();
c = Scan();
if(a == 1) {
Update(1 ,n ,1 ,b ,c, a);
} else if(a == 2) {
Update(1 ,n ,1 ,b ,c, a);
} else if(a == 3) {
printf("%lld
" ,Query(1 ,n ,1 ,b ,c) % MOD);
}
}
return 0;
}