地精部落

定义 (f_{i,j}) 为当前数集大小为 i，尾数在相对大小关系中的排序为 j

转移的时候考虑在后面添加一个数字，在当前排列中排序为 k

如果满足，那么可以转移到 (f_{i+1,k} (kin {1,i+1}))

然后观察哪些位置可以被转移

对于一个 (f_{i,j}) 可以对大于等于它的数字造成贡献

所以反过来，我们维护前缀和就好了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,a,b) for(register int i=a;i<=b;++i)
namespace yspm{
    inline int read()
    {
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res*f;
    }
    const int N=4210;
    int n,mod,f[N][N],sum[N],ans;
    inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
    inline int del(int x,int y){return x-y<0?x-y+mod:x-y;}
    signed main()
    {
        n=read(); mod=read();
        f[1][1]=1; sum[1]=1;
        For(i,2,n)
        {
            if(i&1) For(j,1,i-1) f[i][j]=del(sum[i-1],sum[j-1]);
            else For(j,2,i) f[i][j]=del(sum[j-1],sum[0]);
            sum[0]=0; For(j,1,i) sum[j]=add(sum[j-1],f[i][j]);
        }
        For(i,1,n) ans=add(ans,f[n][i]); 
        memset(f,0,sizeof(f)); f[1][1]=1; sum[1]=1;
        For(i,2,n)
        {
            if(!(i&1)) For(j,1,i-1) f[i][j]=del(sum[i-1],sum[j-1]);
            else For(j,2,i) f[i][j]=del(sum[j-1],sum[0]);
            sum[0]=0; For(j,1,i) sum[j]=add(sum[j-1],f[i][j]);
        }
        For(i,1,n) ans=add(ans,f[n][i]); 
        cout<<ans<<endl; 
        return 0;
    }
}
signed main(){return yspm::main();}

T2

(bzoj4321)

首先按照原来的套路观察插入每个点的时候当前的序列的状态，然后插空

下面定义冲突为：(abs(p_i-p_{i+1})=1)

那么则有三种：

1.插空之后添加了

这里是把那个 i 插入到 i-1 后面或者前面了，同时不是 i-1 和 i-2 相连的那个位置

2.插空之后冲突的个数不变

原来 i-1 和 i-2 相连，然后把 i 插入到这两个中间

3.插空之后冲突的个数减少了

上面的情况，有 (j/j-1) 个空可以插进去

然后我们发现仅仅定义 (f_{i,j}) 表示i个数字，j个冲突是没法转移的

所以添加一维：(f_{i,j,0/1}) 表示 i 和 i-1 是不是相邻

对应状态进行转移即可

最后答案：(f_{n,0,0})

注意：这里考虑往下一层转移会相对好写一点

T3

(Luogu4309 [TJOI2013])最长上升子序列

这题 (O(n^2 log n)) 的在线做法比较简单

但是并不能通过

所以我们离线

先用vector模拟出来最终的序列，然后对它做 LIS

在这个过程中，我们考虑对于每个栈中的元素存一个vector

用 vector 中最小的那个元素做二分时候的代表

如果不开

#define int long long

那么vector过10万

（所以考场挂了30）

然后是正解部分：

1.可以考虑平衡树直接维护出来整个序列，不需要 (vector)

2.后面的查询答案的部分可以考虑一种 (O(n log n)) 的做法

用树状数组维护最大值（注意，只能是有限制的一部分的最大值，不能差分……）

考虑离线下来的序列每个数当作结尾的 (LIS)

对于每个数字，先查询比它小的数字中的 (LIS) 的最大值，然后加上1，再扔到树状数组里面

最后 (ans_i=max(ans_i,ans_{i-1}))

然后就做完了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,a,b) for(register int i=a;i<=b;++i)
namespace yspm{
    inline int read()
    {
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res*f;
    }
    const int N=1e5+10;
    vector<int> las;
    int n,id[N],pos,ans[N];
    struct node{
        int c[N];
        inline int lowbit(int x){return x&(-x);}
        inline void update(int x,int v)
        {
            for(;x<=n;x+=lowbit(x)) c[x]=max(c[x],v);
            return ;
        }
        inline int query(int x)
        {
            int res=0; 
            for(;x;x-=lowbit(x)) res=max(res,c[x]);
            return res;
        }
    }T;
    signed main()
    {
        n=read();
        For(i,1,n) pos=read(),las.insert(las.begin()+pos,i);
        For(i,0,n-1) ans[las[i]]=T.query(las[i])+1,T.update(las[i],ans[las[i]]);
        For(i,1,n) ans[i]=max(ans[i],ans[i-1]);
        For(i,1,n) printf("%lld
",ans[i]);
        return 0;
    }
}
signed main(){return yspm::main();}

T4

Luogu3320 SDOI2015寻宝游戏

考试的时候没时间想这题了，其实发现了总的路径长度是个二倍关系的相关性质

本质上面这题是个虚树的总边长的二倍？补习虚树去了……

然后是正经题解：

先思考总的路径怎么走最短，瞎走显然是不能做到最优解的

一种做法是按照 (dfn) 走，正确性？因为不会走重复的反向

（反正我这么着就理解了，但是如果理解不了的话可以考虑画画图）

然后用一种数据结构维护 (dfn) 的大小

每次如果添加一个点的话，那么要做的是把两边的距离断开，然后添加上 (l o now) 和 (now o r)，删掉(l o r)

删除的话就是把 (l o r) 加上，删掉那俩

找 (l,r) 用二分，边界需要特判一下

其实实现比较简单

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,a,b) for(int i=a;i<=b;++i) 
namespace yspm{
    inline int read()
    {
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res;
    }
    const int N=1e5+10;
    struct node{
        int to,dis,nxt;
    }e[N<<1];
    int head[N],cnt,dep[N],fa[N][20],dis[N],n,T,dfn[N],num,p[N],ans,l,r;
    bool vis[N];
    set<int> s; 
    inline void add(int u,int v,int w)
    {
        e[++cnt].to=v; e[cnt].dis=w; e[cnt].nxt=head[u];
        return head[u]=cnt,void();
    }
    inline void dfs(int x,int fat)
    {
        dep[x]=dep[fat]+1; fa[x][0]=fat; dfn[x]=++num; p[num]=x;
        for(int i=1;(1<<i)<=dep[x];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
        for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fat) dis[e[i].to]=dis[x]+e[i].dis,dfs(e[i].to,x);
        return ;
    }
    inline int lca(int x,int y)
    {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=19;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
        if(x==y) return x;
        for(int i=19;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
    inline int dist(int x,int y)
    {
        int lc=lca(x,y);
        return dis[x]+dis[y]-dis[lc]*2;
    }
    signed main()
    {
        n=read(); T=read();
        for(int i=1,u,v,w;i<n;++i) u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w); dfs(1,0);
        while(T--)
        {
            int x=read(); 
            if(!vis[x]) s.insert(dfn[x]); 
            x=dfn[x];
            l=s.lower_bound(x)==s.begin()?*(--s.end()):*(--s.lower_bound(x)); l=p[l];
            r=s.upper_bound(x)==s.end()?*s.begin():*s.upper_bound(x); r=p[r];
            x=p[x];
            if(vis[x]) s.erase(dfn[x]);
            int tmp=dist(l,x)+dist(x,r)-dist(l,r);
            if(vis[x]) ans-=tmp; else ans+=tmp; vis[x]=!vis[x];
            cout<<ans<<endl;
        } 
        return 0;
    }
}
signed main(){return yspm::main();}