H题复杂度 O(2500n+q) 为什么过不了 T^T

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
using ll=long long;
int read(){
    char ch=getchar();
    int s=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) s=(s<<1)+(s<<3)+ch-48,ch=getchar();
    return s;
}
const int N=1e6+10;
char a[N],t[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n=read(),q=read();
    for(int i=1;i<=n;i++){
        a[i]=getchar();
        t[i]=a[i]^a[i-1];
    }
    while(q--){
        int op=read();
        if(op==1){
            int l=read(),r=read();
            t[l]^=1,t[r+1]^=1;
        }
        else{
            int l=read(),aa=read(),b=read();
            int nn=max(aa,b)+l-1,L=-1,R=-1,mid=max(aa,b);
            ll ans=0;
            for(int i=1;i<=nn;i++){
                a[i]=a[i-1]^t[i];
                if(i>=mid){
                	if(a[aa+i-mid]==a[b+i-mid]){
	                	if(L==-1&&R==-1) L=R=i;
	                	else R++;
	                	ans+=R-L+1;
                	}
                	else L=R=-1;
                }
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

rt