lyzqs的博客

某毒瘤比赛的一题

又是动态开点线段树

每次都写不出来

只能看看题解勉强维持生活

#include <bits/stdc++.h>
#define il inline
#define Max 20000005
#define Mod 998244353
#define int long long
#define ll long long
#define dec(x) (x=(x==0?Mod-1:x-1))
#define inc(x) (x=(x==Mod-1?0:x+1))
#define ct(x) ((1ll*x*(x+1)>>1)%Mod)
#define cg(x) (x=(x%Mod+Mod)%Mod)
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,2333,stdin),ss==tt)?EOF:*ss++)
using namespace std;
char In[2333],*ss=In,*tt=In;
namespace lyzqs
{

il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int pre[Max],suf[Max],rt,ls[Max],rs[Max],cnt=0;
bool ok[Max];
ll m,ans=0;
ll n;
il void mdf(int &x,ll l,ll r,ll ql,ll qr)
{
    if(!x) x=++cnt;
    if(ql<=l&&r<=qr)
    {
        ok[x]=1;
        return;
    }
    ll mid=(l+r)>>1;
    if(ql<mid) mdf(ls[x],l,mid,ql,qr);
    if(qr>mid) mdf(rs[x],mid,r,ql,qr);
}
il void pushup(int x)
{
    ans=(ans+1ll*suf[ls[x]]*pre[rs[x]])%Mod;
    cg(ans);
    if(ok[x]&&!ok[ls[x]]&&!ok[rs[x]]) dec(ans);
    if(!ok[x]&&(ok[ls[x]]||ok[rs[x]])) inc(ans);
    pre[x]+=pre[ls[x]]+!ok[x]+(!ok[ls[x]])*(pre[rs[x]]-!ok[rs[x]]);
    suf[x]+=suf[rs[x]]+!ok[x]+(!ok[rs[x]])*(suf[ls[x]]-!ok[ls[x]]);
    cg(pre[x]),cg(suf[x]);
}
il void qry(int &x,ll l,ll r)
{
    if(r-l==1)
    {
        ans+=!ok[x];
        suf[x]=pre[x]=!ok[x];
        return;
    }
    if(!x)
    {
        x=++cnt;
        suf[x]=pre[x]=(r-l)%Mod;
        ans+=ct(pre[x]);
        cg(ans);
        return;
    }
    ll mid=(l+r)>>1;
    qry(ls[x],l,mid);
    qry(rs[x],mid,r);
    pushup(x);
}
void main()
{
    n=read();
    m=read();
    for(int i=1;i<=m;i++)
    {
        ll l=read(),r=read();
        mdf(rt,0,n,l-1,r);
    }
    qry(rt,0,n);
    printf("%lld\n",ans);
}

}

signed main()
{
    lyzqs::main();
}