E - Min of Restricted Sum
构造a[1~n]
所以每一位独立，
对于每一位来说，就是边权为0或者1，点权0或者1，同一个连通块中只要确定一个，其余就确定
了，dfs也就两种，第一个点取0或1，取最小的加上即可
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define int long longconst int N=200010;
vector<pii> G[N];bool vis[N];
int a[N];
int b[N][40];
int cs,c;bool flag1=1;vector<int> vec;
void dfs(int u,int _){//cout<<"dfs"<<u<<" "<<fa<<" "<<a[u]<<'\n';cs++;if(a[u])c++;vec.pb(u);vis[u]=1;for(auto [v,w]:G[u]){int t=(w&(1ll<<_))?1:0;if(!vis[v]){a[v]=a[u]^t;dfs(v,_);}else {if(a[v]!=a[u]^t){//cout<<u<<" "<<v<<" "<<_<<" "<<a[u]<<" "<<a[v]<<" "<<'\n';flag1=0;}}}
}
void solve(){
int n,m;cin>>n>>m;
while(m--){int u,v,w;cin>>u>>v>>w;G[u].pb({v,w});G[v].pb({u,w});
}int ans=0;
for(int _=0;_<=32;_++){for(int i=1;i<=n;i++)vis[i]=0;for(int i=1;i<=n;i++){if(!vis[i]){flag1=1;int tmp=INF;vec.clear();a[i]=0;cs=0;c=0;dfs(i,_);if(!flag1){cout<<-1<<'\n';return ;}if(tmp>c){tmp=c;for(auto j:vec)b[j][_]=a[j];}if(tmp>cs-c){tmp=cs-c;for(auto j:vec)b[j][_]=a[j]^1;}ans+=tmp*(1ll<<_);}}
}
//cout<<ans<<'\n';
for(int i=1;i<=n;i++){int bb=0;for(int j=0;j<=32;j++){if(b[i][j])bb+=(1ll<<j);}cout<<bb<<" ";
}
}
signed main(){std::ios::sync_with_stdio(false);int T;T=1;while(T--){solve();}
}
F - Rotated Inversions
cf题，只有正好变成0的贡献发生改变，+前面比他小的-后面比他小的
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
const int N=200010;
int a[N],b[N],c[N];vector<int> G[N];
int n,m;
int lowbit(int x){return x&(-x);}
int tr[N];
void add(int x,int k){for(int i=x;i<=m;i+=lowbit(i)){tr[i]+=k;}
}
int get(int x){int s=0;for(int i=x;i>0;i-=lowbit(i))s+=tr[i];return s;
}void solve(){
cin>>n>>m;
int ans=0;
for(int i=1;i<=n;i++){cin>>a[i];a[i]++;ans+=i-1-get(a[i]);G[a[i]].pb(i);add(a[i],1);
}for(int i=m;i>=1;i--){cout<<ans<<'\n';for(int j=0;j<G[i].size();j++){int p=G[i][j];ans+=p-1-(j-1+1);ans-=n-p-(G[i].size()-1-j-1+1);}
}}
signed main(){std::ios::sync_with_stdio(false);int T;T=1;while(T--){solve();}
}