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;
}