思路讲解
先搞一个布尔运算前缀和，再搞一个布尔运算后缀和，加快查询效率
那么关键就来到了布尔运算前缀数组以及布尔运算后缀数组怎样运算更快（线性复杂度）？
https://www.luogu.com.cn/article/9yd2730s
如果vector的大小很大，复杂度就会变得很劣质，但我们发现当vector的大小超过3 时，可以将中间的所有数字或起来合并。
来讲讲为什么可以这样那？其实vector数组只要超过2，既有三个时，就可以合并了，因为只有最后一个bool不能合并，因为他仍然会受到后续与运算的影响，我们来实践一下试试。
但实际上不是只是把suffix和prefix搓出来就好的，特别是针对&，比如来看下面这个例子
1
2
3
| 5 7
false and true or true
1 1 false
|
false & suffix[3] == false看似是对的，但实际上是有问题的，后面这段当中有or出现，false ｜true == true，所以出现了问题。
AC代码
心路历程（WA，TLE，MLE……）
没有考虑其实用&运算直接连起来是不可行的，上面解释的非常清楚
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
152
153
154
155
156
157
158
159
160
| #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);
}
}
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;
cin>>l>>r>>op;
if(op[0]=='t')
w=true;
else
w=false;
if(l==1 && r==n){
cout<<'Y';
continue;
}
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;
}
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';
}
}
}
|