先学会这个哈夫曼距离的处理才能做 cf 的G
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define maxn 100005
const int inf = (int)1e9;
];
<<+],mx[<<+];
int main(){
int n;
scanf("%d",&n);
;j<n;j++){
;k<;k++){
scanf("%lf",&a[j][k]);
}
}
;j<(<<);j++){
mi[j] = inf;
mx[j] = -inf;
}
// double mx = 0,mi = inf;
double ans = -inf;
;j<n;j++){
//int cur = 0.
;k<(<<);k++){
;
;i<;i++){
<<i)){
cur += a[j][i];
}else{
cur -= a[j][i];
}
}
//cout<<cur<<endl;
mx[k] = max(mx[k],cur);
mi[k] = min(mi[k],cur);
//ans = max(ans,mx[j]-mi[j]);
}
}
;j<(<<);j++){
//cout<<mx[j]<<" "<<mi[j]<<endl;
ans = max(ans,mx[j]-mi[j]);
}
printf("%0.2f\n",ans);
}点一下 题目链接
CF G 用线段树处理一下
就ok
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define inf (int)1e9
*maxn][];
*maxn][];
int n,m;
void build(int l,int r,int in){
if(l==r){
;j<(<<m);j++){
;
;k<m;k++){
<<k)){
cur+=b[l][k];
}else cur-=b[l][k];
}
//cout<<cur<<endl;
a[in][j] = cur;
}
return ;
}
;
build(l,mid,);
build(mid+,r,+);
;j<(<<m);j++){
a[][j],a[+][j]);
}
}
void up(int l,int r,int x,int in){
if(l==r){
;j<(<<m);j++){
;
;k<m;k++){
<<k)){
cur+=b[l][k];
}else cur-=b[l][k];
}
a[in][j] = cur;
}
return ;
}
;
if(x>mid){
up(mid+,r,x,+);
}else{
up(l,mid,x,);
}
;j<(<<m);j++){
a[][j],a[+][j]);
}
}
int query(int l,int r,int x,int y,int i,int in){
//if(x>y) return inf;
if(l==x&&r==y){
return a[in][i];
}
;
if(x>mid){
,r,x,y,i,+);
}else if(y<=mid){
);
}
),query(mid+,r,mid+,y,i,+));
}
int main(){
cin>>n>>m;
;j<=n;j++){
;k<m;k++){
scanf("%d",&b[j][k]);
}
}
build(,n,);
// for(int j=0;j<(1<<m);j++){
// cout<<a[1][j]<<endl;
// }
int t; cin>>t;
while(t--){
int z;
scanf("%d",&z);
){
int i;
scanf("%d",&i);
;j<m;j++){
scanf("%d",&b[i][j]);
}
up(,n,i,);
}else{
;
scanf("%d%d",&l,&r);
;j<(<<(m-));j++){
,n,l,r,j,);
,n,l,r,j^((<<m)-),);
//cout<<x<<" "<<y<<endl;
mx = max(mx,abs(x+y));
}
printf("%d\n",mx);
}
}
;
}