C-sequence

题意：

题目给出长度为n的两个数组a,b，求出

分析：

标准题解：

代码：

 （线段树+单调栈）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int MAX=3e6+9;const int INF=0x3f3f3f3f;typedef long long ll;#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1int n;int l[MAX],r[MAX],a[MAX],b[MAX];ll sum[MAX];stack
            
             st;struct tree{ //线段树维护前缀和最大最小值 ll mx,mn;}tree[MAX<<2];void PushUp(int rt){ tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx); tree[rt].mn=min(tree[rt<<1].mn,tree[rt<<1|1].mn);}void Build(int l,int r,int rt){ if(l==r) { tree[rt].mx=sum[l]; tree[rt].mn=sum[l]; return; } int m=l+r>>1; Build(ls);Build(rs); PushUp(rt);}ll Query_min(int L,int R,int l,int r,int rt){ ll ans=INF; if(L<=l&&r<=R) return tree[rt].mn; int m=l+r>>1; if(L<=m)ans=min(ans,Query_min(L,R,ls)); if(R>m)ans=min(ans,Query_min(L,R,rs)); return ans; }ll Query_max(int L,int R,int l,int r,int rt){ ll ans=-INF; if(L<=l&&r<=R) return tree[rt].mx; int m=l+r>>1; if(L<=m)ans=max(ans,Query_max(L,R,ls)); if(R>m)ans=max(ans,Query_max(L,R,rs)); return ans;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)scanf("%d",&b[i]); for(int i=1;i<=n;i++)sum[i]=b[i]+sum[i-1]; Build(1,n,1); a[0]=a[n+1]=-INF; for(int i=0;i<=n+1;i++) { while(!st.empty()&&a[st.top()]>a[i]) //单调栈维护以每个a[i]为最小值的区间左右端点 { r[st.top()]=i-1; st.pop(); } if(!st.empty())l[i]=st.top()+1; st.push(i); }// for(int i=1;i<=n;i++)cout<
             
              <<' '<
              
               <
               
                =0) { ll h=(ll)a[i]*(sum[r[i]]-sum[l[i]-1]); if(h>ans) ans=h; } else { //a[i]为负数 取区间和最小 ll mx=Query_max(l[i],i,1,n,1); ll mn=Query_min(i,r[i],1,n,1); ll h=(ll)a[i]*(mn-mx); if(h>ans)ans=h; } } printf("%lld\n",ans); return 0;}
               
              
             
            
           
          
         
        
       
      

 

A-meeting

题意：

有一座城市，里面有n个有趣的地方分别标号为1~n，现在在地方x1，x2...，xk有一个人，他们想

找个地方会面，问最少需要花费多少时间。

分析：

标准题解简单易懂，tql

错误：弱智的我没有相通，觉得求出所有点之间的lca，d然后取该点到lca最大的就可以。但是只需要

简单想想就可以找到反例，比如有1->2 2->3 3->4  1->5  这样找到的lca是1，那么1和5汇聚的最短距离就是

3 但其实在点3汇聚最短花费就是2了

代码:

（找出x1~xk中离所有点的lca最远的点，然后找出该点到其他点最大距离，取一半向上取整）

#include
      
       #include
       
        #include
        
         using namespace std;const int MAX=1e5+9;struct Edge{    int to,val,next;}edge[MAX*2];int head[MAX],cnt=0;int deep[MAX],dis[MAX];int up[MAX][20];int n,k,a,b,x[MAX];inline void add(int u,int v,int w){    edge[cnt].val=w;    edge[cnt].to=v;    edge[cnt].next=head[u];    head[u]=cnt++;}void dfs(int u){    for(int i=head[u];i!=-1;i=edge[i].next)    {        int to=edge[i].to;        if(up[u][0]==to)continue;        deep[to]=deep[u]+1;        dis[to]=dis[u]+edge[i].val;        up[to][0]=u;        dfs(to);    }}void init(){    for(int j=1;(1<
         
          <=n;j++)        for(int i=1;i<=n;i++)            up[i][j]=up[up[i][j-1]][j-1];}int LCA(int a,int b){    if(deep[a]
          
           =0;i--)    {        if(up[a][i]!=up[b][i])            a=up[a][i],b=up[b][i];    }    return up[a][0];        }int get_dis(int a,int b,int lca){    return dis[a]+dis[b]-dis[lca]*2;}int main(){    memset(head,-1,sizeof(head));    scanf("%d%d",&n,&k);    for(int i=1;i
          
         
        
       
      

 （两次dfs求出树的直径，在x1~xk中随意取一点dfs找出离该点最远的点，在用该点dfs，找到直接的另一个

点，直接取一半向上取整）

#include
      
       #include
       
        #include
        
          using namespace std;const int MAX=1e5+9;int n,k,a,b,x[MAX];int head[MAX],cnt=0;int ans,pos;bool vis[MAX];struct Edge{    int to,val,next;}edge[MAX*2];inline void add(int u,int v,int w){    edge[cnt].to=v;    edge[cnt].val=w;    edge[cnt].next=head[u];    head[u]=cnt++;}void dfs(int u,int fa,int dist){    if(ans