1 严格次小生成树
题目大意
对于无向图(G)，我们记最小生成树的边集为(E_m)，次小生成树的边集为(E_p)，用( ext{value}(x))表示(x)的边权，则严格次小生成树满足(sumlimits_{xin E_m} ext{value}(x)<sumlimits_{xin E_p} ext{value}(x))，请你求出其边权。
题解
对于最小生成树，删去一条边后形成两个联通块，任意连接两个联通块的边，最小的边即为次小生成树。严格的意思是，连接的这个边严格大于删掉的边，如果等于了，也叫次小生成树。
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define int long long
#define M 300003
using namespace std;
inline int read(){
int f=1,x=0;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+(c^48);c=getchar();}
return x*f;
}
struct node1{
int x,y,z,flag;
}w[M];
struct node2{
int to,next,val;
}edge[M];
#define INF 2100000001
#define N 100003
int cnt,m,n,minn=INF,ans=0;
int f[N][22],max1[N][22],g[N][22],fa[N],head[N],dep[N];
bool cmp(node1 a,node1 b){
return a.z<b.z;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void add(int x,int y,int v){
cnt++;
edge[cnt].val=v;
edge[cnt].to=y;
edge[cnt].next=head[x];
head[x]=cnt;
}
void krs(){
int q=1;
sort(w+1,w+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int s1=find(w[i].x);
int s2=find(w[i].y);
if(s1!=s2){
ans+=w[i].z;w[i].flag=1;
q++;
fa[s1]=s2;
add(w[i].x,w[i].y,w[i].z);
add(w[i].y,w[i].x,w[i].z);
}
if(q==n) break;
}
}
void dfs(int x){
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(v==f[x][0]) continue;
f[v][0]=x;
max1[v][0]=edge[i].val;
dep[v]=dep[x]+1;
for(int j=1;j<=20;j++){
if(dep[v]<(1<<j)) break;
f[v][j]=f[f[v][j-1]][j-1];
max1[v][j]=max(max1[v][j-1],max1[f[v][j-1]][j-1]);
if(max1[v][j-1]==max1[f[v][j-1]][j-1])
g[v][j]=max(g[v][j-1],g[f[v][j-1]][j-1]);//g是次小边
else{
g[v][j]=min(max1[v][j-1],max1[f[v][j-1]][j-1]);
g[v][j]=max(g[v][j],g[f[v][j-1]][j-1]);
g[v][j]=max(g[v][j-1],g[v][j]);
}
}
dfs(v);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=20;i>=0;i--) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
if(v==u) return v;
for(int i=20;i>=0;i--) if(f[v][i]!=f[u][i]) v=f[v][i],u=f[u][i];
return f[v][0];
}
void change(int x,int lca,int val){
int maxx1=0,maxx2=0;
int d=dep[x]-dep[lca];
for(int i=0;i<=20;i++){
if(d<(1<<i)) break;
if(d&(1<<i)){
if(max1[x][i]>maxx1){
maxx2=max(maxx1,g[x][i]);
maxx1=max1[x][i];
}
x=f[x][i];
}
}
if(val!=maxx1) minn=min(minn,val-maxx1);
else minn=min(minn,val-maxx2);
}
void work(){
for(int i=1;i<=m;i++){
if(!w[i].flag){
int s1=w[i].x,s2=w[i].y;
int lcp=lca(s1,s2);
change(s1,lcp,w[i].z);change(s2,lcp,w[i].z);
}
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&w[i].x,&w[i].y,&w[i].z);
}
krs();
dfs(1);
work();
printf("%lld
",ans+minn);
return 0;
}
2 逆序对[树状数组维护]
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxx=1000005;
ll a[maxx],b[maxx],s[maxx];
ll n;
void init()
{
sort(b+1,b+1+n);
unique(b+1,b+1+n);//-b-1;
for(ll i=1;i<=n;i++)
{
a[i]=lower_bound(b+1,b+n+1,a[i])-b;
}
return;
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
}
ll ans=0;
init();
for(ll i=n;i>=1;i--)
{
for(ll j=a[i];j<=n;j+=(j&-j))
{
s[j]++;
}
for(ll j=a[i]-1;j>=1;j-=(j&-j))
{
ans+=s[j];
}
}
printf("%lld",ans);
return 0;
}