鸡排销售查询系统(线段树)

描述

传送门:SHUOJ232

看着虫虫重写的铁路购票系统使用非常方便,xyiyy想要虫虫帮忙实现一个鸡排销售情况查询的系统,主要是针对XX路上销售情况的查询。已知在XX路上,从东往西共有$n$个住户,标号分别为$1,2…n-1,n$,初始时,所有住户购买的鸡排数都为$0$。现只要求实现两个非常简单的功能,就是更新销售信息和查询$[L,R]$区间内有几位住户购买的鸡排数为$3$的倍数。系统命令的表示如下:

  1. 0 L R,表示标号在$[L,R]$范围内的所有住户都购买了一块鸡排。
  2. 1 L R,询问标号在$[L,R]$范围内购买的鸡排数目为$3$的倍数的住户数。

现有已知有$Q$条该系统的操作记录,但虫虫很忙,xyiyy希望你能帮忙实现这个系统。

输入

第一行包含两个数字$n$,$Q$,表示住户的数目,$1≤n,Q≤100000$。

接下来$Q$行由三个数字组成,$0$,$L$,$R$或者$1$,$L$,$R$,分别表示两种操作,$1≤L,R≤n$。

输出

对于每一次的询问操作输出购买的鸡排数目为$3$的倍数的住户数

样例输入

1
2
3
4
5
6
7
8
4 7
1 1 4
0 2 3
0 2 4
1 1 1
0 1 4
1 4 4
1 1 4

样例输出

1
2
3
4
4
1
0
2

思路

  • 最开始老是想着单点更新才能统计某一个数到底是不是三的倍数,实际上我们可以维护区间内模$3$后余$0,1,2$的数的个数分别用$v0[],v1[],v2[]$维护,那么每次询问就是查询$v0[rt]$。
  • 然后我们需要解决的就是区间更新的信息如何维护。手动模拟一下可以发现,当一个区间整体加上$1$的时候,$v0[],v1[],v2[]$的值会发生一个循环(即余$2$的会变成余$1$的,以此类推……),整体加上$2$也是类似,整体加$3$则不变。这样就可以延迟更新了~
  • 具体实现的细节见代码。

代码

1
2
3
4
#define lson rt << 1
#define rson rt << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1e5 + 5;
ll v0[maxn << 2], v1[maxn << 2], v2[maxn << 2], addv[maxn << 2];

inline void add1(int rt)
{
int tmp = v0[rt];
v0[rt] = v1[rt];
v1[rt] = v2[rt];
v2[rt] = tmp;
}

inline void add2(int rt)
{
int tmp = v0[rt];
v0[rt] = v2[rt];
v2[rt] = v1[rt];
v1[rt] = tmp;
}

void pushup(int rt)
{
v0[rt] = v0[lson] + v0[rson];
v1[rt] = v1[lson] + v1[rson];
v2[rt] = v2[lson] + v2[rson];
}

void build (int l, int r, int rt)
{
v1[rt] = v2[rt] = 0;
if (l == r)
{
v0[rt] = 1;
return;
}
int m = (l + r) >> 1;
build(Lson);
build(Rson);
pushup(rt);
}

void pushdown(int rt)
{
if (addv[rt] == 0) return;
addv[lson] += addv[rt];
addv[rson] += addv[rt];
if (addv[rt] % 3 == 1)
{
add1(lson);
add1(rson);
}
if (addv[rt] % 3 == 2)
{
add2(lson);
add2(rson);
}
addv[rt] = 0;
}

void update(int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R)
{
addv[rt]++;
add1(rt);
return;
}
pushdown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, Lson);
if (m < R) update(L, R, Rson);
pushup(rt);
}

ll query(int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R)
return v0[rt];
pushdown(rt);
int m = (l + r) >> 1;
ll ans = 0;
if (L <= m) ans += query(L, R, Lson);
if (m < R) ans += query(L, R, Rson);
return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
fastin
int n, q, c, l, r;
cin >> n >> q;
build(1, n, 1);
while (q--)
{
cin >> c >> l >> r;
if (c)
cout << query(l, r, 1, n, 1) << endl;
else
update(l, r, 1, n, 1);
}
return 0;
}
捐助作者
0%