0%

「2020.5.25训练赛」 Tyher的烦恼

题意

给你 $n(n <= 10^9)$ 个盒子,初始全为空。有 $m(m<=50000)$ 个操作:

  1. 将编号为 $L$ 到 $R$ 的盒子里的石头数量变为 $(X-L+1)\times A \bmod B$,$X$ 为盒子编号;
  2. 查询 $L$ 到 $R$ 的盒子的石头总数。

题解

看到区间操作以及 $10^9$ 这么鬼畜的数据范围,就能想到要用珂朵莉树。然而我们发现,查询时我们要计算这么个东西:

这里只对每一项取模,而并没有对和取模,这就比较难办了。

我们考虑去掉取模:

后面那一项直接用类欧几里得算法求就可以了。总的时间复杂度在随机数据下为 $O(n\log n \log \log n)$

Code

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
#include <bits/stdc++.h>
#define fl first
#define fr second
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 100000 + 5;

struct Node
{
LL l, r;
mutable LL v, a, b, q;
Node(const LL &l, const LL &r, const LL &v, const LL &a, const LL &b)
: l(l), r(r), v(v), a(a), b(b) {}
inline bool operator < (const Node &o) const { return l < o.l; }
};

typedef set<Node>::iterator iter;

int n, m;
set<Node> odt;

iter split(LL x)
{
if (x > n) return odt.end();
iter it = --odt.upper_bound(Node{x, 0, 0, 0, 0});
if (it->l == x) return it;
LL l = it->l, r = it->r;
LL v = it->v, a = it->a, b = it->b;
odt.erase(it);
odt.insert(Node(l, x - 1, v, a, b));
return odt.insert(Node(x, r, ((v + x - l) % b + b) % b, a, b)).first;
}

void assign(LL l, LL r, LL v, LL a, LL b)
{
iter itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
odt.insert(Node(l, r, v, a, b));
}

LL f(LL a, LL b, LL c, LL n)
{
if (!a) return (b / c) * (n + 1);
if (a >= c || b >= c)
{
return f(a % c, b % c, c, n) + (n * (n + 1) / 2) * (a / c) + (n + 1) * (b / c);
}
LL m = (a * n + b) / c;
return n * m - f(c, c - b - 1, a, m - 1);
}

inline LL Get(LL v, LL a, LL b)
{
return v * (v + 1) / 2 * a - b * f(a, 0, b, v);
}

LL Query(LL l, LL r)
{
iter itr = split(r + 1), itl = split(l);
LL res = 0;
for (; itl != itr; ++itl)
{
res += Get(itl->v + itl->r - itl->l, itl->a, itl->b);
res -= Get(itl->v - 1, itl->a, itl->b);
}
return res;
}

int main()
{
scanf("%d%d", &n, &m);
odt.insert(Node{1, n, 0, 0, 1});
while (m--)
{
int opt, l, r, a, b;
scanf("%d", &opt);
if (opt == 1)
{
scanf("%d%d%d%d", &l, &r, &a, &b);
assign(l, r, 1, a, b);
}
else
{
scanf("%d%d", &l, &r);
printf("%lld\n", Query(l, r));
}
}
return 0;
}