1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NPOS = -1;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a < M ? a : (a -= M); } //假如a和b都已经在同余系内，就不必取模了，取模运算耗时很高
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //考虑a和b不在同余系内甚至为负数的情况
ll mul(ll a, ll b) const { return add(a * b, M); }
/*
ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); }
ll mul(ll a, ll b) const //无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%M，需要a<M且b<M，可以调用时手动取模
{
ll c = a / SM, d = b / SM;
a %= SM, b %= SM;
ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
}
*/
ll pow(ll a, ll b) const
{
ll r = 1;
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数
/*
ll inv(ll a) const //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
{
ll x, y, d = gcd(a, M, x, y);
return d == 1 ? add(x, M) : -1; //return pow(a, phi(M) - 1);
}
vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
{
vector<ll> ans;
ll x, y, d = gcd(a, M, x, y);
if (b % d)
return ans;
ans.push_back(mul((b / d) % (M / d), x));
for (ll i = 1; i < d; ++i)
ans.push_back(add(ans.back(), M / d));
return ans;
}
*/
ll log(ll a, ll b) const
{
unordered_map<ll, ll> x;
for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
if (!x.count(e))
x[e] = i;
for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
if (x.count(b))
return i * SM + x[b];
return -1;
}
} M(1e9 + 7);
struct SegmentTree
{
struct Seg
{
int l, r;
ll suma, sumb, ans;
void upd(ll bdd, ll add)
{
M.qadd(ans, M.mul(sumb, add));
M.qadd(suma, M.mul(r - l + 1, add));
M.qadd(ans, M.mul(suma, bdd));
M.qadd(sumb, M.mul(r - l + 1, bdd));
}
friend Seg up(const Seg &lc, const Seg &rc)
{
Seg fa = lc;
fa.r = rc.r;
M.qadd(fa.suma, rc.suma);
M.qadd(fa.sumb, rc.sumb);
M.qadd(fa.ans, rc.ans);
return fa;
}
};
struct Node : Seg
{
int lc, rc;
ll bdd, add;
};
vector<Node> v;
SegmentTree(int l, int r) { build(l, r); }
void build(int l, int r)
{
int rt = v.size();
v.push_back({});
v[rt].Seg::operator=({l, r, 0, 0, 0});
v[rt].lc = v[rt].rc = NPOS;
v[rt].bdd = 0, v[rt].add = 0;
}
void down(int rt)
{
int m = v[rt].l + v[rt].r >> 1;
if (v[rt].lc == NPOS)
v[rt].lc = v.size(), build(v[rt].l, m);
if (v[rt].rc == NPOS)
v[rt].rc = v.size(), build(m + 1, v[rt].r);
upd(v[v[rt].lc].l, v[v[rt].lc].r, v[rt].bdd, v[rt].add, v[rt].lc);
upd(v[v[rt].rc].l, v[v[rt].rc].r, v[rt].bdd, v[rt].add, v[rt].rc);
v[rt].bdd = 0, v[rt].add = 0;
}
void upd(int l, int r, ll bdd, ll add, int rt = 0)
{
if (l <= v[rt].l && v[rt].r <= r)
return M.qadd(v[rt].bdd, bdd), M.qadd(v[rt].add, add), v[rt].upd(bdd, add);
down(rt);
if (r <= v[v[rt].lc].r)
upd(l, r, bdd, add, v[rt].lc);
else if (l >= v[v[rt].rc].l)
upd(l, r, bdd, add, v[rt].rc);
else
upd(l, v[v[rt].lc].r, bdd, add, v[rt].lc), upd(v[v[rt].rc].l, r, bdd, add, v[rt].rc);
v[rt].Seg::operator=(up(v[v[rt].lc], v[v[rt].rc]));
}
Seg ask(int l, int r, int rt = 0)
{
if (l <= v[rt].l && v[rt].r <= r)
return v[rt];
down(rt);
if (r <= v[v[rt].lc].r)
return ask(l, r, v[rt].lc);
if (l >= v[v[rt].rc].l)
return ask(l, r, v[rt].rc);
return up(ask(l, v[v[rt].lc].r, v[rt].lc), ask(v[v[rt].rc].l, r, v[rt].rc));
}
};
int main()
{
int n, m;
scanf("%d%d", &n, &m);
SegmentTree t(1, n);
for (int i = 0, l, r, x; i < m; ++i)
{
char s[9];
scanf("%s%d%d", s, &l, &r);
if (s[0] == '?')
printf("%lld\n", t.ask(l, r).ans);
else
scanf("%d", &x), t.upd(l, r, s[0] != '*' ? x : 0, s[0] == '*' ? x : 0);
}
}
|