Submission #68198389

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define beg begin
#define All(A) A.beg(),A.end()
#define pb push_back
#define fir first
#define sec second
#define gr greater<>()
#define Lsh(A) sort(All(A)),\
A.erase(unique(All(A)),A.end());
#define u_set unordered_set
#define u_map unordered_map
#define lwb lower_bound
#define upb upper_bound
using ull=unsigned long long;
using bint=__int128;
using uint=unsigned int;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
using vi=vector<int>;
using gi=greater<int>;
using str=string;
using bqi=priority_queue<int>;
using lqi=priority_queue<int,vi,gi>;
using qi=queue<int>;
using si=set<int>;
using usi=u_set<int>;
using vll=vector<ll>;
using pll=pair<ll,ll>;
using vvi=vector<vi>;
using vvl=vector<vll>;
using vpi=vector<pii>;
using ply=vll;
mt19937_64 Rng(time(0));
ll rnd(int l,int r)
{return Rng()%(r-l+1)+l;}
namespace Binom{
const int p=998244353;
const int i2=(p+1)/2;
ll ksm(ll a,ll b)
{
    ll ans=1;while(b)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p;b>>=1;
    }return ans;
}const int Msz=1e6+5;
ll fc[Msz],iv[Msz];
void init_C(int n)
{
    fc[0]=1;for(int i=1;i<=n;i++)fc[i]=fc[i-1]*i%p;
    iv[n]=ksm(fc[n],p-2);for(int i=n-1;i>=0;i--)
    iv[i]=iv[i+1]*(i+1)%p;
}ll C(int n,int m)
{
    if(n<m||m<0)return 0;
    return fc[n]*iv[m]%p*iv[n-m]%p;
}}using Binom::C;
using Binom::init_C;
namespace Poly
{
    const int p=998244353;
    const int N=1<<21;int rv[N];
    const int g=3,ig=(p+1)/g;
    ll ksm(ll a,ll b)
    {
        ll ans=1;while(b)
        {
            if(b&1)ans=ans*a%p;
            a=a*a%p;b>>=1;
        }return ans;
    }
    void init(int n)
    {
        for(int i=1;i<=n;i++)
        {
            rv[i]=rv[i>>1]>>1;
            if(i&1)rv[i]|=(n>>1);
        }
    }
    void NTT(ll *a,int l,int o)
    {
        for(int i=0;i<l;i++)
        if(i<rv[i])swap(a[i],a[rv[i]]);
        for(int d=1;d<l;d<<=1)
        {
            ll pw=ksm(g,(p-1)/d/2);
            if(o<0)pw=ksm(pw,p-2);
            for(int i=0;i<l;i+=(d<<1))
            {
                ll vl=1;
                for(int j=i;j<i+d;j++)
                {
                    ll x=a[j],y=a[j+d]*vl%p;
                    if((a[j]=x+y)>=p)a[j]-=p;
                    if((a[j+d]=x-y)<0)a[j+d]+=p;
                    vl=vl*pw%p;
                }
            }
        }if(o<0)
        {
            ll vl=ksm(l,p-2);
            for(int i=0;i<l;i++)
            a[i]=a[i]*vl%p;
        }
    }
    ply mul(ply f,ply g)
    {
        int n=f.size()-1,m=g.size()-1;
        ply rs(n+m+1);int l=1;
        while(l<=n+m)l<<=1;
        static ll a[N],b[N];init(l);
        for(int i=0;i<l;i++)a[i]=b[i]=0;
        for(int i=0;i<=n;i++)a[i]=f[i];
        for(int i=0;i<=m;i++)b[i]=g[i];
        NTT(a,l,1),NTT(b,l,1);
        for(int i=0;i<l;i++)a[i]=a[i]*b[i]%p;
        NTT(a,l,-1);for(int i=0;i<=n+m;i++)
        rs[i]=a[i];return rs;
    }
}using Poly::mul;
namespace quickpow{
template<ll p>
ll qpow(bint a,ll b)
{
    bint ans=1;while(b)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p,b>>=1;
    }return ans;
}template<typename T>
T qpowt(T a,ll b)
{
    T ans;while(b)
    {
        if(b&1)ans=ans*a;
        a=a*a,b>>=1;
    }return ans;
}ll Ksm(bint a,ll b,ll p)
{
    bint ans=1;while(b)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p,b>>=1;
    }return ans;
}
}using namespace quickpow;
namespace num_th{
vi ckl={2,325,9375,28178,
450775,9780504,1795265022};
template<typename T>
T gcd(T a,T b)
{
    while(b^=a^=b^=a%=b);
    return a;
}
bool ckpr(ll n)
{
    if(n<3||!(n&1))return (n==2);
    if(n%3==0)return (n==3);
    ll u=n-1;int t=0;
    while(!(u&1))u>>=1,t++;
    for(int a:ckl)
    {
        if(a%n<=1||a%n==n-1)continue;
        ll v=Ksm(a,u,n);
        if(v==1)continue;int s;
        for(s=0;s<t;s++)
        {
            if(v==n-1)break;
            v=bint(v)*v%n;
        }if(s==t)return false;
    }return true;
}ll gtfc(ll x)
{
    ll s=0,t=0,c=rnd(1,x-1);
    for(int k=1;;k<<=1)
    {
        ll vl=1;s=t;
        for(int j=1;j<=k;j++)
        {
            t=(bint(t)*t+c)%x;
            vl=bint(vl)*abs(t-s)%x;
            if(!vl)return gtfc(x);
            if(!(j&127))
            {
                ll d=gcd(x,vl);
                if(d>1)return d;
            }
        }ll d=gcd(x,vl);
        if(d>1)return d;
    }
}
}using num_th::ckpr;
using num_th::gtfc;
const int p=998244353;//the Mod
const auto ksm=qpow<p>;
const int N=2e5+5;
int n,q,a[N];
int cnt=0;
set<pii> s,st;
void gt()
{
    if(s.size()==0)
    {
        if(cnt==n)cout<<n<<'\n';
        else if(a[1]==0&&a[n]==0)cout<<"3\n";
        else cout<<"2\n";return;
    }
    int ans=(a[1]==0&&a[2]==1);
    ans+=(a[n]==0&&a[n-1]==1);
    ans+=int(s.size())*3-1;
    if(s.size())
    {
        if(s.begin()->first!=1)ans++;
        if(s.rbegin()->second!=n)ans++;
    }cout<<ans<<'\n';
}void ins(int l,int r)
{
    st.insert((pii){l,r});
    if(l^r)s.insert((pii){l,r});
}void del(int l,int r)
{
    st.erase((pii){l,r});
    if(l^r)s.erase((pii){l,r});
}
void mf1(int x)
{
    auto it=st.upper_bound((pii){x,1e9});
    it--;int l=it->first,r=it->second;
    del(l,r);if(l^x)ins(l,x-1);
    if(r^x)ins(x+1,r);
}
void mf0(int x)
{
    auto it=st.upper_bound((pii){x,1e9});
    int Rl=-10,Rr=-10;if(it!=st.end())
    Rl=it->first,Rr=it->second;
    int Ll=-10,Lr=-10;if(it!=st.begin())
    {it--;Ll=it->first;Lr=it->second;}
    if(Lr+1==x&&x+1==Rl)
    {
        del(Rl,Rr),del(Ll,Lr);
        ins(Ll,Rr);
    }else if(Lr+1==x)
    {
        del(Ll,Lr);
        ins(Ll,x);
    }else if(x+1==Rl)
    {
        del(Rl,Rr);
        ins(x,Rr);
    }else ins(x,x);
}
void solve()
{
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
    cnt=0;for(int i=1;i<=n;i++)
    {
        if(a[i]==1)continue;
        int j=i;while(i+1<=n&&a[i+1]==0)
        i++;st.insert((pii){j,i});
        if(i^j)s.insert((pii){j,i});
    }for(int i=1;i<=n;i++)cnt+=a[i];
    cin>>q;for(int i=1;i<=q;i++)
    {
        int x;cin>>x;
        if(a[x]==0)mf1(x);
        else mf0(x);
        cnt-=a[x];
        a[x]^=1;
        cnt+=a[x];
        gt();
    }
}void init(){/*init_C(Msz-5);*/}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;init();//cin>>t;
    while(t--)solve();
    return 0;
}

Submission Info

Compile Error

./Main.cpp:120:20: warning: misleading indentation; statement is not part of the previous 'for' [-Wmisleading-indentation]
        rs[i]=a[i];return rs;
                   ^
./Main.cpp:119:21: note: previous statement is here
        NTT(a,l,-1);for(int i=0;i<=n+m;i++)
                    ^
./Main.cpp:263:13: warning: misleading indentation; statement is not part of the previous 'while' [-Wmisleading-indentation]
        i++;st.insert((pii){j,i});
            ^
./Main.cpp:262:17: note: previous statement is here
        int j=i;while(i+1<=n&&a[i+1]==0)
                ^
./Main.cpp:40:11: warning: unused variable 'i2' [-Wunused-const-variable]
const int i2=(p+1)/2;
          ^
./Main.cpp:65:19: warning: unused variable 'ig' [-Wunused-const-variable]
    const int g=3,ig=(p+1)/g;
                  ^
./Main.cpp:198:12: warning: unused variable 'ksm' [-Wunused-const-variable]
const auto ksm=qpow<p>;
           ^
5 warnings generated.

Judge Result