标算复杂度似乎是$O(3^{n}*n^2)$的，但可以$O(2^{n}*n^3)$

首先枚举哪些点是叶子。(设枚举的点集为 $s_1$,剩下的点集为 $s_2$)

如何保证一个点 $i$ 是叶子？

只要让 $i$ 往 $s_2$ 连一条边就可以了。

所以方案数 $f[s_1]=$ $s_2$ 的生成树个数 $ \times \prod_{i,i \in s_1}$ $i$ 连向 $s_2$ 的边数。前一项可以用矩阵树求

但这样其实只能保证 ${\textbf s_1}$ 的点是叶子，却不能保证 ${\textbf s_2}$ 的点不是叶子。

现在要求只有 ${\textbf s}$ 的点是叶子的方案数 $ans[s]$，就再容斥一下:

$ ans[s]=\sum_{s',s' \supseteq s } f[s'] * (-1)^{|s'|-|s|} $

这个东西如果暴力的话因为每个点有三种状态所以复杂度$O(3^{n})$

但他其实类似高维前缀和，于是可以$O(2^{n}*n)$

答案就是$\sum_{s,|s|=k} ans[s]$

总复杂度是$\sum_{i=0}^{s} cnt[s-i]^{3}$ , 其中$s=2^{n}-1$,$cnt[s]$ 表示二进制数 $s$ 中 $1$ 的个数

当$n=10$时，这个值为$166400$

但我也不会算，就当它是$O(2^{n}*n^3)$吧

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

template <typename T> void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

struct vec
{
    int *a,n;
    void pb(int x)
    {
        if(n==(n&-n))
        {
            int *_a=new int [n*2];
            memcpy(_a,a,n*sizeof(int));
            a=_a;
        }
        a[n++]=x;
    }
};

const int N=10,U=1<<N;
int lk[N][N];
ll f[U];

int q[N];
ll qa[N][N],*a[N];
ll gauss(int m)
{
    ll ans=1;
    for(int i=0;i<m;++i)
    {
        for(int j=i+1;j<m;++j)
        {
            while(a[j][i])
            {
                ll bi=a[i][i]/a[j][i];
                for(int k=i;k<m;++k)
                 a[i][k]-=a[j][k]*bi;

                swap(a[i],a[j]);
                ans=-ans;
            }
        }
        ans*=a[i][i];
    }
    return ans;
}

int main()
{
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);

    for(int i=0;i<N;++i)a[i]=qa[i];

    int n=read(),m=read(),k=read();
    while(m--)
    {
        int x=read()-1,y=read()-1;
        ++lk[x][y];++lk[y][x];
    }
    int u=(1<<n)-1;
    for(int s=1;s<u;++s)
    {
        ll ans=1;

        m=0;
        for(int i=0;i<n;++i)
        if(!(s&(1<<i))) q[m++]=i;
        for(int i=0;i<n;++i)
        if(s&(1<<i)) 
        {
            int cnt=0;
            for(int j=0;j<m;++j) cnt+=lk[i][q[j]];
            ans*=cnt;
        }

        for(int i=0;i<m;++i)
        for(int j=0;j<m;++j)
         a[i][j]=0;

        for(int i=0;i<m;++i)
        for(int j=0;j<i;++j)
        {
          int w=lk[q[i]][q[j]];
          a[i][i]+=w;
          a[j][j]+=w;
          a[i][j]=a[j][i]=-w;
        }

        ans*=gauss(m-1);

        if((n-m-k)%2==1) f[s]=-ans;
        else f[s]=ans;
    }

    for(int i=0;i<n;++i)
    for(int s=0;s<u;++s)
    if( (s&(1<<i))==0 ) f[s]+=f[s+(1<<i)];

    ll ans=0;
    for(int s=0;s<u;++s)
    {
        int cnt=0;
        for(int i=0;i<n;++i)
        if(s&(1<<i))++cnt;
        if(cnt==k)ans+=f[s];
    }
    cout<<ans;
}

没有题解我来发一个。(同时来存模板)

http://acm.fzu.edu.cn/problem.php?pid=2246

第1种情况，t直接出现在s中。

那么要么割前面要么割后面。

求出t在s中第一次出现的位置和最后一次出现的位置即可。

第2种情况，t分成两半出现在s中。

那么枚举被分成哪两半，求出前缀在s中第一次出现的位置和后缀在s中最后一次出现的位置即可。

要求m个串的所有前缀在s中第一次出现的位置，建ac自动机，让s跑一遍就好了。

后缀的话全反过来做一遍就好了。

要注意: ac自动机中fail[i]不一定<i, 但深度顺序或者bfs序一定<i。(因为是i的后缀)

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
//#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define mid (l+r>>1)
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

template <typename T> inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

struct vec
{
    int *a,n;
    void pb(int x)
    {
        if((n&-n)==n)
        {
            int *_a=new int [n*2];
            memcpy(_a,a,n*sizeof(int));
            a=_a;
        }
        a[n++]=x;
    }
};
#define fore(arr) for(int *it=arr.a,*end=arr.a+arr.n;it!=end;++it)

const int N=1e5+500;
char s[N],T[N*2];int mn1[N*2],mn2[N],t[N],len[N];

int fail[N],ch[N][26],mn[N];int tot;
void ins(char *s)
{
    int i=1;
    for(char *c=s;*c>'0';++c)
    {
        int &to=ch[i][*c-'a'];
        i=to?to:(to=++tot);
    }
}
int q[N],tail;
void init_fail()
{
    tail=1;q[1]=1;
    for(int head=1;head<=tail;++head)
    {
        int i=q[head];
        int f=fail[i];
        rep(j,0,26-1)
        if(ch[i][j]) fail[q[++tail]=ch[i][j]]=ch[f][j];
        else ch[i][j]=ch[f][j];
    }
}
void travel(char *s)
{
    memset(mn+1,1<<5,tot*sizeof(int));
    int i=1,l=0;
    for(char *c=s;*c>'0';++c,++l) chmin(mn[i=ch[i][*c-'a']],l);
    for(int i=tot;i;--i) chmin(mn[fail[q[i]]],mn[q[i]]);
}
void Get(int *f,char *s)
{
    int i=1,l=0;
    for(char *c=s;*c>'0';++c,++l)
    {
        i=ch[i][*c-'a'];
        f[l]=mn[i];
    }
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    int tt=read();
    rep(j,0,25)ch[0][j]=1;
    while(tt--)
    {
        scanf("%s",s);
        int n=strlen(s);

        memset(ch+1,0,tot*sizeof(*ch));
        tot=1;

        int m;
        cin>>m;
        int nt=0;
        rep(i,1,m) 
        {
            scanf("%s",T+(t[i]=nt));
            len[i]=strlen(T+nt);
            ins(T+nt);
            nt+=len[i]+1;
        }
        init_fail();

        travel(s);
        rep(i,1,m) 
        {
            Get(mn1+t[i],T+t[i]);
        }

        reverse(s,s+n);
        rep(i,1,m) reverse(T+t[i],T+t[i]+len[i]);

        memset(ch+1,0,tot*sizeof(*ch));
        tot=1;

        rep(i,1,m) ins(T+t[i]);
        init_fail();

        travel(s);
        rep(i,1,m) 
        {    
           Get(mn2,T+t[i]);
           int l=len[i],*mn=mn1+t[i];
           int ans=max(n-1-mn[l-1],n-1-mn2[l-1]);
           rep(j,1,l-1) 
            chmax(ans, n-(mn[j-1]+1+mn2[l-1-j]+1) );
           if(ans<0) puts("-1");
           else printf("%d\n",ans);
        }
    }
}

题目链接

先考虑 $x^a=y^b$ 意味着什么

记 $p(x)$ 为最小的 $p$, 使得 $\exists k , p^k=x$。 那么 $x^a=p(x)^{k(x) \times a}$

则 $ x^a=y^b $ 等价于 $ p(x)^{k(x) \times a}=p(y)^{k(y) \times b}$ 等价于 $ p(x) = p(y) \land k(x) \times a = k(y) \times b $

考虑枚举 $p$ ，计算所有 $p(x)=p$ 的 $x$ 带来的重复

那么 使 $x$ 在给定区间 的 $k(x)$ 在一个区间中

于是问题转化为，求 $ card \{ i \times j \, | \, i \in [l_1,r_1] \, , j \in [l_2,r_2] \} $其中$l_1$,$r_1$为$O(log_2(n))$级别，$l_2$,$r_2$为 $O(n)$ 级别

容斥。

先加上在 $[l_1,r_1]$ 中任选一个数,并在 $[l_2,r_2]$ 任选一个数的方案数

再减去在 $[l_1,r_1]$ 任选两个数 $x,y$，并在 $[l_2,r_2]$ 任选两个数 $a,b$ ,使得$x \times a=y \times b$的方案数

再加上在 $[l_1,r_1]$ 任选三个数 $x,y,z$，并在 $[l_2,r_2]$ 任选三个数 $a,b,c$ ,使得$x \times a=y \times b=z \times c$的方案数 ......

可以发现 当 $[l_1,r_1]$ 中的数确定之后, $[l_2,r_2]$ 的方案数是可以算出来的 因为乘积一定为 $lcm$ 的倍数

设为 $x$ 倍 则$l_2 \le x \times lcm/max \, \& \& \, x \times lcm/min \le r_2$ 于是 $l_2 \times max \le x \times lcm \le r_2 \times min$

所以 $x$ 的取值数=$r_2 \times min/lcm - l_2 \times max/lcm +1$

于是暴力容斥复杂度 $=O(2^{r_1-l_1+1})=O(n)$

$l_1$,$r_1$一共有 $ log_2^2(n) $种

对于所有的一样的$l_1$,我们可以从小到大枚举$r_1$计算。 总复杂度还是 $O(n)$

当然还过不了

注意到 如果一个数选了之后对于$lcm,max,min$没有影响 那么他选和不选的贡献就会抵消

所以先枚举$max,min$ 之后$dfs$ 如果碰到对$lcm$无贡献的数，就直接退出

同时，如果选了它导致前面的数成为对$lcm$无贡献的数，那么它就不选

这样优化之后复杂度就很好了 李陶冶说"比较接近于光滑数的数量（其实比这个还要低一个数量级）"

但我不知道光滑数是什么东西 总之O(跑的过)

还有个问题，就是如何求出有多少个$p(x)$会使得$k(x)$在 $[l_1,r_1]$ 中

我是筛出$ \sqrt{n} $以内所有$p(x)=x$的$x$ 然后枚举 求更优的方法？

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int D=1e9+7,Lo=52;
int cnt[Lo+2][Lo+2];
ll L1,R1,l2,r2,ans,now;
void init()
{
    ll m,n,a,b;
    cin>>m>>n>>a>>b;
    ans=(m%D)*(n%D)%D;
    L1=a;R1=a+n-1;l2=b;r2=b+m-1;
}

int Gcd[Lo+2][Lo+2];
int gcd(int x,int y)
{
    while(y)swap(x%=y,y);
    return x;
}

int l1,r1,mn;
ll L,R;//L(=l2*mx)<=x*Lcm<=R(=r2*mn)   
int mx_p[Lo+5],st[Lo+5],*top;
#define len (R/Lcm - (L+Lcm-1)/Lcm +1)
void dfs(int *h,const ll &Lcm,bool ji)
{
    if(Lcm>R)return ;
    if(h>top)
    {
        if(ji)now-=len;
        else now+=len;
        return ;
    }
    int x=*h;
    if(Lcm%x==0) return ;
    //if(len<=0) return ;
    dfs(h+1,Lcm,ji);
    dfs(h+1,Lcm*(x/Gcd[x][Lcm%x]),ji^1);
}

const int U=8e7;
bool mark[U];

int main()
{
    //freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    init();
    int mp=sqrt(R1);
    for(int p=2;p<=mp;++p)
    if(!mark[p])
    {
        int k=0;
        ll x=1;
        while(x<L1&&x<=R1/p) { x*=p;if(x<=mp)mark[x]=1;++k; }
        if(x<L1||x>R1)continue;
        int l1=k; 
        while(x<=R1/p) { x*=p;if(x<=mp)mark[x]=1;++k; }
        if(k>l1)
        ++cnt[l1][k];
    }

    for(int i=1;i<=Lo;++i)
    for(int j=0;j<i;++j)
     Gcd[i][j]=gcd(i,j);
    for(int i=1;i<=Lo;++i)
    for(int j=1;j<i;++j)
    if(i%j==0) mx_p[i]=j; 

    for(l1=1;l1<=Lo;++l1)
    {
        int mr=0;
        for(r1=Lo;r1>l1;--r1)
        if(cnt[l1][r1]){mr=r1;break;}

        now=0;
        for(r1=l1+1;r1<=mr;++r1)
        {        
            L=l2*r1;
            for(mn=l1;mn<r1;++mn)
            {
               R=r2*mn;    
               if(L>R)continue;

               int Lcm=r1*(mn/gcd(r1,mn));
               int i=mn+1;
               for(;i<r1;++i)
               if(Lcm%i==0) break;
               if(i<r1)continue;

               top=st-1;
               for(int i=mn+1;i<r1;++i)
               if(mx_p[i]<=mn) 
                *++top=i;

               dfs(st,Lcm,0); 
            }
            now%=D;
            ans-=cnt[l1][r1]*now%D;
        }
    }
    cout<<(ans%D+D)%D;
}

先在线段树上二分得到 满足子树点权和>=总点权/2的 dfs序最大的点x

之后再考虑计算带权距离和，即 $ans(x)= \sum_{i} dis(i,x) * v[i]$

因为$dis(i,x)=deep[i]+deep[x]-2*deep[lca]$

所以$ans(x)=(\sum_{i} deep[i] * v[i]) + (deep[x]*\sum_{i} v[i]) -2*(\sum_{i} v[i]*deep[lca]) $

前两项直接维护

最后一个式子怎么算呢

就是每次 $v[i]$+=$x$ 就把$i$到根的路径上的点的$add$全部+=$x$

查询$ans(x)$时 就查询x到根的$\sum_{i} add[i]*(deep[i]-deep[fa[i]])$

线段树预处理区间$\sum_{i}(deep[i]-deep[fa[i]])$后可以维护

时间$O(nlog^2)$ 跑的还是挺快的

# pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define pb push_back
const int ch_top=1e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
int read()
{
    while(*++now_r<'-');
    if(*now_r=='-')
    {
        int x=*++now_r-'0';
        while(*++now_r>='0')x=x*10+*now_r-'0';
        return -x;
    }
    int x=*now_r-'0';
    while(*++now_r>='0')x=x*10+*now_r-'0';
    return x;
}
void write(ll x)
{
    static char st[20];static int top;
    if(!x)*++now_w='0';
    else
    {
        do{st[++top]='0'+x%10;}while(x/=10);
        do{*++now_w=st[top];}while(--top);
    }
    *++now_w='\n';
}

const int N=1e5+5,T=N*4;
struct edge
{
    int to,w;
};
int n,m;
vector<edge>lk[N];
int fa[N],deep[N],sz[N],son[N],top[N],dfn[N],tot;
int q[N];
void dfs(int x,int fr,int dep)
{
    fa[x]=fr;deep[x]=dep;sz[x]=1;
    vector<edge>::iterator i=lk[x].begin();
    while(i!=lk[x].end())
    {
        int y=i->to;
        if(y==fr){++i;continue;}
        dfs(y,x,dep+i->w);
        sz[x]+=sz[y];
        if(sz[y]>sz[son[x]])son[x]=y;
        ++i;
    }
}
void dfs2(int x,int ntop)
{
    q[dfn[x]=++tot]=x;top[x]=ntop;
    if(!son[x])return ;
    dfs2(son[x],ntop);
    for(vector<edge>::iterator i=lk[x].begin();i!=lk[x].end();++i)
    {
        int y=i->to;
        if(y==son[x]||y==fa[x])continue;
        dfs2(y,y);
    }
}

int x,w;
ll xs,s;
#define mid (l+r>>1)
#define cl (k*2)
#define cr (cl+1)
namespace seg
{
int ad[T],mx[T];ll s[T],xs[T];
int ql,qr;
inline void _add(int k,int x)
{
    ad[k]+=x;mx[k]+=x;
    xs[k]+=s[k]*x;
}
inline void down(int k)
{
    if(ad[k]){_add(cl,ad[k]);_add(cr,ad[k]);ad[k]=0;}
}
inline void up(int k)
{
    mx[k]=max(mx[cl],mx[cr]);
    xs[k]=xs[cl]+xs[cr];
}
void add(int k,int l,int r)
{
    if(ql<=l&&qr>=r){_add(k,w);return ;}
    down(k);
    if(ql<=mid)add(cl,l,mid);
    if(qr>mid)add(cr,mid+1,r);
    up(k);
}
void add(int l,int r)
{
    ql=l;qr=r;
    add(1,1,n);
}
void init(int k,int l,int r)
{
    if(l==r)
    {
        s[k]=deep[q[l]]-deep[fa[q[l]]];
        return ;
    }
    init(cl,l,mid);init(cr,mid+1,r);
    s[k]=s[cl]+s[cr];
}
int qiu(const ll &x)
{
    int k=1,l=1,r=n;
    while(l!=r)
    {
        down(k);
        if(mx[cr]>=x) {k=cr;l=mid+1;}
        else {k=cl;r=mid;}
    }
    return l;
}

ll ans;
void qiu(int k,int l,int r)
{
    if(ql<=l&&qr>=r){ans+=xs[k];return ;}
    down(k);
    if(ql<=mid)qiu(cl,l,mid);
    if(qr>mid)qiu(cr,mid+1,r);
}
ll qiu(int l,int r)
{
    ql=l;qr=r;ans=0;
    qiu(1,1,n);
    return ans;
}
};
void add_to_rt(int x)
{
    while(x)
    {
        int f=top[x];
        seg::add(dfn[f],dfn[x]);
        x=fa[f];
    }
}
ll qiu_s(int x)
{
    ll ans=0;
    while(x)
    {
        int f=top[x];
        ans+=seg::qiu(dfn[f],dfn[x]);
        x=fa[f];
    }
    return ans;
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    fread(ch,1,ch_top,stdin);
    n=read();m=read();
    rep(i,1,n-1)
    {
        int a=read(),b=read(),c=read();
        lk[a].pb((edge){b,c});lk[b].pb((edge){a,c});
    }
    dfs(1,0,0);
    dfs2(1,1);
    seg::init(1,1,n);
    while(m--)
    {
        x=read();w=read();
        add_to_rt(x);
        xs+=(ll)deep[x]*w;
        s+=w;
        x=q[seg::qiu(s+1>>1)];
        write(xs+s*deep[x]-2*qiu_s(x));
    }
    fwrite(ch,1,now_w-ch+1,stdout);
}

题目:https://www.luogu.org/problem/show?pid=1565

原题解似乎是 $O(n^3 * \log n)$ 的

但这题有$ O(n^3) $的做法。

虽然 https://www.luogu.org/record/show?rid=2494227 我这个$ O(n^3*\log n) $的做法跑的比我的$ O(n^3) $还快。。(应该是数据问题)

就是枚举上下边界$ x_1 $,$ x_2 $，然后枚举右端点 $ i $，

那么就是求最左的点 $ j $ 满足 $ sum_j < sum_i $ ( $ sum_i $ 表示 $ x=x_1...x_2,\,y=0...i $ 这个矩形的面积和)

如果 $ j_1 < j_2 $ 且 $ sum_{j_1} < sum_{j_2} $ ，那么 $j_2 $ 不可能成为左端点。

所以可以用单调栈维护可能的左端点，查询时二分。

$ O(n^3) $的做法:

(1) https://www.luogu.org/record/show?rid=2498503

枚举上下边界，实际上不只是可能的左端点在单调栈上，可以同理证明可能的右端点在相反的单调栈上。

从左到右枚举右端点(只枚举单调栈上的)，左端点的变化是单调的。于是可以$ O(n) $

(2) https://www.luogu.org/record/show?rid=2498807

感觉这是理论最快的做法。

原理是:当上下区间长度不变时 就是要求左右区间长度的最大值 $ mx $ , 而 $mx$ 最多变大 $ n $ 次。

长度从大到小地枚举上下边界(其实从小到大也一样)，再枚举右端点 $ i $ ，

如果以$i$为右端点的区间长度的最大值大于当前的$ mx $ ,那么 $ sum_i>min\,\, sum_j | j=[0,i-mx] $，这两者等价

所以维护这个$min$，如果发现$sum_i>min$，就++$ mx $，之后暴力重新$ O(n) $算出 $ min $。

如果上下区间长度从大到小枚举，其实长度不变或变小时都不用修改$mx$，于是最多重算$O(n)$次$min$。

从小到大枚举的话，当长度变大时需要将$mx$清0，于是最多重算$O(n^2)$次$min$。

总之总复杂度都是$O(n^3)$

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
template<class T>inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
template<class T>inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
typedef long long ll;
const int N=205;
ll s[N][N];
int ans;
ll a,_a;int w,_w;
#define get(y) (s[x2][y]-s[x1][y])

int main()
{
    freopen("1.in","r",stdin);freopen("2.out","w",stdout);
    int n,m;
    cin>>n>>m;
    rep(i,1,n)
    {
      rep(j,1,m)
      { 
        scanf("%lld",s[i]+j);
        s[i][j]+=s[i][j-1];
      }
      rep(j,1,m)
        s[i][j]+=s[i-1][j];
    }
    int mx=1;
    for(int t=n;t;--t)
    {
        int x1=0,x2=t;
      do
      {
          int i=mx;ll mn=0;//mn=min(get(0)..get(i-mx))
         do
         {
             chmin(mn,get(i-mx));
           while(get(i)>mn&&mx<=i)
           {++mx;
            mn=0;
            rep(j,1,i-mx) chmin(mn,get(j));
           }
         }while(++i<=m);
      }while(++x1,++x2<=n);
       chmax(ans,t*(mx-1));
    }
    printf("%d\n",ans);
}

迟了半个小时多才ak。。

我打的dp似乎是O(n^5)的(不过常数挺小的)，应该不是最优的

考虑到距离序列

一定是一段一段的

每段每个点都向上一段连一条边，并可能存在段内互连

用dp[x][y1][y2][n1][n2]表示做到第x个点，上一段有y1个点还能连1条边,y2个点2条，当前段有n1个点1条，n2个点2条。

当y1=y2=0时，考虑把这个点新开一段

枚举他和当前段连的是2条的点还是1条的点

否则把这个点作为当前段

枚举他和上个段连的是2条的点还是1条的点

并枚举他和当前段内的连边

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=52,D=1e9+7,W1=50,W2=50*50,W3=50*50*50,W4=50*50*50*50;
int n;
int d[N];ll c[N][N];
map<int,int>f[N];

int dp(int x,int y1,int y2,int n1,int n2)
{
    if(y1<0||y2<0||n1<0||n2<0)return 0;
    if(x>n) return y1==0&&y2==0&&n1==0&&n2==0;

    int now=y1*W3+y2*W2+n1*W1+n2;
    if(f[x].count(now)) return f[x][now];

    ll ans=0;
    if(y1==0&&y2==0)
    {
        rep(x1,0,1)
        {
           int x2=1-x1;
           ans+=c[n1][x1]*c[n2][x2]%D*dp(x+1,n1-x1+x2,n2-x2,d[x]-x1-x2==1,d[x]-x1-x2==2);
        }
    }
    else
    {
        rep(x1,0,1)
        {
         int x2=1-x1;
        if(y1-x1+x2>=0&&x2<=y2)
        {
           int nd=d[x]-x1-x2;
           rep(nx1,0,nd)
           rep(nx2,0,nd-nx1)
            ans+=c[y1][x1]*c[y2][x2]%D*c[n1][nx1]%D*c[n2][nx2]%D*
            dp(x+1,y1-x1+x2,y2-x2,n1-nx1+nx2+(nd-nx1-nx2==1),
                                  n2-nx2+(nd-nx1-nx2==2));
        }
        }
    }
    return f[x][now]=ans%D;
}

int main()
{
    freopen("1.in","r",stdin);
    scanf("%d",&n);
    rep(i,1,n)scanf("%d",d+i);
    rep(i,0,n)
    {
       c[i][0]=1;    
       rep(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%D;
    }
    printf("%d\n",dp(3,d[1]==2,d[1]==3,d[2]==2,d[2]==3));
}

两道题我都不知道有没有更优做法。。

https://daniu.luogu.org/problem/show?pid=3591

如果步长>根号的话，

步数就<根号，

直接暴力模拟每一步就可以了。

如何暴力模拟？

求出lca，问题就只剩下如何求一个点距离为k的祖先。

就是按size链剖，每条链记录每个深度的点。

找距离为k的祖先，如果当前这条链不够，就跳到下一条链。

这样最多一次询问只会跳log条链，时间是根号的。

(其实这个问题17年集训队论文里讲了梯子+倍增的O(1)做法，不过这题我这样做也就已经均摊O(1)了)

如果步长<根号的话，

我们就对每个这样的步长k特殊处理，那么也只用处理根号次。

就是dp出每个点距离为k的祖先，并处理出i,i-k,i-k*2...点权的前缀和。

询问时找到最浅那个i-k*x就可以了。

dp时间也是n根号的。

总时间n根号。

https://www.luogu.org/problem/show?pid=3751

对每个询问暴力模拟，时间应该是k[x]+k[y]的。

也就是每次选一个离下一个点较近的移动，之后判一下是不是起点的相对前后!=终点的相对前后。

如果k[x],k[y]都<根号，那么这是没问题的。

如果k[x],k[y]都>根号，那么记忆化一下，应该也是没问题的。

否则，如果我们能用较小的k的时间，那么也是ok的。

因为速度是一样的，所以x移动一次最多只会相遇一次，而且相对前后一旦变了就变不回去了。

所以只要每次移动x，之后二分一下y会移动到哪里就可以了。

时间O(n根号log)

我只想到了n根号(nlog)log的分块，感谢出题人教了我如何n根号log。

(假设分k块)

每个块内都排好序。

加的时候
整块的就打标记 O(k)
零散的，
考虑打标记后，没打标记的和打了标记的部分顺序都还是不变，
遍历一遍原来排好的顺序，就能得到这两个部分，之后归并一下就可以了。O(n/k)

求k大
先二分 转为check一个区间有多少数比一个数小。

按普通的想法
整块的二分 O(klog)
零散的暴力 O(n/k)
所以一次复杂度是O(klog^2+nlog/k)
k取根号(n/log),总复杂度就是O(n根号(nlog)log)

注意到，check零散的时间是O(nlog/k)，这还可以优化。
首先，用遍历一遍原来顺序的方法 O(n/k)把两个零散的各自排序。
之后check的时候就可以二分了，O(log^2)
所以一次复杂度变成O(klog^2+n/k)
k取根号n/log,总复杂度就是O(n根号nlog)

还有一个方法，是跟值域有关的。

因为值域小了，就可以处理出每个块的前缀和

分块使得
1 每个块max-min<=x1*len
2 块的大小也不超过x2
3 块尽量大

如果不考虑2的话 块是n/x1个的
因为所有相邻两数的差的和是nlen的 因为n次区间加，每次加len
而相邻两块的max-min>x1len
说明相邻两块所有相邻两数的差>max-min>x1len
所以块数<nlen/x1*len=n/x1

现在再把2考虑进来 相当于说一些大于x2的块要被拆掉
设大于x2的块的大小-x2的和是sum 那么每拆一次 sum-=x2
所以最多拆n/x2次

所以块数是n/x1+n/x2的。
因为所有块max-min的和<nlen，所以build的时间是nlen

check的时候
整块就可以O(1)
零散的暴力 就是x2
时间O(log*(n/x1+n/x2+x2))

加的时候整块打标记，O(n/x1+n/x2)
零散的暴力重算块的前缀和,O(x2+x1*len)

注意根号次加法后，块的max-min可能又大了根号*len，

这个时候要再重构一次分块。

时间(根号nlen)

x1,x2应该都要取根号

总时间O(n根号log+n根号len)

因为感觉第一种比较好写 我只写了第一种

#include<bits/stdc++.h>
using namespace std;

#define mid (l+r>>1)

const int ch_top=10000000;
char ch[ch_top],*now_r=ch,*now_w=ch-1;
int read()
{
    while(*now_r<'0')++now_r;
    int x=*now_r-'0';
    while(*++now_r>='0') x=x*10+*now_r-'0';
    return x; 
}
void write(int x)
{
    static char st[20];static short top;
    if(!x)*++now_w='0';
    else
    {
        for(;x;x/=10)st[++top]='0'+x%10;
        for(;top;--top)*++now_w=st[top];
    }
    *++now_w='\n';
}

const int N=100005,L=1500,K=N/L+5;
int f[N],w[N];vector<int>son[N];
typedef vector<int>::iterator ii;
int a[N],b[N];//b[i]是块排好序后的人 

int q[N],t,qa[N],la,qb[N],lb;
void merge_to(int *q)
{
    if(!lb) { memcpy(q+1,qa+1,la*sizeof(int));return ; }
    if(!la) { memcpy(q+1,qb+1,lb*sizeof(int));return ; }
    t=0;
    int ha=1,hb=1;
    for(;;)
    if(a[qa[ha]]<a[qb[hb]])
    {
        q[++t]=qa[ha];
        if(++ha>la) 
        {
            do
            {
                q[++t]=qb[hb];
            }while(++hb<=lb);
            break;
        }
    }
    else
    {
        q[++t]=qb[hb];
        if(++hb>lb) 
        {
            do
            {
                q[++t]=qa[ha];
            }while(++ha<=la);
            break;
        }
    }
}

int kl[K],kr[K],ad[K];
bool a_xiao(int x,int y)
{
    return a[x]<a[y];
}

void chmin(int &x,int y)
{
    if(x>y)x=y;
}
void chmax(int &x,int y)
{
    if(x<y)x=y;
}

int dfn[N],out[N],tot;
void dfs(int x,int fr,int now)
{
    now+=w[x];
    a[dfn[x]=++tot]=now;
    for(ii it=son[x].begin();it!=son[x].end();++it)
     dfs(*it,x,now);
    out[x]=tot;
}

int nl,nr;
int erfen(int *q,int t,int now)
{
    if(a[q[1]]>now)return 0;
    if(a[q[t]]<=now)return t;
    int l=1,r=t;
    while(l+1!=r)
    if(a[q[mid]]<=now) l=mid;
    else r=mid;
    return l;
}
int xiao_deng(int now)
{
   int ans=erfen(qa,la,now)+erfen(qb,lb,now);
   for(int k=nl+1;k<nr;++k) ans+=erfen(b+kl[k]-1,L/*kr[k]-kl[k]+1*/,now-ad[k]);
   return ans;
} 

void down(int k)
{
    int x=ad[k];
    if(!x)return ;
    for(int i=kl[k];i<=kr[k];++i) a[i]+=x;
    ad[k]=0;
}

int main()
{
    //freopen("1.in","r",stdin);freopen("3.out","w",stdout);
    ch[fread(ch,1,ch_top,stdin)]=0;
    int n=read(),m=read(),i,k;
    read();
    for(i=2;i<=n;++i)
    {
        son[f[i]=read()].push_back(i);
        w[i]=read();
    }

    dfs(1,0,0);

    tot=(n-1)/L;
    for(i=0;i<=tot+1;++i) {kl[i]=i*L+1;kr[i]=(i+1)*L;}
    kr[tot]=n;

    for(i=1;i<=n;++i)b[i]=i;
    for(k=0;k<=tot;++k)
        sort(b+kl[k],b+kr[k]+1,a_xiao);

    while(m--)
    {
        int type=read(),x=read();
        int ql=dfn[x],qr=out[x]; 
        //int ql=read(),qr=read();
        x=read();
        nl=(ql-1)/L;nr=(qr-1)/L;
        if(type==1)
        {
            int len=qr-ql+1;
            if(len<x) { *++now_w='-';*++now_w='1';*++now_w='\n';continue; }  
            down(nl);down(nr);
            if(len<=L*2)
            {
                down(nl+1);
                memcpy(q,a+ql,len*sizeof(int));
                nth_element(q,q+x-1,q+len);
                write(q[x-1]);
                continue;
            }
            else
            {
                la=0;
                for(i=kl[nl];i<=kr[nl];++i)
                if(b[i]>=ql) qa[++la]=b[i];
                lb=0;
                for(i=kl[nr];i<=kr[nr];++i)
                if(b[i]<=qr) qb[++lb]=b[i];
                //merge_to(q);

                int l=min(a[qa[1]],a[qb[1]]),r=max(a[qa[la]],a[qb[lb]]);
                for(k=nl+1;k<nr;++k) 
                {
                  chmin(l,a[b[kl[k]]]+ad[k]);
                  chmax(r,a[b[kr[k]]]+ad[k]); 
                }
                if(xiao_deng(l)>=x) { write(l);continue; }
                while(l+1!=r)
                {
                    if(xiao_deng(mid)>=x) r=mid;
                    else l=mid;
                }
                write(r);
            }
        }
        else
        {
            if(nl==nr)
            {
                for(i=ql;i<=qr;++i) a[i]+=x;
                la=lb=0;
                for(i=kl[nl];i<=kr[nl];++i) 
                if(b[i]>=ql&&b[i]<=qr) qa[++la]=b[i];
                else qb[++lb]=b[i];
                merge_to(b+kl[nl]-1);
                continue;
            }
            for(k=nl+1;k<nr;++k) ad[k]+=x;

            for(i=ql;i<=kr[nl];++i) a[i]+=x;
            la=0;lb=0;
            for(i=kl[nl];i<=kr[nl];++i)
            if(b[i]>=ql) qa[++la]=b[i];
            else qb[++lb]=b[i];
            merge_to(b+kl[nl]-1);

            for(i=kl[nr];i<=qr;++i) a[i]+=x;
            la=0;lb=0;
            for(i=kl[nr];i<=kr[nr];++i)
            if(b[i]<=qr) qa[++la]=b[i];
            else qb[++lb]=b[i];
            merge_to(b+kl[nr]-1);
        }
    }
    fwrite(ch,1,now_w-ch+1,stdout);
}

简要题意:
区间众数 强制在线 空间<n根号

区间众数的做法很普通
就是分根号块 预处理两块之间众数mx[i][j]，以及cnt[i][j]表示前i块中权值j出现次数
询问时要么众数是块间原本的众数 否则一定在多出来的里面出现过 时间n根号
由于cnt[i][j] 空间n根号

如何优化空间呢

特判掉出现次数<k的权值 这样cnt[i][j]中j就<=n/k 空间就变成n根号/k了

怎么特判呢 就是再用个l[k][i]表示出现次数=k时，右端点为i，第一次可以的那个左端点(也就是最大的那个)

我k取了3 (由于初始ans为清0，导致第一次就异或，wa了很久很久)

#include<cstdio>
#include<algorithm>
#include<string.h>
using std::sort;
using std::swap;

#define us unsigned short
#define gc getchar()
void read(us &x)
{
    char ch;
    while((ch=gc)<'0');
    for(x=ch-'0';(ch=gc)>='0';)x=x*10+ch-'0';
}
void read(int &x)
{
    char ch;
    while((ch=gc)<'0');
    for(x=ch-'0';(ch=gc)>='0';)x=x*10+ch-'0';
}

void chmax(us &x,us y)
{
    if(x<y)x=y;
}

#define B(i) ((i-1)/len)
const int K=240,N=60000,U=N/4+5;
us kl[K],kr[K];
us cnt[K][U],mx[K][K];
us n,m,i,j,l,len,k;
us a[N+5],top;bool del[N+5];
us now[U],st[N/K*2+10],stt,nowmx;
us dr[N+5],dl[N+5];
us l_2[N+5],l_3[N+5];//l_i[r]= 当右端点=[1,r]时，达到i需要的最大左端点 

struct item
{
    int a;us id;
    bool operator <(const item &i)const
    {
        return a<i.a;
    }
}q[N+5];
void mark(us l,us r)
{
    if(l>r)swap(l,r);
    del[l]=del[r]=1;chmax(l_2[r],l);
}
void mark(us a,us b,us c)
{
if(a>b)swap(a,b);
if(b>c)
{swap(b,c);
if(a>b)swap(a,b);
}
    del[a]=del[b]=del[c]=1;
    chmax(l_3[c],a);
    chmax(l_2[c],b);
    chmax(l_2[b],a);
}
void check(us i)
{
    if(i==1||(q[i].a!=q[i-1].a)) 
    {    
        del[q[i].id]=1; 
        --top;
    }else
    if(i==2||(q[i].a!=q[i-2].a)) 
    {
        mark(q[i].id,q[i-1].id); 
        --top;
    }else
    if(i==3||(q[i].a!=q[i-3].a))
    {
        mark(q[i].id,q[i-1].id,q[i-2].id);
        --top;
    }
}
void lisan()
{
    for(i=1;i<=n;++i){read(q[i].a);q[i].id=i;}
    sort(q+1,q+n+1);
    top=a[q[1].id]=0;
    for(i=2;i<=n;++i)
    {
     if(q[i].a!=q[i-1].a) 
     {
       check(i-1);++top;
     }
     a[q[i].id]=top;  
    }
    check(n);
}

void write(us x)
{
    putchar('-');
    for(;x;x/=10)st[++stt]=x%10;
    for(;stt;--stt)putchar('0'+st[stt]);
    putchar('\n');
}

us ql,qr,L,R;

int main()
{   freopen("1.in","r",stdin);freopen("2.out","w",stdout);
    read(n);read(m);
    lisan();

    us t=0;
    for(i=1;i<=n;++i)
    {
        if(del[i])dr[i]=t;
        else a[dr[i]=++t]=a[i];
    }
    dl[n+1]=++t;
    for(i=n;i;--i)
    {
        if(del[i])dl[i]=t;
        else dl[i]=--t;
    }
    t=dr[n];
    for(i=1;i<=n;++i) {chmax(l_2[i],l_2[i-1]);chmax(l_3[i],l_3[i-1]);}

    if(!t)
    {
        while(m--)
        {
            read(ql);read(qr);
                ql^=nowmx;qr^=nowmx;
            nowmx=(ql<=l_3[qr])?3:((ql<=l_2[qr])?2:1);
            write(nowmx);
        }
        return 0;
    }

    for(len=1;B(t)>=K||len<t/len;++len);
    kl[0]=1;
    for(i=len+1;i<=t;i+=len) {kr[B(i)-1]=i-1;kl[B(i)]=i;} 
    kr[k=B(t)]=t;

    for(i=0;i<=k;++i)
    {
        nowmx=0;
        for(j=i;j<=k;++j)
        {
          for(l=kl[j];l<=kr[j];++l)
          if(++now[a[l]]>nowmx)nowmx=now[a[l]];
          mx[i][j]=nowmx;
          if(!i)memcpy(cnt[j],now,(top+1)*2);
        }
        memset(now,0,(top+1)*2);
    }

    nowmx=0;
    while(m--)
    {
        read(ql);read(qr);
        ql^=nowmx;qr^=nowmx;
        L=B(dl[ql]);R=B(dr[qr]);
        if(L>=R) 
        {
            for(i=dl[ql];i<=dr[qr];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            nowmx=0;
            for(;stt;--stt) 
            {
              if(now[st[stt]]>nowmx)nowmx=now[st[stt]];
              now[st[stt]]=0;
            }
        }
        else
        {
            for(i=dl[ql];i<=kr[L];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            for(i=kl[R];i<=dr[qr];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            nowmx=mx[L+1][R-1];
            for(;stt;--stt) 
            {
              us &x=now[st[stt]];
              x+=cnt[R-1][st[stt]]-cnt[L][st[stt]];
              if(x>nowmx)nowmx=x;
              x=0;
            }
        }
        if(nowmx<3)
        {
         if(ql<=l_3[qr])nowmx=3;
         else
         if(nowmx<2)
         {
           if(ql<=l_2[qr])nowmx=2;
           else
           if(nowmx<1)nowmx=1; 
         }
        }
        write(nowmx);
    }
}

s是c的后缀，倒过来，s就是c的前缀。

之后建trie树，所有c就是s的子树。

所以问题就转化了求子树k大。

由于可以离线，所以可以把询问挂在节点上。

dfs一遍，用直接转移重儿子,暴力轻儿子的方法维护当前的权值线段树，时间O(nlog^2)。

有了权值线段树，询问时只用O(log)。

感觉会比主席树快，没试过。

加了fread,fwrite后拿了rank1

#include<bits/stdc++.h>

#define gc getchar()
int read()
{
    char ch;
    while((ch=gc)<'0');
    int x=ch-'0';
    while((ch=gc)>='0')x=x*10+ch-'0'; 
    return x;
}

const int N=100005,T=300005;
int dy[N],j;
int ch[T][26],tot=1;
int cnt[T],t[T],next[N];
int sz[T],dfn[T],out[T],q[N],son[T];
int k[N],ans[N];

int a[N*3],d;
void clear(int i)
{
    for(i+=d;i;i>>=1)--a[i];
}
void add(int i)
{
    for(i+=d;i;i>>=1)++a[i];
}
#define L (i<<1)
int qiu(int k)
{
    if(k>a[1]) return -1;
    int i=1;
    while(i<=d)
    if(k<=a[L])i=L;
    else { k-=a[L];i=L+1; }
    return i-d;
}

char s[T];int len;
int to(int &x)
{
    if(!x)x=++tot;
    return x;
}

void dfs(int x)
{
    dfn[x]=tot+1;
    int i,y;
    for(i=t[x];i;i=next[i]) q[++tot]=i;

    for(i=0;i<26;++i) 
    if(y=ch[x][i]) 
    {
        dfs(y);
        if(sz[y]>sz[son[x]]) son[x]=y;
    }

    sz[x]=(out[x]=tot)-dfn[x]+1;
}
void solve(int x)
{
    int i,y,c=son[x];
    if(sz[c])
    {
        for(i=0;i<26;++i)
        if((y=ch[x][i])!=c&&sz[y]) 
        {solve(y); 
         for(j=dfn[y];j<=out[y];++j) clear(q[j]);
        }
        solve(c);
        for(j=dfn[x];j<dfn[c];++j) add(q[j]);
        for(j=out[x];j>out[c];--j) add(q[j]);
    }
    else 
    for(j=dfn[x];j<=out[x];++j) add(q[j]);

    for(j=0;j<cnt[x];++j)
    {
        i=q[dfn[x]+j];
        ans[i]=qiu(k[i]);
    }
}

int main()
{

    int n=read(),i,now,x;
    for(i=1;i<=n;++i)
    {
        scanf("%s",s+1);len=strlen(s+1);
        now=1;
        for(j=len;j;--j) now=to(ch[now][s[j]-'a']);
        ++cnt[dy[i]=now];
        next[i]=t[now];t[now]=i;
    }
    for(i=1;i<=n;++i) k[i]=read();

    for(d=1;d<n;d*=2);d-=1;
    tot=0;
    dfs(1);
    solve(1);

    for(i=1;i<=n;++i) printf("%d\n",ans[i]);
}