A

直接取 $n$ ,然后就是 $\frac{n-1}{2}+1$ 。

B

注意到只要超出一行的数目 $c$,就可以连接在一起,此方案就为 $c$ ,等差数列求和,如果只有一行,那么方案数一定为 $1$

C

不难发现第二种客人无论怎么拿,最多只能拿 $\min\{n,m\}$ 个,因为他们总是取低的那个,于是低的高度减 $1$ ,不存在什么能取两次 $a$ 高度的, 然后借此判断即可

D

就是一构造数列,对角线随便造。

E

枚举 $x$ ,不难发现,$x$ 的范围总在 $(\max\{a_i\}-n+1,\max\{a_i\}-1)$ 范围中,因为方案数既不能为 $0$ 也不能为 $n!$ ( $p$ 可整除)。

然后就可以枚举 $x$ ,得到 $\prod\limits_{i=x}^{x+n-1}b_{i}-(i-x)=\prod\limits_{i=x}^{x+n-1}x-(b_{i}-i)$

仅需要满足所有的 $x-b_i+i\equiv 0(\text{mod } p)$ ,即 $x\equiv b_i-i(\text{mod p})$

其中,$b_i$ 表示 小于等于 $i$ 糖果的敌人数。

$\Theta(n^2)$ 做法就是直接暴力算所有的 $b_i-i$ 。

$\Theta(n)$ 做法就是发现 $x+1$ ,只会增加一个 $b_{x+n}-(x+n)$ ,减去一个 $b_{x-1}-(x-1)$ ,用个数组记录数出现的次数即可,实现过程需要整体移位,即 $-\max\{a_i\}+n$

const int N=1e5+10;
int a[N],b[N<<1],ans[N],c[N],len;
int n,p;
int mod(int x){return (x%p+p)%p;}
int main()
{
    int mx=0;scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),mx=max(a[i],mx);
    for(int i=1;i<=n;i++)b[max(0,a[i]-mx+n)]++;
    for(int i=1;i<=(n<<1);i++)b[i]+=b[i-1];int tmp=mx-n;
    for(int i=1;i<=n;i++)c[mod(i-b[i])]++;
    for(int i=1;i<n;i++){if(!c[mod(i)])ans[++len]=i+tmp;c[mod(i-b[i])]--;c[mod(i+n-b[i+n])]++;}
    printf("%d\n",len);for(int i=1;i<=len;i++)printf("%d ",ans[i]);
    return 0;
} 

F

即可码农,也可不码农。

这里介绍一种不码农的做法。

不妨分别存储翻转,和没翻转的序列信息,然后在区间合并时,分别合并信息。

在合并信息时,注意左区间的后缀与右区间的前缀的合并方式,可以分为四种情况,也即

左区间前缀分别为 $<<<<<<<$ 以及不是 $<<<<<<<$ 的情况,后缀、右区间同理。

之后就是考虑细节的问题了。

const int N=5e5+5;
template<class o>void qr(o &x)
{
    x=0;char c=gc;int f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}x*=f;
}
template<class o>void qw(o x){if(x<0)putchar('-'),x=-x;if(x/10)qw(x/10);putchar(x%10+48);}
struct SGT
{
    int l[2],m[2],r[2],S;bool rv;
    /*
    l[0]>0 means sufix <<<<<<<....< l[0]<0 means >><<<...<  or >>>>>...>>(this state means l[0]=r[0]=S or other ....) 
    r[0]>0 means the same as l[0]>0,r[0]<0 means the same as l[0]<0
    the others are the same.
    */
    I void set(bool v)
    {
        m[0]=m[1]=1;S=1;rv=0;
        if(v)r[0]=1,l[0]=-1,r[1]=-1,l[1]=1;
        else r[1]=1,l[1]=-1,r[0]=-1,l[0]=1;
    }
    I void rev(){swap(l[0],l[1]);swap(m[0],m[1]);swap(r[0],r[1]);rv^=1;}
    friend SGT operator +(const SGT &l,const SGT &r)
    {
        SGT n;n.S=l.S+r.S;int L=l.S,R=r.S;n.rv=0;
        for(int i=0;i<2;i++)
        {
            n.l[i]=l.l[i];n.r[i]=r.r[i];
            if(l.l[i]>0)n.l[i]+=(l.l[i]==L&&r.l[i]>0?r.l[i]:0);
            else if(l.l[i]==-L)if(l.r[i]==L||r.l[i]>0)n.l[i]-=abs(r.l[i]);
            if(r.r[i]>0)n.r[i]+=(r.r[i]==R&&l.r[i]>0?l.r[i]:0);
            else if(r.r[i]==-R)if(r.l[i]==R||l.r[i]>0)n.r[i]-=abs(l.r[i]);
            n.m[i]=max(l.m[i],r.m[i]);
            if(l.r[i]>0||r.l[i]>0)n.m[i]=max(n.m[i],abs(l.r[i])+abs(r.l[i]));
        }
        return n;
    }
}t[N<<2],cur;char s[N];int cl=0;
void pushdown(int p){if(t[p].rv){t[p<<1].rev();t[p<<1|1].rev();t[p].rv=0;}}
void build(int p,int l,int r)
{
    t[p].S=r-l+1;if(l==r){t[p].set(s[l]=='>');return ;}
    int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    t[p]=t[p<<1]+t[p<<1|1];
}
void upd(int p,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r){t[p].rev();if(cl)cur=cur+t[p];else cur=t[p];++cl;return ;}
    int mid=l+r>>1;pushdown(p);if(ql<=mid)upd(p<<1,l,mid,ql,qr);if(qr>mid)upd(p<<1|1,mid+1,r,ql,qr);
    t[p]=t[p<<1]+t[p<<1|1];
}
int main()
{
    int n,m;qr(n),qr(m);
    scanf("%s",s+1);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int l,r;qr(l),qr(r);
        upd(1,1,n,l,r);cl=0;
        qw(cur.m[0]);puts("");
    }
    return 0;
}