[题解]HDU7059-Counting Stars

Posted on In

题意

本题是2021东北四省赛D-Lowbit 的强化版.

给出一个长度为\(n\)的数列\(raw[]\), 维护下列三种操作:

1 l r查询\(raw[l] + raw[l+1] + ... + raw[r]\)对\(998244353\)取模的值

2 l r对区间\([l,r]\)里的每个值分别减去其lowbit

3 l r对区间\([l,r]\)里的每个值分别加上其最高位的值

\(1 \leq n,q \leq 10^5\)

题解

容易发现对于操作2, 每个数\(a_i\)在减去最多\(\log a_i\)次后就会变成0. 因而我们暴力模拟这个过程, 同时用\(full[x] = 1\)表示该节点下的所有值全部为0, 在之后的操作2中将这种节点忽略即可.

对于操作3, 只需把最高位拆出来单独维护即可. 注意操作2会影响到拆出来的最高位.

代码

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
150
151
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10;//CHANGE IT!
const int maxm = maxn*2;
const int p = 998244353;//CHANGE IT!
int p2[maxn];
ll Pow(ll x,ll d){ll ta=1;if(d==0)return 1%p;x %= p;ll a=Pow(x,d/2);ta=a*a%p;if(d%2)ta=ta*x%p;return ta%p;}
struct Segtree{
	int siz = 1;
	vector<int>hbit,addv,subv,sumv;
	vector<bool>full;
	void init(int n){
		while(siz < n)siz *= 2;
		hbit.assign(siz*2,0);
		addv.assign(siz*2,0);
		sumv.assign(siz*2,0);
		full.assign(siz*2,0);
	}
	inline int ls(int x){return (x<<1)|1;}
	inline int rs(int x){return (x<<1)+2;}
	int lowbit(int x){return x & -x;}
	int highbit(int x){
		for(int i = 30;i >= 0;i--)if((1<<i)&x)return (1<<i);
		return 0;
	}
	void pushup(int x){
		if(full[ls(x)] and full[rs(x)])full[x] = 1;
		sumv[x] = (sumv[ls(x)] + sumv[rs(x)])%p;
		hbit[x] = (hbit[ls(x)] + hbit[rs(x)])%p;
	}
	void pushdown(int x){
		if(addv[x]){
			int & v = addv[x];
			addv[ls(x)] += v,addv[rs(x)] += v;
			hbit[ls(x)] = (hbit[ls(x)] * p2[v])%p;
			hbit[rs(x)] = (hbit[rs(x)] * p2[v])%p;
			v = 0;
		}
	}
	void build(vector<int> & in,int x,int lx,int rx){
		if(rx - lx == 1){
			if(lx < (int)in.size()){
				int h = highbit(in[lx]);
				hbit[x] = h;
				in[lx] -= h;
				sumv[x] = in[lx];
				if(!sumv[x] and !hbit[x])full[x] = 1;
			}
			return;
		}
		int m = (lx+rx)/2;
		build(in,ls(x),lx,m);
		build(in,rs(x),m,rx);
		pushup(x);
	}
	void build(vector<int> & in){
		build(in,0,0,siz);
	}
	void add(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(rx - lx > 1)pushdown(x);
		if(l <= lx and rx <= r){
			hbit[x] = (hbit[x]*2)%p;
			addv[x]++;
			return;
		}
		int m = (lx+rx)/2;
		add(l,r,ls(x),lx,m);
		add(l,r,rs(x),m,rx);
		pushup(x);
	}
	void add(int l,int r){
		r++;
		add(l,r,0,0,siz);
	}
	void sub(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		if(rx - lx > 1)pushdown(x);
		if(l <= lx and rx <= r){
			if(full[x]){
				return;
			}
			if(rx - lx == 1){
				if(!sumv[x]){
					full[x] = 1;
					hbit[x] = 0;
				}
				sumv[x] -= lowbit(sumv[x]);
				return;
			}
		}
		int m = (lx+rx)/2;
		sub(l,r,ls(x),lx,m);
		sub(l,r,rs(x),m,rx);
		pushup(x);
	}
	void sub(int l,int r){
		r++;
		sub(l,r,0,0,siz);
	}
	ll sum(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		if(rx - lx > 1)pushdown(x);
		if(l <= lx and rx <= r){
			return (sumv[x] + hbit[x])%p;
		}
		int m = (lx+rx)/2;
		ll s1 = sum(l,r,ls(x),lx,m);
		ll s2 = sum(l,r,rs(x),m,rx);
		return (s1+s2)%p;
	}
	ll sum(int l,int r){
		r++;
		return sum(l,r,0,0,siz);
	}
};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.setf(ios::fixed,ios::floatfield);
	cout.precision(12);
	p2[0] = 1;
	for(int i = 1;i < maxn;i++)p2[i] = p2[i-1]*2%p;	 
	int __;
	cin >> __;
	while(__--){
		int n;
		cin >> n;
		vector<int>in(n+1);
		for(int i = 1;i <= n;i++)cin >> in[i];
		Segtree seg;
		seg.init(n+10);
		seg.build(in);
		int q;
		cin >> q;
		while(q--){
			int opt,l,r;
			cin >> opt >> l >> r;
			if(opt == 1)cout << seg.sum(l,r) << endl;
			else if(opt == 2)seg.sub(l,r);
			else seg.add(l,r);
		}
	}
	return 0;
}