[Tjoi2016&Heoi2016]题解

By Snakes

（好不容易做完一套题……）

A Tree

离线处理，将所有操作倒序，并用并查集维护。对于标记操作，只需要在每个结点倒序之后，最后被执行标记操作的时刻与它父亲合并即可。对于询问操作，只需要查询该结点所在并查集的父亲。可以添加路径压缩优化。时间复杂度$O(n+q\alpha(n))$。

还可以用树链剖分哟～（如果你是树剖爱好者QAQ）

B Sort

30分考验你对C++的sort的使用熟练程度。（像我这种一开始打了30分暴力还在自定义cmp的时候把升序降序搞反也是没救了）

考虑二分答案，若当前答案为mid，那我们处理出一个长度为n的01序列，如果原序列第i位比mid小，那么标记为0，否则标记为1。新序列可以用线段树维护，排序过程相当于查询一次区间和以及两次区间修改。升序排序就将区间中的1移到右边，降序排序相当于将区间中的1移到左边。如果所有排序结束后，第q位为1,那么就表示该位置大于或等于mid，否则小于mid。继续二分即可。二分时间复杂度$O(logn)$，每次排序时间复杂度$O(mlogn)$，那么总的时间复杂度为$O(mlog^2n)$

C Seq

先考虑dp，令$f(i)$为第i个位置结尾的最优答案，不考虑某些项的值发生变化的时候可以用$f(i)=max(f(j))+1|j < i,a[j]<=a[i]$转移。记录一个位置能变化的最小值$b[i]$，最大值$c[i]$，那么考虑值发生变化的影响就可以用$$f(i)=max(f(j))+1|j < i,a[j]<=a[i],c[j]<=a[i],a[j]<=b[i]$$转移啦。如果将i从小到大扫描，每次扫描完一个点，将i加入数据结构中，那么就可以用kd-tree或者是cdq分治做啦。我用四分树也能做，直接维护最大值即可。查询的时候可以直接在树上查询满足$a[j]<=min(a[i],b[i]),c[j]<=a[i]$的最大值。时间复杂度$O(nlog^2n)$。

代码如下～

#include <cstdio>
#include <algorithm>
#define maxn 1<<19
#define maxt 100005
using namespace std;
struct node
{
    int ch[4],data;
};
node tree[maxn];
int root,glob_tot;
inline int new_node(int val)
{
    tree[++glob_tot].data=val;
    return glob_tot;
}
int x,y,val;
inline void insert(int lx,int rx,int ly,int ry,int &p)
{
    if (p==0)
        p=new_node(val);
    else
        tree[p].data=max(tree[p].data,val);
    if (lx^rx)
    {
        int mx=(lx+rx)>>1,my=(ly+ry)>>1;
        if (x>mx)
            if (y>my)
                insert(mx+1,rx,my+1,ry,tree[p].ch[0]);
            else
                insert(mx+1,rx,ly,my,tree[p].ch[1]);
        else
            if (y>my)
                insert(lx,mx,my+1,ry,tree[p].ch[3]);
            else
                insert(lx,mx,ly,my,tree[p].ch[2]);
    }
}
inline void query(int lx,int rx,int ly,int ry,int p)
{
    if (p==0||tree[p].data<val)
        return;
    if (rx<=x&&ry<=y)
    {
        val=tree[p].data;
        return;
    }
    int mx=(lx+rx)>>1,my=(ly+ry)>>1;
    if (x>mx)
        if (y>my)
        {
            query(mx+1,rx,my+1,ry,tree[p].ch[0]);
            query(mx+1,rx,ly,my,tree[p].ch[1]);
            query(lx,mx,ly,my,tree[p].ch[2]);
            query(lx,mx,my+1,ry,tree[p].ch[3]);
        }
        else
        {
            query(mx+1,rx,ly,my,tree[p].ch[1]);
            query(lx,mx,ly,my,tree[p].ch[2]);
        }
    else
        if (y>my)
        {
            query(lx,mx,ly,my,tree[p].ch[2]);
            query(lx,mx,my+1,ry,tree[p].ch[3]);
        }
        else
            query(lx,mx,ly,my,tree[p].ch[2]);
}
int n,m,a[maxt],b[maxt],c[maxt],i,j,ans;
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=c[i]=a[i];
    }
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        if (y<b[x])
            b[x]=y;
        if (y>c[x])
            c[x]=y;
    }
    for (i=1;i<=n;i++)
    {
        x=a[i];
        y=b[i];
        val=0;
        query(1,maxn,1,maxn,root);
        val++;
        if (val>ans)
            ans=val;
        x=c[i];
        y=a[i];
        insert(1,maxn,1,maxn,root);
    }
    printf("%d\n",ans);
    return 0;
}

D Game

二分图匹配的裸题。对于每个硬石头，将它左右和上下分别看成不同的行与不同的列。对于每个空地，将与它一行的标号和与它一列的标号连边，行与列作为二分图的两边，求最大匹配即可。可以证明这样连边满足每个行联通的块与列联通的块最多只会放一个炸弹。时间复杂度$O(VE)$，其中V为点数，E为边数。

E Sum

数论变态题QAQ

套第二类斯特林数展开式可以得到

$$ \begin{align} f(n)&=\sum_{i=0}^n\sum_{j=0}^i S(i,j)*2^j*(j!)\\ &=\sum_{i=0}^n\sum_{j=0}^n S(i,j)*2^j*(j!)\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*(j!)* \frac 1{j!}*\sum_{k=0}^j(-1)^kC_k^j(j-k)^i\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}C_k^jk^i\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}*\frac{j!}{k!(j-k)!}*k^i\\ &=\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}*\frac{j!}{k!(j-k)!}*\sum_{i=0}^nk^i\\ &=\sum_{j=0}^n 2^j*j!*\sum_{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}*\frac{\sum_{i=0}^nk^i}{k!} \end{align} $$

其中$\sum_{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}*\frac{\sum_{i=0}^nk^i}{k!}$交给我们伟大的NTT处理，令$a_i=\frac{(-1)^{j-i}}{(j-i)!}$，$b_i=\frac{\sum_{i=0}^nk^i}{k!}=\frac{i^{n+1}-1}{(i-1)*i!}$，$c_i=\sum_{k=0}^ia_k*b_{i-k}$，则$ans=\sum_{j=0}^n 2^j*j!*c_j$。

代码见下～（另附一超级猎奇版本，见文末。）

#include <cstdio>
using namespace std;
#define maxn 1<<19
#define mod 998244353
#define g 3
long long n,i,dft_len,pow2,fac;
long long fac_inv[maxn];
long long a[maxn],b[maxn],c[maxn];
long long rev[maxn],w[maxn],v[maxn];
long long ans;
long long q_pow(long long x,long long p)
{
    long long ans=1;
    while (p)
    {
        if (p&1)
            ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans;
}
void init()
{
    long long i,j,t;
    for (i=0;i<dft_len;i++)
        for (j=1,t=i;j<dft_len;j<<=1,t>>=1)
            rev[i]<<=1,rev[i]+=t&1;
    w[0]=1;
    w[1]=q_pow(g,(mod-1)/dft_len);
    for (i=2;i<=dft_len;i++)
        w[i]=w[i-1]*w[1]%mod;
}
void dft(long long a[],long long p)
{
    long long i,j,k,tot=dft_len,c,x,y;
    for (i=0;i<dft_len;i++)
        v[rev[i]]=a[i];
    for (i=2;i<=dft_len;i<<=1)
    {
        tot>>=1;
        c=p?dft_len:0;
        for (j=0;j<i>>1;j++)
        {
            for (k=j;k<dft_len;k+=i)
            {
                x=v[k];
                y=v[k+(i>>1)]*w[c]%mod;
                v[k]=(x+y)%mod;
                v[k+(i>>1)]=(x-y+mod)%mod;
            }
            if (p)
                c-=tot;
            else
                c+=tot;
        }
    }
    for (i=0;i<dft_len;i++)
        a[i]=v[i];
}
void ntt()
{
    long long inv=q_pow(dft_len,mod-2);
    init();
    dft(a,0);
    dft(b,0);
    for (i=0;i<dft_len;i++)
        c[i]=a[i]*b[i]%mod;
    dft(c,1);
    for (i=0;i<dft_len;i++)
        c[i]=c[i]*inv%mod;
}
int main()
{
    scanf("%d",&n);
    dft_len=1;
    while (dft_len<=n<<1)
        dft_len<<=1;
    fac_inv[0]=1;
    for (i=1;i<=n;i++)
        fac_inv[i]=(fac_inv[i-1]*i)%mod;
    for (i=0;i<=n;i++)
        fac_inv[i]=q_pow(fac_inv[i],mod-2);
    for (i=0;i<=n;i++)
        a[i]=i&1?(-fac_inv[i]+mod)%mod:fac_inv[i];
    b[0]=1;
    b[1]=n+1;
    for (i=2;i<=n;i++)
        b[i]=(q_pow(i,n+1)-1)*q_pow(i-1,mod-2)%mod*fac_inv[i]%mod;
    ntt();
    pow2=1;
    fac=1;
    for (i=0;i<=n;i++)
    {
        ans=(ans+pow2*fac%mod*c[i]%mod)%mod;
        pow2=(pow2<<1)%mod;
        fac=fac*(i+1)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

F Str

用SA求出height数组，暴力二分答案并查询，由于bzoj时限20s，所以最坏时间复杂度$O(nlogn+mnlogn)$刚好过了……（论玄学的威力QAQ）

正解需要离线处理，按照询问的a降序排序。线段树维护，二分查询。复杂度$O(mlog^2n)$。

～～～完结撒花～～～

谁说完结了？

E Sum

超级猎奇版本（缩小屏幕后食用更加）

#include                    <cstdio>
const long                 long N=1
<<19;  const               long long
mod=998244353;             long long
g=3;long long n,           i,dft_len
,pow2,j,  fac,ans;         long long
fac_inv[   N];long         long a[N]
,b[N],c     [N];long      long rev[N]
,w[N],v      [N];long      long q_pow
(  long        long x,     long long
p){long         long ans   =1;while(
p){if(p&         1) ans=  ans*x%mod;
x=x*x%            mod;p>>= 1;}return
ans;  }             void init(){long
long i,               t;for(i=0*0;i<
dft_len;               i++)for(j=2-1
,t=i;j<                 dft_len;j<<=
1,t>>=1)                 rev[i]<<=1,
rev[i]+=                  t&1;w[0]=1;


w[1]=q_pow(g,(mod-1)/dft_len);for (i=
2;i<=dft_len;i++)w[i]=w[i-1]*w[1]%mod;
}void dft(long long a[],long long p){
             long long
             i,j,k,tot
             =dft_len,
             c,x,y;for
             ( i=0; i<
             dft_len;i
             ++)v[rev[
             i]]=a[i];
             for(i=2;i
             <=dft_len
             ;i<<=2-1)
             {tot>>=1;
             c=p|p|p|p
             ?dft_len:
             0;for(j=0
             ;j<i>>1;j
             ++){for(k


=j;k<dft_len;k+=i){x=v[k];y=v[k+(i>>1)
]*w[c]%mod;v[k]=(x+y)%mod;v[k+(i>>1)]=
(x-y+mod)%mod;}if(p)c-=tot;else c+=tot;
             }}for(i=0;
             i<dft_len
             ;i++)a[i]
             =v[i]*1;}
             void ntt(
             ){/*ntt*/
             long long
             inv=q_pow
             (dft_len,
             mod-1-1);
             init();dft
             (a,0);dft
             (b,0);for
             (i=1-1;i<
             dft_len;i
             ++) c[i]=


           a[i]*b[i]%mod;
           dft(c,1);for(
           i=0;i<dft_len
           ;i++)c[i]=c[i
           ]*inv%mod+1-1
           ;}int main(){
           scanf("%d",&n
           );dft_len=1;;
           while(dft_len
           <=n*2)dft_len
           <<=1;fac_inv[
           0]=1;for(i=1;
           i<=n;i++,i=i)
           fac_inv[i]= (
           fac_inv[i-1]*
           i)%mod;for(i=
           1-1;i<=n;i++)
           fac_inv[i]=1*
           q_pow(fac_inv
            [i],mod-2);
            for(i=0;i<=
            n;i++)a[i]=
             i&1?(-1*1
             *fac_inv[
             i]+mod)%

           mod:fac_inv[i
           ];b[0]=1;b[1]
           =n+1;for(i=2;
           i<=n;i++)b[i]
           =(q_pow(i,n+1
           )-1)*q_pow(i-


  1,mod-2                                )%
mod                                      *
 fac_inv[                               i]
       %mod   ;; ntt();    pow2=1;      fac=1;       for(i=0      ;i<=n
        ;i++   ){    ans        =1-    1+(   ans   +pow2  *fac   %mod
        *c[i  ]%     mod    )%mod;     pow2=(pow2  <<1)%mod;;      fac=
       fac    *(i    +1)  %mod  ;}    i=i   ;i;    fac;             n++;
printf(       /*:    )*/   "%lld\n",  ans     );;    return 0;  n=n-i;}

～～～～真正的完结撒花～～～～