来自FallDream的博客，未经允许，请勿转载，谢谢。

----------------------------------------------------------------------------------------

我写完A题拍不出错，感觉没问题，交上去全RE，发现我竟然在倍增的时候把0的父亲写成了-1   脑抽爆0了..   本来可以300的

----------------------------------------------------------------------------------------

A.summing

你有一棵以 你有一棵以 0为根，n个节点的树  n<=500000

定义：点u的等级为点u到根的距离，树的高度h为树上所有点的等级中最大值F(l,k)表示子树中等级为l的点数量不小于k的点的数量

现在给你 现在给你 h+1个常数 a0,a1,a2,…,ah，请你求出 ，请你求出 ，请你求出 $\sum_{i=0}^{h}F(i,ai)$

题解：我们发现答案只会在相邻两个点的lca处变化，所以可以把同一个等级的点全部拿出来，然后把它们lca的深度塞进一个pq，每次更新答案就可以了。合并次数最多n次，复杂度nlogn

我脑抽，改了就过了。

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long long#define MN 500000#define MK 20using namespace std;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;}struct eve{    int dep,x,y;    bool operator<(const eve&b)const{
   return dep
         
          
            q;ll ans=0,now=0;int n,h,fa[MN+5][MK+5],cnt=0,head[MN+5],a[MN+5],s[MN+5],dep[MN+5],size[MN+5];struct edge{ int to,next;}e[MN*2+5];vector
           
             v[MN+5];void ins(int f,int t){ e[++cnt]=(edge){t,head[f]};head[f]=cnt; e[++cnt]=(edge){f,head[t]};head[t]=cnt;}void dfs(int x,int f){ v[dep[x]].push_back(x);fa[x][0]=f; for(int i=head[x];i;i=e[i].next) if(e[i].to!=f) { dep[e[i].to]=dep[x]+1; dfs(e[i].to,x); }}int lca(int x,int y){ if(dep[x]
            
             >=1) if(i&1) x=fa[x][j]; if(x==y)return x; for(int i=MK;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0];}int getfa(int x){ return s[x]==x?x:s[x]=getfa(s[x]);}void Merge(int x,int y,int lim){ int f1=getfa(x),f2=getfa(y); now-=(size[f1]>=lim)+(size[f2]>=lim); s[f1]=f2,size[f2]+=size[f1]; now+=(size[f2]>=lim);}int main(){ freopen("summing19.in","r",stdin); freopen("summing.out","w",stdout); n=read();h=read();int xx; for(int i=1;i
            
           
          
         
        
       
      
     

B.三角形规划 (你的三角形已如风中残烛) 这个是上次校内训练赛的题..详见的C题

#include
     
      #include
      
       #include
       
        #include
        
         #define eps 1e-10#define INF 2000000000#define T 9851#define S 0#define ld long doubleusing namespace std;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;} int head[T+5],d[T+5],q[T+5],cnt=1,n,tot,top,c[T+5];struct edge{    int to,next;ld w;}e[1200000];bool b[55][55]; void ins(int f,int t,ld w){    e[++cnt]=(edge){t,head[f],w};head[f]=cnt;    e[++cnt]=(edge){f,head[t],0};head[t]=cnt;} ld dfs(int x,ld f){    if(x==T)return f;    ld used=0;    for(int&i=c[x];i;i=e[i].next)    if(e[i].w>0&&d[e[i].to]==d[x]+1)    {        ld w=dfs(e[i].to,min(f-used,e[i].w));        used+=w;e[i].w-=w;e[i^1].w+=w;        if(fabs(f-used)
         
          0&&!d[e[j].to])                d[q[++top]=e[j].to]=d[q[i]]+1;    return d[T]>0;} void solve(int x){    if(!d[x])    {        d[x]=1;        for(int&i=head[x];i;i=e[i].next)            if(e[i].w>1e-6)                solve(e[i].to);    }} int main(){    freopen("triangle.in","r",stdin);    freopen("triangle.out","w",stdout);    tot=n=read();    for(int i=1;i<=n;i++)        ins(S,i,0);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            b[i][j]=read();    for(int i=1;i
         
        
       
      
     

C.给定一个n个数的序列ai，求有多少对(i,j)满足ai*aj<=max(ai..aj)   n<=100000

题解：枚举最大值是哪一个，往两边二分出它是最大值的范围，在两端较小的那一段枚举，另一端在主席树上查最值就行了。由于我们取较小的范围，所以查询次数最多nlogn次，复杂度$nlog^{2}n$

#include
     
      #include
      
       #include
       
        #define ll long long#define INF 1000000000#define MN 100000#define MK 17using namespace std;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;}ll ans=0;int s[MN+5],n,p[MN+5],rt[MN+5],cnt=0;int f[MN+5][MK+3],f2[MN+5][MK+3];struct Tree{
   int l,r,x;}T[MN*35]; int query(int x,int nx,int v){    if(x>nx) return 0;x=rt[x-1];nx=rt[nx];    int l=1,r=INF,mid,ans=0;    while(l
        
         >1;        if(v<=mid)        {            nx=T[nx].l;x=T[x].l;            r=mid;        }        else        {            ans+=T[T[nx].l].x-T[T[x].l].x;            nx=T[nx].r;x=T[x].r;l=mid+1;        }    }    return ans+T[nx].x-T[x].x;}void ins(int x,int nx,int v){    int l=1,r=INF,mid;    while(l
         
          >1;        if(v<=mid)        {            T[nx].r=T[x].r;T[nx].l=++cnt;            x=T[x].l;nx=T[nx].l;r=mid;        }        else        {            T[nx].l=T[x].l;T[nx].r=++cnt;            x=T[x].r;nx=T[nx].r;l=mid+1;        }        T[nx].x=T[x].x+1;    }}int calc(int l,int r){    int len=p[r-l+1];    return max(f[l][len],f2[r][len]);}int get(int l,int r,int ans,int x){    int mid,rr=r;    while(l<=r)    {        mid=l+r>>1;        if(calc(mid,r)
          
           >1; if(calc(lt,mid)<=x) ans=mid,l=mid+1; else r=mid-1; } return ans;}int main(){ freopen("pair.in","r",stdin); freopen("pair.out","w",stdout); n=read(); for(int i=0;i<=MK;i++) for(int j=(1<
           
            <=min(n,1<<(i+1));j++) p[j]=i; for(int i=1;i<=n;i++)s[i]=f[i][0]=f2[i][0]=read(); for(int i=1;i<=n;i++)ins(rt[i-1],rt[i]=++cnt,s[i]); for(int i=1,k=1;i<=MK;i++,k<<=1) for(int j=1;j<=n;j++) f[j][i]=max(f[j][i-1],f[min(j+k,n)][i-1]), f2[j][i]=max(f2[j][i-1],f2[max(1,j-k)][i-1]); for(int i=1;i<=n;i++) { int l=get(1,i-1,i,f[i][0]),r=get2(i+1,n,i,f[i][0]); if(i-l
           
          
         
        
       
      
     

D.需要你构造一个有n个点，每个点都恰好有m条单向的出边的图，使得点两两之间的最大距离最小。n<=1000,m<=5  当答案与最小直径相差不超过1的时候判对。

题解：我们考虑一个倍增的思想。如果要表示1-7的数，我们会选择1 2 4。同理，我们对于每个点i，连接i和i*m+j  (j=0~m-1) ，这样在m^k>=n的时候就能保证任意一个点i在k步之内能走到任意一个点，直接算$m^{x}>=n$的x作为直径就好啦

#include
     
      #include
      
       #include
       
        #define MN 1000using namespace std;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;}int n,m;int main(){    freopen("diameter.in","r",stdin);    freopen("diameter.out","w",stdout);    n=read();m=read();    int ans=0;    for(int i=1;i