numbers_tree

#include <bits/stdc++.h>
using namespace std;
const int N=100005, MAXNR=1000005;
struct Node
{
    int st=0,dr=0,Query3=0,Query2=0;
};
Node Tree[4*N], zero;
int lazy[4*N];
int n,val,ql,qr;
bitset<MAXNR>isPrime;

inline void updateLazy(int tl,int tr,int ti)
{
    if(isPrime[lazy[ti]])
    {
        Tree[ti].st=tr-tl+1;
        Tree[ti].dr=tr-tl+1;
        Tree[ti].Query3=tr-tl+1;
        Tree[ti].Query2=0;
    }
    else
    {
        Tree[ti].st=0;
        Tree[ti].dr=0;
        Tree[ti].Query3=0;
        Tree[ti].Query2=tr-tl+1;
    }
    if(tl<tr)
    {
        lazy[ti*2]=lazy[ti];
        lazy[ti*2+1]=lazy[ti];
    }
    lazy[ti]=0;
}

void updateRange(int tl=1,int tr=n,int ti=1)
{
    if(lazy[ti])
        updateLazy(tl,tr,ti);
    if(tr<ql||qr<tl)
        return;
    if(ql<=tl&&tr<=qr)
    {
        lazy[ti]=val;
        updateLazy(tl,tr,ti);
        return;
    }

    int mid=(tl+tr)/2;
    updateRange(tl,mid,ti*2);
    updateRange(mid+1,tr,ti*2+1);
    Tree[ti].st=max(Tree[ti*2].st,(Tree[ti*2].Query2==0) ? Tree[ti*2].st+Tree[ti*2+1].st : 0);
    Tree[ti].dr=max(Tree[ti*2+1].dr,(Tree[ti*2+1].Query2==0) ? Tree[ti*2+1].dr+Tree[ti*2].dr : 0);
    Tree[ti].Query3=max(max(Tree[ti*2].Query3,Tree[ti*2+1].Query3),Tree[ti*2].dr+Tree[ti*2+1].st);
    Tree[ti].Query2=Tree[ti*2].Query2+Tree[ti*2+1].Query2;
}

int queryRange(int tl=1,int tr=n,int ti=1)
{
    if(lazy[ti])
        updateLazy(tl,tr,ti);
    if(tr<ql||qr<tl)
        return 0;
    if(ql<=tl&&tr<=qr)
        return Tree[ti].Query2;
    int mid=(tl+tr)/2;
    return queryRange(tl,mid,ti*2)+queryRange(mid+1,tr,ti*2+1);
}

Node queryRange3(int tl=1,int tr=n,int ti=1)
{
    if(lazy[ti])
        updateLazy(tl,tr,ti);
    if(tr<ql || qr<tl)
        return zero;
    if(ql<=tl && tr<=qr)
        return Tree[ti];
    int mid=(tl+tr)/2;
    Node left=queryRange3(tl,mid,ti*2);
    Node right=queryRange3(mid+1,tr,ti*2+1);
    Node ans;
    ans.st=max(left.st,(left.Query2==0)?left.st+right.st:0);
    ans.dr=max(right.dr,(right.Query2==0)?right.dr+left.dr:0);
    ans.Query3=max(max(left.Query3,right.Query3),left.dr+right.st);
    ans.Query2=left.Query2+right.Query2;
    return ans;
}

void sieveOfEratosthenes()
{
    isPrime.set();
    int pi;
    for(int i=2;i*i<MAXNR;++i)
        if(isPrime[i])
            for( pi=i*2; pi<MAXNR; pi+=i)
                isPrime[pi]=false;
}
int main()
{
    ios::sync_with_stdio(false);
    sieveOfEratosthenes();
    int op,q;
    ifstream fin("numbers_tree.in");
    fin>>n>>q;
    for(int i=1;i<=n;++i)
    {
        fin>>val;
        ql=qr=i;
        updateRange();
    }
    ofstream fout("numbers_tree.out");
    while(q--)
    {
        fin>>op>>ql>>qr;
        if(op==1)
        {
            fin>>val;
            updateRange();
        }
        else
            if(op==2)
                fout<<queryRange()<<'\n';
            else
                fout<<queryRange3().Query3<<'\n';
    }
    return 0;
}