问题 F: Homework
题目描述
There are n children (numbered from 1 to n) learning the arithmetic operations, which include addition “+”, subtraction “−”, multiplication “×”, and division “÷” on rational numbers.
In the beginning, each child has a paper sheet with only a zero on it. Their teacher, Frank, will then give them q operations. The i-th operation consists of an operator ci and an integer xi . The children numbered Li , Li+1 , . . . , Ri have to append the operator ci and the integer xi to their paper sheets. After that, every child has an expression on their sheet to be evaluated.
For example, suppose that n = 3, q = 2, c1 is “+”, x1 = 1, L1 = 1, R1 = 2, c2 is “−”, x2 = 2,L2 = 2, R2 = 3. The expressions on the sheets are are 0 + 1, 0 + 1 − 2， 0 − 2 for children 1, 2 , 3, respectively.
Since Frank is really lazy and wants to verify the answers quickly, he asks you to calculate the sums of the values of all children’s expressions. Suppose that the value of the expression assigned to child i is ai/bi, then the value will be a × b−1 mod 10^9 + 7 instead, where b−1 denotes the integer satisfying b × b−1 ≡ 1 mod 10^9 + 7. If the sum is not in [0, 10^9 + 7), then the sum modulo 10^9 + 7 should be returned to Frank.
Note: The arithmetic operations has PEMDAS rule, that is, multiplications and divisions should be evaluated before evaluating additions and subtraction.
输入
The first line consists of two space-separated integers n and q. The i-th of the following q lines consists of four space-separated tokens Li , Ri , ci , xi . For the sake of convenience, * and / are used to represent the multiplication and the division operators, respectively.
输出
Output the number that you should return to Frank.
样例输入
3 2
1 2 + 1
2 3 - 2样例输出
1000000005提示
•1≤n≤10^5
•1≤q≤10^5
•Li,Ri∈[1,n]for all 1≤i≤q.
•ci∈{+,-,*,/}forall 1≤i≤q.
•For all 1≤i≤q,xi=0 implies that ci is not /.
•xi∈[0,10^9+7) for all 1≤i≤q.
题解
线段树+乘法逆元
由于有运算优先级，先算乘法后算加法，则可以在每一次区间加法或减法时 对区间求和 然后 清空区间，将区间全部的值更改为当前加法或减法的数值，乘法时直接在区间上做乘法，这样可以做到每次先算乘法，然后再算加法。最后再对全部的数组进行求和即可。
注：有运算优先级，例如样例：
10 4
4 7 + 6
5 7 + 9
4 7 * 2如果根据顺序模拟，则最后的结果应该为 6 2 + 15 2 + 15 2 + 15 2 =102 ，而如果进行优先级运算，则答案应该为： 6 2 + 6 + 9 2 + 6 + 9 2+ 6 + 9 2 = 84，答案应为后者，84。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll ksm(ll n, ll k)
{
ll sum1 = 1, sum2 = n;
while (k != 0)
{
if (k & 1)
sum1 = (sum1 * sum2) % mod;
sum2 = (sum2 * sum2) % mod;
k /= 2;
sum1 %= mod;
sum2 %= mod;
}
return sum1 % mod;
}
ll get_ny(ll n)
{
return ksm(n, mod - 2) % mod;
}
struct node
{
ll l, r, sum, size1, val, pro;
};
node tree[800500] = {0};
void build(ll l, ll r, ll t)
{
tree[t].l = l, tree[t].r = r, tree[t].size1 = r - l + 1, tree[t].val = -1, tree[t].pro = 1, tree[t].sum = 0;
if (l == r)
return;
ll mid = (l + r) / 2;
build(l, mid, 2 * t);
build(mid + 1, r, 2 * t + 1);
}
ll get_sum(ll t)
{
if (tree[t].val != -1)
return ((tree[t].size1 * tree[t].pro) %mod * tree[t].val) % mod;
else
return (tree[t].sum * tree[t].pro) % mod;
}
void push_up(ll t)
{
tree[t].sum = (get_sum(2 * t) + get_sum(2 * t + 1)) % mod;
}
void push_down(ll t)
{
if (tree[t].val != -1)
{
tree[2 * t].val = tree[t].val;
tree[2 * t + 1].val = tree[t].val;
tree[t].val = -1;
tree[2 * t].pro = 1;
tree[2 * t + 1].pro = 1;
}
tree[2 * t].pro *= tree[t].pro;
tree[2 * t].pro%=mod;
tree[2 * t + 1].pro *= tree[t].pro;
tree[2 * t + 1].pro%=mod;
tree[t].pro = 1;
}
void mul(ll t, ll l, ll r, ll x)
{
if (tree[t].l >= l && tree[t].r <= r)
{
tree[t].pro *= x;
tree[t].pro %= mod;
return;
}
push_down(t);
ll mid = (tree[t].l + tree[t].r) / 2;
if (l <= mid)
mul(2 * t, l, r, x);
if (r > mid)
mul(2 * t + 1, l, r, x);
push_up(t);
}
void back(ll t, ll l, ll r, ll k)
{
if (tree[t].l >= l && tree[t].r <= r)
{
tree[t].val = k;
tree[t].pro = 1;
return;
}
push_down(t);
ll mid = (tree[t].l + tree[t].r) / 2;
if (l <= mid)
back(2 * t, l, r, k);
if (r > mid)
back(2 * t + 1, l, r, k);
push_up(t);
}
ll query_sum(ll t, ll l, ll r)
{
if (tree[t].l >= l && tree[t].r <= r)
{
return tree[t].sum = get_sum(t) % mod;
}
push_down(t);
ll ans = 0;
ll mid = (tree[t].l + tree[t].r) / 2;
if (l <= mid)
ans += query_sum(2 * t, l, r) % mod;
ans %= mod;
if (r > mid)
ans += query_sum(2 * t + 1, l, r) % mod;
push_up(t);
return ans % mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n, q, l, r, x;
char c;
cin >> n >> q;
build(1, n, 1);
ll ans = 0;
for (ll i = 1; i <= q; i++)
{
cin >> l >> r >> c >> x;
if (c == '+')
{
ans += query_sum(1, l, r);
//cout<<ans<<endl;
back(1, l, r, x);
}
else if (c == '-')
{
ans += query_sum(1, l, r);
back(1, l, r, mod - x);
}
else if (c == '*')
mul(1, l, r, x);
else if (c == '/')
mul(1, l, r, get_ny(x));
}
ans += query_sum(1, 1, n);
ans = (ans % mod + mod) % mod;
cout << ans << endl;
}
错误代码（根据顺序求解）51分
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll mod = 1e9 + 7;
ll ksm(ll n, ll k)
{
ll sum1 = 1, sum2 = n;
while (k != 0)
{
if (k & 1)
sum1 = (sum1 * sum2) % mod;
sum2 = (sum2 * sum2) % mod;
k /= 2;
sum1 %= mod;
sum2 %= mod;
}
return sum1 % mod;
}
ll get_ny(ll n)
{
return ksm(n, mod - 2) % mod;
}
struct node
{
ll l, r, sum, size1, lazy_add, lazy_mul;
};
node tree[800500] = {0};
void build(ll l, ll r, ll t)
{
tree[t].l = l, tree[t].r = r, tree[t].size1 = r - l + 1, tree[t].lazy_mul = 1, tree[t].lazy_add = 0;
if (l == r)
return;
ll mid = (l + r) / 2;
build(l, mid, 2 * t);
build(mid + 1, r, 2 * t + 1);
}
void push_up(ll t)
{
tree[t].sum = (tree[2 * t + 1].sum + tree[2 * t].sum) % mod;
}
void push_down(ll t)
{
if (tree[t].lazy_mul != 1 || tree[t].lazy_add != 0)
{
tree[2 * t + 1].sum = ((tree[2 * t + 1].sum * tree[t].lazy_mul) % mod + (tree[2 * t + 1].size1 * tree[t].lazy_add) % mod) % mod;
tree[2 * t].sum = ((tree[2 * t].sum * tree[t].lazy_mul) % mod + (tree[2 * t].size1 * tree[t].lazy_add) % mod) % mod;
tree[2 * t + 1].lazy_mul = (tree[2 * t + 1].lazy_mul * tree[t].lazy_mul) % mod;
tree[2 * t].lazy_mul = (tree[2 * t].lazy_mul * tree[t].lazy_mul) % mod;
tree[2 * t + 1].lazy_add = ((tree[2 * t + 1].lazy_add * tree[t].lazy_mul) % mod + tree[t].lazy_add) % mod;
tree[2 * t].lazy_add = ((tree[2 * t].lazy_add * tree[t].lazy_mul) % mod + tree[t].lazy_add) % mod;
tree[2 * t + 1].sum %= mod;
tree[2 * t].sum %= mod;
tree[2 * t].lazy_add %= mod;
tree[2 * t + 1].lazy_add %= mod;
tree[2 * t].lazy_mul %= mod;
tree[2 * t + 1].lazy_mul %= mod;
tree[t].lazy_add = 0;
tree[t].lazy_mul = 1;
}
}
void add(ll t, ll l, ll r, ll x)
{
push_down(t);
if (tree[t].l >= l && tree[t].r <= r)
{
tree[t].lazy_add += x;
tree[t].lazy_add %= mod;
tree[t].sum = ((tree[t].sum * tree[t].lazy_mul) % mod + (tree[t].size1 * tree[t].lazy_add) % mod) % mod;
return;
}
ll mid = (tree[t].l + tree[t].r) / 2;
if (l <= mid)
add(2 * t, l, r, x);
if (r > mid)
add(2 * t + 1, l, r, x);
push_up(t);
}
void mul(ll t, ll l, ll r, ll x)
{
push_down(t);
if (tree[t].l >= l && tree[t].r <= r)
{
tree[t].lazy_mul *= x;
tree[t].lazy_mul %= mod;
tree[t].sum = ((tree[t].sum * tree[t].lazy_mul) % mod + (tree[t].size1 * tree[t].lazy_add) % mod) % mod;
return;
}
ll mid = (tree[t].l + tree[t].r) / 2;
if (l <= mid)
mul(2 * t, l, r, x);
if (r > mid)
mul(2 * t + 1, l, r, x);
push_up(t);
}
ll query_sum(ll t, ll l, ll r)
{
if (tree[t].l == l && tree[t].r == r)
{
return tree[t].sum % mod;
}
ll ans = 0;
ll mid = (tree[t].l + tree[t].r) / 2;
if (l <= mid)
ans += query_sum(2 * t, l, mid) % mod;
ans %= mod;
if (r > mid)
ans += query_sum(2 * t, mid, r) % mod;
return ans % mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n, q, l, r, x;
char c;
cin >> n >> q;
build(1, n, 1);
for (ll i = 1; i <= q; i++)
{
cin >> l >> r >> c >> x;
if (c == '+')
add(1, l, r, x);
else if (c == '-')
add(1, l, r, mod-x);
else if (c == '*')
mul(1, l, r, x);
else if (c == '/')
mul(1, l, r, get_ny(x));
}
ll ans = query_sum(1, 1, n);
ans = (ans % mod + mod) % mod;
cout << ans << endl;
}