区间修改 区间求和
分析
一道大模拟题
#include <iostream>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define met(a , b) memset(a , b , sizeof a);
#define pb push_back
using namespace std;
typedef long long LL ;
typedef pair<int , int> PII;
template <typename T> T chMa(T &x, T y) { if (y > x) x = y; return x; }
template <typename T> T chMi(T &x, T y) { if (y < x) x = y; return x; }
const int N = 100010, mod = 10007;
int n, m;
struct SEG{
#define lc u << 1
#define rc u << 1 | 1
struct Node{
int l, r;
LL s[3];
LL add, mul, lazy;
}tr[N * 4];
void build (int u, int l, int r)
{
tr[u] = {l, r, 0, 0, 0, 0, 1, 0};
if (l == r) return;
int mid = l + r >> 1;
build (lc, l, mid), build (rc, mid + 1, r);
pushup(u);
}
void pushup(int u)
{
for (int i = 0; i < 3; i++)
tr[u].s[i] = (tr[lc].s[i] + tr[rc].s[i]) % mod;
}
void pushdown(int u, int add, int mul, int lazy)
{
LL len = tr[u].r - tr[u].l + 1;
if (lazy)
{
LL c = lazy % mod;
tr[u].s[0] = c * len % mod;
tr[u].s[1] = c * c * len % mod;
tr[u].s[2] = c * c * c * len % mod;
tr[u].add = 0, tr[u].mul = 1, tr[u].lazy = lazy;
}
if (mul != 1)
{
LL c = mul % mod;
tr[u].s[0] *= c;
tr[u].s[1] *= c * c;
tr[u].s[2] *= c * c * c;
tr[u].mul *= c; tr[u].mul %= mod;
tr[u].add *= c; tr[u].add %= mod;
for (int i = 0; i < 3; i++) tr[u].s[i] %= mod;
}
if (add)
{
LL c = add % mod;
tr[u].s[2] += 3 * c * tr[u].s[1] % mod + 3 * c * c * tr[u].s[0] % mod + c * c * c * len % mod;
tr[u].s[1] += 2 * c * tr[u].s[0] % mod + c * c * len % mod;
tr[u].s[0] += c * len % mod;
tr[u].add += c; tr[u].add %= mod;
for (int i = 0; i < 3; i++) tr[u].s[i] %= mod;
}
}
void pushdown(int u)
{
auto &p = tr[u];
pushdown(lc, p.add, p.mul, p.lazy);
pushdown(rc, p.add, p.mul, p.lazy);
p.add = p.lazy = 0;
p.mul = 1;
}
void modify (int u, int l, int r, int c, int op)
{
if (tr[u].l >= l && tr[u].r <= r)
{
if (op == 1) pushdown(u, c, 1, 0);
else if (op == 2) pushdown(u, 0, c, 0);
else pushdown(u, 0, 1, c);
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify (lc, l, r, c, op);
if (r > mid) modify(rc, l, r, c, op);
pushup(u);
}
}
LL query (int u, int l, int r, int p)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].s[p - 1];
int mid = tr[u].l + tr[u].r >> 1;
LL res = 0;
pushdown(u);
if (l <= mid) res = query(lc, l, r, p);
if (r > mid) res += query(rc, l, r, p), res %= mod;
return res;
}
}seg;
void solve()
{
seg.build(1, 1, n);
while (m--)
{
int op, l, r, c;
cin >> op >> l >> r >> c;
// bug4(op, l, r, c);
if (op == 4) cout << seg.query(1, l, r, c) << endl;
else seg.modify(1, l, r, c, op);
}
}
int main()
{
// ios::sync_with_stdio(0);
// int T = 1;
// for(int turn = 1 ; turn <= T ; turn++)
while (cin >> n >> m)
{
if (!n && !m) break;
solve();
}
}