其实也是近一个月之前的一场cf了，div3真是吼啊。今天忽然想起来补完剩下的题。

前五道暴力模拟什么的略过不写了。

E2 Array and Segments (Hard version)

题意：给出大小为n的数组a，m个区间。你可以决定每个区间是否进行操作（对区间内的数全部减1），给出任一方案使得数组最大值与最小值的差最大。n<=1e5,m<=300

E2和E1的区别只有数据范围，E1可以暴力枚举选择每个数作为最小值的情况（将包含最小值的区间全部进行操作），每次更新答案，O(n²m)。

E2可以在此基础上进行改进。线段树进行区间操作查询最大值的优化比较好想。然后发现这个m很小…从m入手发现可以用所有区间的端点可以将数组分成不超过601段，在每一段内的i我们按照如上原则选择的操作是相同的，由此可以批量处理降低时间复杂度。

（然而代码写的就非常不优雅，我自己看完都想说这是什么辣鸡…甚至一年半没写线段树了吧。有机会可能会看看官方里的方法重写。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define Max(a,b) (a>b?a:b)#define N 100005#define INF 0x3f3f3f3fusing namespace std;int read(){ int x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n,m,a[N],l[303],r[303];int seg[606],ans=0;vector
           
            A,cp;struct Node{ int l,r,maxn,lazy;}t[N*4];void build(int idx,int l,int r){ t[idx].l=l,t[idx].r=r; if(l==r){t[idx].maxn=a[l],t[idx].lazy=0;return;} int mid=(l+r)>>1; build(idx<<1,l,mid),build(idx<<1|1,mid+1,r); t[idx].maxn=Max(t[idx<<1].maxn,t[idx<<1|1].maxn);}void pushdown(int idx){ if(t[idx].lazy&&t[idx].l!=t[idx].r) { int lz=t[idx].lazy; t[idx].lazy=0; t[idx<<1].lazy+=lz,t[idx<<1|1].lazy+=lz; t[idx<<1].maxn+=lz,t[idx<<1|1].maxn+=lz; }}void add(int idx,int l,int r,int w){ if(l<=t[idx].l&&r>=t[idx].r) { t[idx].maxn+=w,t[idx].lazy+=w; return; } pushdown(idx); int mid=(t[idx].l+t[idx].r)>>1; if(r<=mid)add(idx<<1,l,r,w); else if(l>mid)add(idx<<1|1,l,r,w); else add(idx<<1,l,r,w),add(idx<<1|1,l,r,w); t[idx].maxn=Max(t[idx<<1].maxn,t[idx<<1|1].maxn);}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i]=read(); build(1,1,n); for(int i=1;i<=m;i++) { l[i]=read(),r[i]=read(); seg[i*2-1]=l[i],seg[i*2]=r[i]; } sort(seg+1,seg+2*m+1),seg[0]=0; int cnt=unique(seg+1,seg+2*m+1)-seg-1; seg[cnt+1]=INF; int now=0,f; for(int i=1;i<=n;i++) { if(i==seg[now]||(i>seg[now]&&i==seg[now+1])) { f=0,cp.clear(); if(i==seg[now+1])now++; for(int j=1;j<=m;j++) { if(l[j]<=i&&r[j]>=i) f++,add(1,l[j],r[j],-1),cp.push_back(j); } } else if(i>seg[now]) { now++,f=0,cp.clear(); for(int j=1;j<=m;j++) { if(l[j]<=seg[now-1]+1&&r[j]>=seg[now]-1) f++,add(1,l[j],r[j],-1),cp.push_back(j); } } int minnum=a[i]-f; if(t[1].maxn-minnum>ans) { ans=t[1].maxn-minnum; A=cp; } if(i==seg[now]-1||i==seg[now]) { for(int j=0;j
           
          
         
        
       
      
     

F. MST Unification

题意：给出一个带权无向图，你可以增加任意边的边权使得最小生成树唯一。求所增加的边权总和的最小值。

先用kruskal跑出一个MST，在这个MST上倍增LCA。对于每一条未被加入当前MST的边进行判断，如果其边权与u,v间路径上的最大边权相等，则这条边可以起替代作用（砍掉最大边用这条联通），需要给权值+1。

（选这个LCA做法是因为它在 只占了三行…写完读了Second Solution发现题解长度和代码长度并不成正比…怎么我选的总是一些莽夫做法）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define Max(a,b) (a>b?a:b)#define N 200005using namespace std;int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n,m,head[N],cnt=0,father1[N],dep[N],p[N][20],mlen[N][20];bool used[N];struct Node1{ int u,v,w;}Edges1[N];bool operator < (Node1 A,Node1 B){ return A.w
            
             dep[y])swap(x,y); int f=dep[y]-dep[x]; for(int i=0;(1<
             
              <=f;i++) if(f&(1<
              
               =0;i--) if(p[x][i]!=p[y][i])res=Max(res,mlen[x][i]),res=Max(res,mlen[y][i]),x=p[x][i],y=p[y][i]; res=Max(res,mlen[x][0]),res=Max(res,mlen[y][0]),x=p[x][0]; } return res;}int main(){ memset(head,-1,sizeof(head)); memset(dep,0,sizeof(dep)); memset(used,0,sizeof(used)); n=read(),m=read(); for(int i=1;i<=m;i++) Edges1[i].u=read(),Edges1[i].v=read(),Edges1[i].w=read(); sort(Edges1+1,Edges1+1+m); for(int i=1;i<=n;i++)father1[i]=i; int cnt=0; for(int i=1;i<=m;i++) { int fu=findf(Edges1[i].u),fv=findf(Edges1[i].v); if(fu!=fv) { cnt++; addedge(Edges1[i].u,Edges1[i].v,Edges1[i].w); addedge(Edges1[i].v,Edges1[i].u,Edges1[i].w); used[i]=1;father1[fu]=fv; } if(cnt==n-1)break; } dep[1]=mlen[1][0]=0;p[1][0]=1; dfs(1),init(); int ans=0; for(int i=1;i<=m;i++) { if(used[i])continue; int u=Edges1[i].u,v=Edges1[i].v; int maxlen=lca(u,v); if(maxlen==Edges1[i].w)ans++; } printf("%d\n",ans); return 0;}
              
             
            
           
          
         
        
       
      

这是那个Second Solution…只需要在Kruskal时把权值相同的边批量处理。

权值相同的边如果在最开始也加不进去就永远不可能在MST中出现，可以加进去的边有able条，并查集合并实际能用到的边uni条，则其余able-uni条边都需要权值++使MST唯一。

（如果一条有可能加入MST的边由于其他边被先考虑而没加进去，那这条边端点u,v间路径上的最大边权与它的权值相同，即可以拆掉另一条换这条。）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define Max(a,b) (a>b?a:b)#define N 200005using namespace std;int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n,m,head[N],cnt=0,father1[N],ans=0;struct Node1{ int u,v,w;}Edges1[N];bool operator < (Node1 A,Node1 B){ return A.w