牛半仙的妹子序列

牛半仙的妹子序列

题解：

考虑。

对于第个点，考虑哪些点对是有贡献的。记点到点间比大的最小值为，那么只要那么这个点就会有贡献。所以我们要维护这个。

怎么维护呢，对于一个新加入的值，那些值小于的点的就要和取。

用维护这个，只观察，发现每次操作可以看成比大的数变成，每次操作都会少一段值相同的区间。总共只有段区间，所以最多操作次，时间复杂度:

用线段树处理应该复杂度一样的吧（作者太菜不会证）。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=998244353;
const int N=1e6+5;
int n,m,ans,a[N],f[N];
struct node{
    int val,gs;
}tree[N*4];
node operator + (node a,node b)
{
    if(a.val>b.val)return a;
    if(a.val<b.val)return b;
    return (node){a.val,(a.gs+b.gs)%mod};
}
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void change(int nod,int l,int r,int L,int R,int x)
{
    if(l>=L&&r<=R&&tree[nod].val<x)return;
    if(l>R||r<L)return;
    if(l==r)
    {
        tree[nod].val=x;
        return;
    }
    int mid=(l+r)/2;
    change(nod*2,l,mid,L,R,x);
    change(nod*2+1,mid+1,r,L,R,x);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
node find(int nod,int l,int r,int L,int R)
{
    if(l==L&&r==R)return tree[nod];
    int mid=(l+r)/2;
    if(R<=mid)return find(nod*2,l,mid,L,R);
    else if(L>mid)return find(nod*2+1,mid+1,r,L,R);
    else return find(nod*2,l,mid,L,mid)+find(nod*2+1,mid+1,r,mid+1,R);
}
void change2(int nod,int l,int r,int x,int val)
{
    if(l==r)
    {
        tree[nod].val=n+1;
        tree[nod].gs=val;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)change2(nod*2,l,mid,x,val);
    else change2(nod*2+1,mid+1,r,x,val);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)
    {
        change(1,1,n,1,a[i],a[i]);
        node x=find(1,1,n,1,a[i]);
        if(x.val==a[i])f[i]=x.gs;
        else f[i]=1;
        change2(1,1,n,a[i],f[i]);
    }
    cout<<tree[1].gs;
    return 0;
}