T3：

題意：給出一棵樹，有點權和邊權，有兩種操作，一種是將一條路徑上的點權修改成min(v[x],a?dis[x]+b)，dis[x] 表示x到起點的距離（只算邊權）。另一種是詢問a到b路徑中最小的點權。
第一種修改可以看成是往樹上的一段區間中加入一個線段。這個東西可以用線段樹維護。用線段樹維護這個區間的線段的斜率和截距。每次向這個區間中加入一條新的線段的時候，看一下這段區間中原來的線段和新加入的線段哪一個對這段區間的影響更大，將影響小的線段下放到它有影響的子樹，每次一直這樣下放到葉子節點。這樣每次插入的復雜度是O(log2n)。
每次查詢的時候只需要看一下這段區間中的最小值和這段區間中所保存的線段的兩個端點的情況就行了，復雜度是O(logn)。
這道題每次的dis數組還是不知道的，可以在加入線段的時候順便將lca傳進去（常數大了好多。。。）
再加上鏈剖，總的復雜度就是O(nlog3n)
code:

#include
#include
#include
#include
using namespace std;
#define mid (l+r)/2
#define L k<<1,l,mid
#define R k<<1|1,mid+1,r
#define LL long long
#define D 123456789123456789LL
const int N=100010;
LL dis[N],a,b;
struct S{int st,en,va;}aa[N<<1];
struct T{int lca,st,kind;LL k,b,minn;}tr[N<<2];
int n,m,point[N],next[N<<1],tot,deep[N],siz[N],son[N],belong[N],fa[N][21],q[N],pos[N],dfsn,cur[N],lca,to[N],flag[N<<2];
inline int in(){
    int f=1,x=0;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 IN(){
    LL f=1,x=0;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 void add(int x,int y,int z){
    next[++tot]=point[x];point[x]=tot;
    aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;
    next[++tot]=point[y];point[y]=tot;
    aa[tot].st=y;aa[tot].en=x;aa[tot].va=z;
}
inline void prepare(){
    int h=1,t=1,u,i,j;
    q[h]=1;
    while(h<=t){
        u=q[h];
        for(i=point[u];i;i=next[i])
          if(aa[i].en!=fa[u][0]){
            q[++t]=aa[i].en;
            deep[aa[i].en]=deep[u]+1;
            fa[aa[i].en][0]=u;
            dis[aa[i].en]=dis[u]+(LL)aa[i].va;
            for(j=1;j<=20;++j)
              fa[aa[i].en][j]=fa[fa[aa[i].en][j-1]][j-1];
          }
        h+=1;
    }
    for(i=t;i;--i){
        u=q[i];siz[u]=1;
        for(j=point[u];j;j=next[j])
          if(aa[j].en!=fa[u][0]){
            siz[u]+=siz[aa[j].en];
            if(siz[aa[j].en]>siz[son[u]]) son[u]=aa[j].en;
          }
    }
    int now=1;
    for(i=1;i<=n;++i) cur[i]=point[i];
    while(now){
        if(!pos[now]){
            pos[now]=++dfsn;
            to[dfsn]=now;
            belong[now]=(now==son[fa[now][0]] ? belong[fa[now][0]] : now);
            now=(son[now] ? son[now] : fa[now][0]);
        }
        else{
            for(i=cur[now];i&&(aa[i].en==fa[now][0]||aa[i].en==son[now]);i=next[i]);
            cur[now]=next[i];
            belong[aa[i].en]=aa[i].en;
            now=(i ? aa[i].en : fa[now][0]);
        }
    }
}
inline int LCA(int x,int y){
    if(deep[x]=r){
        LL minn=D;
        minn=min(minn,calc(l,now.lca,now.st,now.kind)*now.k+now.b);
        minn=min(minn,calc(r,now.lca,now.st,now.kind)*now.k+now.b);
        now.minn=tr[k].minn=min(tr[k].minn,minn);
        if(!flag[k]){
            flag[k]=1;
            tr[k]=now;
            return ;
        }
        int o1=calc(l,now.lca,now.st,now.kind)*now.k+now.bmid) insert(R,x,y,now);
    tr[k].minn=min(tr[k].minn,min(tr[k<<1].minn,tr[k<<1|1].minn));
}
inline LL query(int k,int l,int r,int x,int y){
    LL minn=D;
    if(x<=l&y>=r){
        LL o_l=calc(l,tr[k].lca,tr[k].st,tr[k].kind);
        LL o_r=calc(r,tr[k].lca,tr[k].st,tr[k].kind);
        return min(tr[k].minn,min(o_l*tr[k].k+tr[k].b,o_r*tr[k].k+tr[k].b));
    }
    minn=min(minn,calc(max(x,l),tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b);
    minn=min(minn,calc(min(y,r),tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b);
    if(x<=mid) minn=min(minn,query(L,x,y));
    if(y>mid) minn=min(minn,query(R,x,y));
    return minn;
}
inline void change(int x,int y,int st,int kind){
    int i,j;
    T now=(T){lca,st,kind,a,b,D};
    while(belong[x]!=belong[y]){
        insert(1,1,n,pos[belong[x]],pos[x],now);
        x=fa[belong[x]][0];
    }
    insert(1,1,n,pos[y],pos[x],now);
}
inline LL ask(int x,int y){
    LL minn=D;
    while(belong[x]!=belong[y]){
        minn=min(minn,query(1,1,n,pos[belong[x]],pos[x]));
        x=fa[belong[x]][0];
    }
    minn=min(minn,query(1,1,n,pos[y],pos[x]));
    return minn;
}
int main(){
    int i,j,x,y,t,z;
    n=in();m=in();
    for(i=1;i

#include
#include
#include
#include
using namespace std;
#define LL long long
#define inf 0x7fffffff
const int N=100010;
struct S{int minn,maxn;}tr[N<<2];
int n,a[N],b[N],m,t1[N],t2[N],sa[N],rank[N],c[N],height[N],st[N][21],Log[N];
inline int in(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline bool cmp(int *y,int p,int q,int k){
    int o0,o1;
    o0=(p+k>=n)?-1:y[p+k];
    o1=(q+k>=n)?-1:y[q+k];
    return o0==o1&&y[p]==y[q];
}
inline void build_sa(){
    int i,k,p,*x=t1,*y=t2;
    for(i=0;i=k) y[p++]=sa[i]-k;
        for(i=0;i=n) break;
    }
}
inline void build_height(){
    int i,j,k=0;
    for(i=0;i=r) return tr[k];
    if(x<=mid) ans1=query(L,x,y),f1=true;
    if(y>mid) ans2=query(R,x,y),f2=true;
    if(f1&&f2) return update(ans1,ans2);
    else return f1?ans1:ans2;
}
int main(){
    int i;
    n=in();
    for(i=n-1;~i;--i) a[i]=b[i]=in();
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    for(i=0;i

#include
#include
#include
using namespace std;
#define LL long long
#define Mod 1000000007LL
const int M=1000000;
LL f[M+10],g[M+10];
int T,n,m;
inline int in(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline LL quickpow(LL x,LL y){
    LL ans=1;
    while(y){
        if(y&1LL) ans=(ans*x)%Mod;
        y>>=1LL; x=(x*x)%Mod;
    }
    return ans;
}
int main(){
    int i;  
    T=in();
    for(f[1]=0LL,f[2]=1LL,f[0]=1LL,i=3;i<=M;++i) f[i]=(LL)(i-1)*((f[i-1]+f[i-2])%Mod)%Mod;
    for(g[1]=g[0]=1LL,i=2;i<=M;++i) g[i]=(g[i-1]*(LL)i)%Mod;
    while(T--){
        n=in();m=in();
        if(m>n){
            printf("0\n");
            continue;
        }
        LL ans=f[n-m]*((g[n]*quickpow(g[m],Mod-2)%Mod)*quickpow(g[n-m],Mod-2)%Mod)%Mod;
        printf("%lld\n",ans);
    }
}

#include
#include
#include
using namespace std;
#define LL long long
const int N=3010;
LL f[N][N],a[N];
int n,m,h[N],t[N],q[N][N];
inline LL pow(LL x){return x*x;}
inline LL get_son(int x,int y,int z){
    return f[z][x]+pow(a[x])-f[z][y]-pow(a[y]);
}
inline LL get_fa(int x,int y){
    return a[x]-a[y];
}
inline LL calc(int x,int y,int z){
    return f[z][x]+pow(a[y]-a[x]);
}
int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i) 
      scanf("%lld",&a[i]),a[i]+=a[i-1];
    memset(f,127/3,sizeof(f));
    for(j=0;j<=m;++j) f[j][0]=0,q[j][h[j]=t[j]=1]=0;
    for(j=1;j<=m;++j)
      for(i=1;i<=n;++i){
        while(h[j-1]