T1

离散化后线段树维护\(dp\),\(fi\)表示最小值为\(i\)时最多点亮多少个，

区间操作即可。

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
namespace EMT{
    #define pf printf
    #define int long long
    #define F(i,a,b) for(register int i=a;i<=b;i++)
    #define D(i,a,b) for(register int i=a;i>=b;i--)
    typedef long long ll;
    inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
    inline int min(int a,int b){return a<b?a:b;}inline int max(int a,int b){return a>b?a:b;}
    inline void pi(int x){pf("%lld ",x);}inline void pn(){pf("\n");}const int N=1e5+100;
    inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
    int n;int a[N<<4],b[N<<4],s[N<<4],cnt;
    struct tree{int val,lz;}t[N<<4];
    inline void down(int p){
        if(t[p].lz){
            t[p<<1].lz+=t[p].lz;t[p<<1|1].lz+=t[p].lz;
            t[p<<1].val+=t[p].lz;t[p<<1|1].val+=t[p].lz;
            t[p].lz=0;
        }
    }
    inline void up(int p){
        t[p].val=max(t[p<<1].val,t[p<<1|1].val);
    }
    inline void add(int p,int l,int r,int ql,int qr){
        if(ql>qr)return;
        if(l>=ql&&r<=qr){
            ++t[p].lz;++t[p].val;
            return;
        }down(p);
        int mid=(l+r)>>1;
        if(qr<=mid)add(p<<1,l,mid,ql,qr);
        else if(ql>mid)add(p<<1|1,mid+1,r,ql,qr);
        else add(p<<1,l,mid,ql,mid),add(p<<1|1,mid+1,r,mid+1,qr);
        up(p);
    }
    inline int getmax(int p,int l,int r,int ql,int qr){
        if(ql>qr)return 0;
        if(l>=ql&&r<=qr){
            return t[p].val;
        }down(p);
        int mid=(l+r)>>1;
        if(qr<=mid)return getmax(p<<1,l,mid,ql,qr);
        if(ql>mid)return getmax(p<<1|1,mid+1,r,ql,qr);
        return max(getmax(p<<1,l,mid,ql,mid),getmax(p<<1|1,mid+1,r,mid+1,qr));
    }
    inline void change(int p,int l,int r,int x,int v){
        if(l==r){
            t[p].val=max(t[p].val,v);
            return;
        }down(p);
        int mid=(l+r)>>1;
        if(x<=mid)change(p<<1,l,mid,x,v);
        else change(p<<1|1,mid+1,r,x,v);
        up(p);
    }
    inline short main(){
        n=read();
        F(i,1,n)s[++cnt]=a[i]=read(),s[++cnt]=b[i]=read();
        std::sort(s+1,s+cnt+1);
        int len=std::unique(s+1,s+cnt+1)-s-1;
        F(i,1,n)a[i]=std::lower_bound(s+1,s+len+1,a[i])-s,b[i]=std::lower_bound(s+1,s+len+1,b[i])-s;
        F(i,1,n){
            if(a[i]<=b[i]){
                int x=getmax(1,1,len,b[i]+1,len);
                change(1,1,len,a[i],x+1);
            }else{
                int x=getmax(1,1,len,a[i],len);
                change(1,1,len,a[i],x+1);
                add(1,1,len,b[i]+1,a[i]-1);
            }
        }
        pi(getmax(1,1,len,1,len));
        return 0;
    }
}
signed main(){return EMT::main();}

T2

用一手主席树，按照深度插入，这里历史版本比较特殊，还要边插入边修改，

判断和上个版本的相似情况即可。

set维护dfs序，在i与i的前趋、后继的lca处分别减1，前趋后继的lca处加1,每次查找前趋后继为O(logn).

ps：主席树的ls和rs不再是\(p<<1\)和\(p<<1|1\)了！调了半天。

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
namespace EMT{
    #define pf printf
    #define F(i,a,b) for(register int i=a;i<=b;i++)
    #define D(i,a,b) for(register int i=a;i>=b;i--)
    typedef long long ll;//(double)clock() / (double)CLOCKS_PER_SEC;
    inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
    inline int min(int a,int b){return a<b?a:b;}inline int max(int a,int b){return a>b?a:b;}
    inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}
    inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
    const int N=1e5+100;
    int n,m,c[N],deep[N],head[N],co,ti,time[N];
    struct node{int next,to;}e[N];
    struct tp{int top,son,size,dfn,fa;}w[N];
    struct pt{int id,deep,pre,nxt;}p[N];
    inline void add(int next,int to){e[++co].next=head[next],e[co].to=to;head[next]=co;}
    inline void dfs1(int k){
        w[k].son=-1;w[k].size=1;
        for(register int i=head[k];i;i=e[i].next){
            w[e[i].to].fa=k;deep[e[i].to]=deep[k]+1;
            dfs1(e[i].to);
            w[k].size+=w[e[i].to].size;
            if(w[k].son==-1||w[w[k].son].size<w[e[i].to].size)w[k].son=e[i].to;
        }
    }
    inline void dfs2(int k,int tp){
        w[k].top=tp;w[k].dfn=++ti;time[ti]=k;
        if(w[k].son==-1)return;
        dfs2(w[k].son,tp);
        for(register int i=head[k];i;i=e[i].next)
            if(e[i].to!=w[k].son)
                dfs2(e[i].to,e[i].to);
    }
    inline int getlca(int x,int y){
        int fx=w[x].top,fy=w[y].top;
        while(fx!=fy){
            if(deep[fx]>=deep[fy])x=w[fx].fa;
            else y=w[fy].fa;
            fx=w[x].top,fy=w[y].top;
        }if(deep[x]>=deep[y])return y;return x;
    }
    inline bool cmp(pt a,pt b){return a.deep<b.deep;}
    std::set<int>v[N];
    int root[N],tot,sum[N*40],ls[N*40],rs[N*40];
    inline void up(int p){
        sum[p]=0;
        if(ls[p])sum[p]+=sum[ls[p]];
        if(rs[p])sum[p]+=sum[rs[p]];
    }
    inline void add(int x,int &y,int l,int r,int t,int v){
        if(!y){
            y=++tot;sum[y]=sum[x];ls[y]=ls[x];rs[y]=rs[x];
        }if(l==r){sum[y]+=v;return;}
        int mid=(l+r)>>1;
        if(t<=mid){if(ls[x]==ls[y])ls[y]=0;add(ls[x],ls[y],l,mid,t,v);}
        else {if(rs[x]==rs[y])rs[y]=0;add(rs[x],rs[y],mid+1,r,t,v);}
        up(y);
    }
    inline int query(int p,int l,int r,int ql,int qr){
        if(l>=ql&&r<=qr)return sum[p];
        int mid=(l+r)>>1;
        if(qr<=mid)return query(ls[p],l,mid,ql,qr);
        if(ql>mid)return query(rs[p],mid+1,r,ql,qr);
        return query(ls[p],l,mid,ql,mid)+query(rs[p],mid+1,r,mid+1,qr);
    }
    inline short main(){
        //file();
        n=read(),m=read();
        F(i,1,n)c[i]=read(),p[i].id=i;
        F(i,2,n){int x=read();add(x,i);}
        deep[1]=1;
        dfs1(1);dfs2(1,1);
        F(i,1,n)p[i].deep=deep[i];
        std::sort(p+1,p+n+1,cmp);
        F(i,1,n){
            add(root[p[i].deep-1],root[p[i].deep],1,n,w[p[i].id].dfn,1);
            v[c[p[i].id]].insert(w[p[i].id].dfn);
            std::set<int>::iterator it1,it;it1=it=v[c[p[i].id]].find(w[p[i].id].dfn);
            if(it==v[c[p[i].id]].begin())p[i].pre=0;else it--,p[i].pre=time[*it];
            it1++;
            if(it1==v[c[p[i].id]].end())p[i].nxt=0;else p[i].nxt=time[*it1];
            if(p[i].nxt)add(root[p[i].deep-1],root[p[i].deep],1,n,w[getlca(p[i].nxt,p[i].id)].dfn,-1);
            if(p[i].pre)add(root[p[i].deep-1],root[p[i].deep],1,n,w[getlca(p[i].pre,p[i].id)].dfn,-1);
            if(p[i].nxt&&p[i].pre)
                        add(root[p[i].deep-1],root[p[i].deep],1,n,w[getlca(p[i].pre,p[i].nxt)].dfn,1);
        }
        F(i,1,m){
            int u=read(),d=read();
            pi(query(root[min(deep[u]+d,p[n].deep)],1,n,w[u].dfn,w[u].dfn+w[u].size-1));
            pn();
        }
        return 0;
    }
}
signed main(){return EMT::main();}

T3

设\(f_{i,j}\)表示到\(i\)点长度为\(j\)的方案数

\(p_i\)为上一个相似的字符位置，

则有：

f[i][j]=f[i-1][j]+f[i-1][j-1]-(p[i][s[i]-'a']?f[p[i][s[i]-'a']-1][j-1]:0))

递推即可

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
namespace EMT{
    #define pf printf
    #define F(i,a,b) for(register int i=a;i<=b;i++)
    #define D(i,a,b) for(register int i=a;i>=b;i--)
    typedef long long ll;
    inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
    inline int min(int a,int b){return a<b?a:b;}inline int max(int a,int b){return a>b?a:b;}
    inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}
    const int N=3e3+10;const int mod=998244353;
    inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
    int n,l,p[N][30],f[N][N];char s[N];
    inline void db(){pf("debug\n");}
    inline short main(){
        int x=scanf("%s",s+1);
        l=read();n=strlen(s+1);
        F(i,2,n){
            F(j,0,25){
                p[i][j]=p[i-1][j];
            }p[i][s[i-1]-'a']=i-1;
        }
        f[1][1]=1;
        F(i,2,n){f[i][1]=p[i][s[i]-'a']?f[i-1][1]:f[i-1][1]+1;F(j,2,min(i-1,l))f[i][j]=((f[i-1][j]+f[i-1][j-1]-(p[i][s[i]-'a']?f[p[i][s[i]-'a']-1][j-1]:0))%mod+mod)%mod;f[i][i]=1;}
        pi(f[n][l]);
        return 0;
    }
}
signed main(){return EMT::main();}