B3836
by live_cxy110122 @ 2024-04-14 15:44:40
啥也不是！！！
by greyandking @ 2024-04-14 15:44:44
P10273我这题不会
求求了
by greyandking @ 2024-04-14 15:45:29
```c
/**
* author: sunkuangzheng
* created: 25.03.2024 09:12:19
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,m,pre[N],rk[N],sa[N],ok[N],h[N],st[20][N],mp[N],ans[N],th[N],sta[N],res[N],tp,ts[20][N],sm[N]; string s,t;
void SA(){
for(int i = 1;i <= n;i ++) sa[i] = i,rk[i] = s[i];
for(int j = 1;j <= n;j *= 2){
for(int i = 1;i <= n;i ++) ok[i] = rk[i]; int p = 0;
sort(sa+1,sa+n+1,[&](int x,int y){return rk[x] < rk[y] || rk[x] == rk[y] && rk[x + j] < rk[y + j];});
auto cmp = [&](int x,int y){return ok[x] == ok[y] && ok[x + j] == ok[y + j];};
for(int i = 1;i <= n;i ++) rk[sa[i]] = (cmp(sa[i],sa[i-1]) ? p : ++p); if(p == n) break;
}for(int i = 1,k = 0;i <= n;h[rk[i ++]] = k) for(k --,k = max(k,0);s[i + k] == s[sa[rk[i] - 1] + k];k ++);
for(int i = 1;i <= n;i ++) st[0][i] = h[i];
for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
st[j][i] = min(st[j-1][i],st[j-1][i+(1<<j-1)]);
}int lcp_pos(int i,int j){
if(i == j) return n - i + 1;
if(i = rk[i],j = rk[j],i > j) swap(i,j);
int k = __lg(j - i);
return min(st[k][i+1],st[k][j-(1<<k)+1]);
}struct str{int l,r,id;}a[N];
struct seg{
int t[N*4],tg[N*4],t2[N*4],tg2[N*4];
void cg(int s,int k,int op){
op ? (tg[s] = max(tg[s],k),t[s] = max(t[s],k)) :
(tg2[s] = min(tg2[s],k),t2[s] = min(t2[s],k));}
void pd(int s){cg(s*2,tg[s],1),cg(s*2+1,tg[s],1),cg(s*2,tg2[s],0),cg(s*2+1,tg2[s],0),tg2[s] = 1e9,tg[s] = 0;}
void upd(int s,int l,int r,int ql,int qr,int k,int op){
if(ql <= l && r <= qr) return cg(s,k,op);
int mid = (l + r) / 2; pd(s);
if(ql <= mid) upd(s*2,l,mid,ql,qr,k,op); if(qr > mid) upd(s*2+1,mid+1,r,ql,qr,k,op);
t[s] = min(t[s*2],t[s*2+1]),t2[s] = max(t2[s*2],t2[s*2+1]);
}int qry(int s,int l,int r,int ql,int qr,int op){
if(ql > qr) return -1e9;
if(ql <= l && r <= qr) return (op ? t[s] : t2[s]);
int mid = (l + r) / 2,ans = (op ? 1e9 : -1e9); pd(s);
if(ql <= mid) ans = qry(s*2,l,mid,ql,qr,op);
if(qr > mid) ans = (op ? min(ans,qry(s*2+1,mid+1,r,ql,qr,op)) : max(ans,qry(s*2+1,mid+1,r,ql,qr,op)));
return ans;
}void init(){for(int i = 1;i <= 4*n;i ++) t[i] = tg[i] = 0,t2[i] = tg2[i] = 1e9;}
}sg;
int lcp_sub(str i,str j){return min({lcp_pos(i.l,j.l),i.r - i.l + 1,j.r - j.l + 1});}
bool cmp(str i,str j){
if(lcp_pos(i.l,j.l) >= min(i.r - i.l + 1,j.r - j.l + 1)) return (i.r - i.l + 1 < j.r - j.l + 1);
return rk[i.l] < rk[j.l];
}void los(){
cin >> n >> m >> s >> t,s = " " + s,t = " " + t;
fill(mp+1,mp+n+1,1e9),SA();
for(int i = 1;i <= m;i ++) cin >> a[i].l >> a[i].r,a[i].id = i,mp[a[i].l] = min(mp[a[i].l],a[i].r);
sort(a+1,a+m+1,cmp),sg.init();
for(int i = 1;i <= n;i ++) sm[i] = sm[i-1] + (t[i] == '1');
pre[0] = 1e9;
for(int i = 1;i <= m;i ++) ts[0][i] = a[i].l,pre[i] = min(pre[i-1],a[i].r);
for(int j = 1;j <= __lg(m);j ++) for(int i = 1;i + (1 << j) - 1 <= m;i ++)
ts[j][i] = min(ts[j-1][i],ts[j-1][i+(1<<j-1)]);
auto qmin = [&](int l,int r){
l = max(l,1); if(l > r) return (int)1e9;
int k = __lg(r - l + 1);
return min(ts[k][l],ts[k][r-(1<<k)+1]);
};
for(int i = 1;i <= n;i ++) if(t[i] == '0') sg.upd(1,1,n,i,i,1e9,1),sg.upd(1,1,n,i,i,-1e9,0);
int j = 1,ql = 0,qr = 1e9,fg = 0; res[0] = 1e9;
auto ins = [&](int i,int k){
while(tp && th[sta[tp]] >= th[i]) tp --;
int j = sta[tp]; sta[++tp] = i;
return res[i] = min({res[j],pre[k],qmin(j,k) + th[i]});
};
for(int i = 1;i <= m;i ++){
th[i] = (i == 1 ? 0 : lcp_sub(a[i],a[i-1]));
// cerr << s.substr(a[i].l,a[i].r - a[i].l + 1) << "\n";
while(j < i && cmp(a[j],a[i]))
sg.upd(1,1,n,a[j].l,a[j].r,a[j].l,1),sg.upd(1,1,n,a[j].l,a[j].r,a[j].l,0),ql = max(ql,a[j ++].l);
qr = min(qr,ins(i,j-1));
if(mp[a[i].l] != a[i].r) ans[a[i].id] = 0;
else{
// debug(a[i].id,ql,qr);
if(j == 1) {ans[a[i].id] = 1; continue;}
int len = min({lcp_pos(a[1].l,a[i].l),a[1].r - a[1].l,a[i].r - a[i].l}) + 1;
ans[a[i].id] |= sg.qry(1,1,n,a[i].l,a[i].l + len - 1,1) < a[i].l;
if(ql <= qr){
auto sum = [&](int l,int r){return (l <= r ? sm[r] - sm[l - 1] : 0);};
ans[a[i].id] |= (sum(ql,min(qr,a[i].l-1)) || sum(max(a[i].r+1,ql),min(n,qr)) || sg.qry(1,1,n,max(ql,a[i].l),min(qr,a[i].r),0) > a[i].l);
}
}
}for(int i = 1;i <= m;i ++) cout << ans[i];
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(T = 1;T --;) los();
}
```
@[greyandking](/user/1058749)
by jiaoshousimida114514 @ 2024-04-14 15:55:52