numbers_tree

#include <fstream>
#include <bitset>
using namespace std;
const int N=1e5+5,maxNr=1e6+5;
struct nod
{
    /// st          = cate nr prime consecutive sunt in acest interval de la inceput la sfarsit
    /// dr          = cate nr prime consecutive sunt in acest interval de la sfarsit la inceput
    /// secventaMax = secventa max de nr prime consecutive
    /// totCompuse  = cate nr compuse sunt in tot nodul
    int st=0,dr=0,secventaMax=0,totCompuse=0;
} arb[4*N],nullElement;
int lazy[4*N]; /// retine ce numar trebuie sa fie de aici in jos
int n,val,ql,qr;
bitset<maxNr>prim;

inline void updateLazy(int tl,int tr,int ti)
{
    if (prim[lazy[ti]])
    {
        arb[ti].st=tr-tl+1;
        arb[ti].dr=tr-tl+1;
        arb[ti].secventaMax=tr-tl+1;
        arb[ti].totCompuse=0;
    }
    else
    {
        arb[ti].st=0;
        arb[ti].dr=0;
        arb[ti].secventaMax=0;
        arb[ti].totCompuse=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) /// Nu este in interval
        return;
    if(ql<=tl&&tr<=qr) /// Este complet in interval
    {
        lazy[ti]=val;
        updateLazy(tl,tr,ti);
        return;
    }
    /// Partial in interval
    int mid=(tl+tr)/2;
    updateRange(tl,mid,ti*2);
    updateRange(mid+1,tr,ti*2+1);
    arb[ti].st=max(arb[ti*2].st,(arb[ti*2].totCompuse==0)?arb[ti*2].st+arb[ti*2+1].st:0);
    arb[ti].dr=max(arb[ti*2+1].dr,(arb[ti*2+1].totCompuse==0)?arb[ti*2+1].dr+arb[ti*2].dr:0);
    arb[ti].secventaMax=max(max(arb[ti*2].secventaMax,arb[ti*2+1].secventaMax),arb[ti*2].dr+arb[ti*2+1].st);
    arb[ti].totCompuse=arb[ti*2].totCompuse+arb[ti*2+1].totCompuse;
}

int queryRange(int tl=1,int tr=n,int ti=1)
{
    if(lazy[ti])
        updateLazy(tl,tr,ti);
    if(tr<ql||qr<tl) /// Nu este in interval
        return 0;
    if(ql<=tl&&tr<=qr) /// Este complet in interval
        return arb[ti].totCompuse;
    /// Partial in interval
    int mid=(tl+tr)/2;
    return queryRange(tl,mid,ti*2)+queryRange(mid+1,tr,ti*2+1);
}

nod queryRange1(int tl=1,int tr=n,int ti=1)
{
    if(lazy[ti])
        updateLazy(tl,tr,ti);
    if(tr<ql||qr<tl) /// Nu este in interval
        return nullElement;
    if(ql<=tl&&tr<=qr) /// Este complet in interval
        return arb[ti];
    /// Partial in interval
    int mid=(tl+tr)/2;
    nod left=queryRange1(tl,mid,ti*2);
    nod right=queryRange1(mid+1,tr,ti*2+1);
    nod result;
    result.st=max(left.st,(left.totCompuse==0)?left.st+right.st:0);
    result.dr=max(right.dr,(right.totCompuse==0)?right.dr+left.dr:0);
    result.secventaMax=max(max(left.secventaMax,right.secventaMax),left.dr+right.st);
    result.totCompuse=left.totCompuse+right.totCompuse;
    return result;
}

void ciur()
{
    prim.set();
    int mult;
    for(int i=2;i<maxNr;++i)
    {
        if(prim[i])
        {
            mult=i*2;
            while(mult<maxNr)
                prim[mult]=false,mult+=i;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    ciur();
    int op,q;
    ifstream f("numbers_tree.in");
    f>>n>>q;
    for(int i=1;i<=n;++i)
        f>>val,ql=qr=i,updateRange();
    ofstream g("numbers_tree.out");
    while(q--)
    {
        f>>op>>ql>>qr;
        if(op==1) /// Tot intervalul [ql,qr] va avea noua valoare val
            f>>val,updateRange();
        else
            if(op==2) /// Cate nr de la st la dr sunt compuse
                g<<queryRange()<<'\n';
            else /// Cea mai lunga secventa de numere prime
                g<<queryRange1().secventaMax<<'\n';
    }
    return 0;
}