60pts求助

#include<bits/stdc++.h>
using namespace std; 
const int N = 1000010;
int n, m, a[N], st[N][21], lg[N], pre[N], pp[N];
inline int query(int l, int r){
	int k = lg[r-l+1];
	return max(st[l][k], st[r-(1<<k)+1][k]);
}
int main(){
	cin >> n >> m;
	lg[0] = -1;
	for(int i = 1;i <= n; i++) lg[i] = lg[i>>1]+1;
	for(int i = 1;i <= n; i++) cin >> a[i];
	a[0] = 2;
	int sum = 0, o = 0, z = 0;
	for(int i = 1;i <= n; i++){
		if(a[i]){
			sum --;
			o ++;
		}
		else{
			sum ++;
			z ++;
		}
		st[i][0] = z-o;
		pp[i] = o;
		pre[i] = pre[i-1]+(a[i]==1&&a[i-1]==0); 
	}
	for(int j = 1;j <= 20; j++){
		for(int i = 1;i+(1<<j)-1 <= n; i++)
			st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
	}
	while(m --){
		int op,l,r;
		cin >> op >> l >> r;
		if(op == 1)
			cout << max(pp[r]-pp[l-1],query(l,r)-(l-1-pp[l-1])+pp[r]);
		else if(op == 2){
			cout << (1+!(pre[l]==pre[r]));
		}
		cout << "\n";
	}
	return 0;
}