USACO 2024 US Open Contest, Bronze—Problem 1.Logical Moos · znzryb
## 思路讲解
先搞一个布尔运算前缀和，再搞一个布尔运算后缀和，加快查询效率
那么关键就来到了布尔运算前缀数组以及布尔运算后缀数组怎样运算更快（线性复杂度）？
[https://www.luogu.com.cn/article/9yd2730s](https://www.luogu.com.cn/article/9yd2730s)
> 如果vector的大小很大，复杂度就会变得很劣质，但我们发现当vector的大小超过3 时，可以将中间的所有数字或起来合并。
来讲讲为什么可以这样那？其实vector数组只要超过2，既有三个时，就可以合并了，因为只有最后一个bool不能合并，因为他仍然会受到后续与运算的影响，我们来实践一下试试。
但实际上不是只是把suffix和prefix搓出来就好的，特别是针对&，比如来看下面这个例子
```cpp
5 7
false and true or true
1 1 false
```
false & suffix[3] == false看似是对的，但实际上是有问题的，后面这段当中有or出现，false ｜true == true，所以出现了问题。
## AC代码
## 心路历程（WA，TLE，MLE……）
没有考虑其实用&运算直接连起来是不可行的，上面解释的非常清楚
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,m;
// 先搞一个布尔运算前缀和，再搞一个布尔运算后缀和，加快查询效率
void cal(const vector<bool> &temp,vector<bool> &xfix,const int idx){
xfix[idx]=temp[0];
for(int i=1;i<temp.size();++i){
xfix[idx]=(xfix[i] | temp[i]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
vector<bool> A(n+5);
vector<bool> prefix(n+5,false),suffix(n+5,false);
for(int i=1;i<=n;++i){
string a;
cin>>a;
if(a[0]=='f' || a[0]=='o')
A[i]=false;
else
A[i]=true;
}
vector<bool> temp;
// 计算前缀和
for(int i=1;i<=n;i+=2){
if(A[i-1]==false){
temp.push_back(A[i]);
cal(temp, prefix,i);
if(temp.size()>3){
temp[0]=(temp[0] | temp[1]);
temp[1]=temp[2];
temp.pop_back();
}
}else{
int last=temp.size()-1;
temp[last]=(temp[last] & A[i]);
cal(temp, prefix,i);
}
}
// 计算后缀和
// 显然可以直接将 [l,r] 的一大串直接替换为目标布尔值
temp.clear();
for(int i=n;i>=1;i-=2){
if(A[i+1]==false){
temp.push_back(A[i]);
cal(temp, suffix,i);
if(temp.size()>3){
temp[0]=(temp[0] | temp[1]);
temp[1]=temp[2];
temp.pop_back();
}
}else{
int last=temp.size()-1;
temp[last]=(temp[last] & A[i]);
cal(temp,suffix,i);
}
}
// 执行询问
for(int i=1;i<=m;++i){
ll l,r; string op;bool w; // w即want
cin>>l>>r>>op;
if(op[0]=='t')
w=true;
else
w=false;
if(l==1 && r==n){
cout<<'Y';
continue;
}
// l==1的特殊情况
if(l==1){
bool isWant=false;
if(A[r+1]==false){
if((w | suffix[r+2])==w)
isWant=true;
if(isWant)
cout<<'Y';
else
cout<<'N';
}else{
if((w & suffix[r+2])==w)
isWant=true;
if(isWant)
cout<<'Y';
else
cout<<'N';
}
continue;
}
// r==n的特殊情况
if(r==n){
bool isWant=false;
if(A[l-1]==false){
if((w | prefix[l-2])==w)
isWant=true;
if(isWant)
cout<<'Y';
else
cout<<'N';
}else{
if((w & prefix[l-2])==w)
isWant=true;
if(isWant)
cout<<'Y';
else
cout<<'N';
}
continue;
}
bool isWant=false;
if(A[r-1]==false && A[l-1]==false){
if((prefix[l-2] | w | suffix[r+2])==w)
isWant=true;
if(isWant)
cout<<'Y';
else
cout<<'N';
}else if(A[r-1]==true && A[l-1]==false){
if((prefix[l-2] & w | suffix[r+2])==w)
isWant=true;
if(isWant)
cout<<'Y';
else
cout<<'N';
}else if(A[r-1]==false && A[l-1]==true){
if((prefix[l-2] | w & suffix[r+2])==w)
isWant=true;
if(isWant)
cout<<'Y';
else
cout<<'N';
}else{
if((prefix[l-2] & w & suffix[r+2])==w)
isWant=true;
if(isWant)
cout<<'Y';
else
cout<<'N';
}
}
}
```