题解

模板题，参考区间根号题.

我们发现最多只会运算 $350$ 次，所以 $O(350n)$ 是完全可以的.

具体做法：维护一个线段树，记录区间内 $1$ 的个数，修改时如果发现有一个子树内的元素都为 $1$ 就不搜了；查询直接按普通线段树做.

由于这个算法是自顶而下的，所以就不能用重口味线段树了.

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[200005], sum[800005];
int n, q;
void build(int u, int l, int r){//O(n)建树
	if(l == r){
		cin >> a[l];
		sum[u] = (a[l] == 1);//判断是否为1
		return;
	}
	int mid = l + r >> 1;
	build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
	sum[u] = sum[u * 2] + sum[u * 2 + 1];
}

void __modify(int u, int l, int r, int x, int y){
	if(l == r){
		a[l] = (a[l] & 1 ? a[l] * 3 + 1 : a[l] / 2);//暴力计算
		sum[u] = (a[l] == 1);
		return;
	}
	int mid = l + r >> 1;
	if(x <= mid && sum[u * 2] < mid - l + 1) __modify(u * 2, l, mid, x, y);//如果全是1就不遍历了
	if(y > mid && sum[u * 2 + 1] < r - mid) __modify(u * 2 + 1, mid + 1, r, x, y);
	sum[u] = sum[u * 2] + sum[u * 2 + 1];
}

int __query(int u, int l, int r, int x, int y){
	if(x <= l && y >= r) return sum[u];
	
	int mid = l + r >> 1;
	int ct = 0;
	if(x <= mid) ct += __query(u * 2, l, mid, x, y);
	if(y > mid) ct += __query(u * 2 + 1, mid + 1, r, x, y);
	
	return ct;
}
#define modify(l, r) __modify(1, 1, n, l, r)
#define query(l, r) __query(1, 1, n, l, r)
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> q;
	build(1, 1, n);
	while(q--){
		int tmp, l, r;
		cin >> tmp >> l >> r;
		if(tmp == 1) modify(l, r);
		else cout << query(l, r) << '\n';
	}

	return 0;
}

时间复杂度：$O(Q\log N+350N)$