如果没有k个城市可以独立供电，我们就直接找到x和y的中位数，然后计算距离和就可以了，现在要去掉k个城市，很明显，中位数位置的偏移不超过k/2+1,这样，我们分别枚举x和y在[n/2-k/2-1,n/2+k/2+1]的位置就可以找到最优情况了.
UESTC 1650
#include<cstdio> #include<queue> #include<iostream> #include<algorithm> using namespace std; int tx[1010],ty[1010],change[1010],n,k; struct node { int c,x,y; }va[1010]; int cal(int posx,int posy) { priority_queue<int,vector<int>,greater<int> >q; int ans=0; for(int i=0;i<n;i++) { int temp=abs(va[i].x-tx[posx])+abs(va[i].y-ty[posy]); ans+=temp; q.push(va[i].c-temp); } for(int i=0;i<k;i++) { ans+=q.top(); q.pop(); } return ans; } int main() { int T,i,j,cases=0; scanf("%d",&T); while(T--) { cases++; scanf("%d%d",&n,&k); for(i=0;i<n;i++) scanf("%d",&va[i].c); for(i=0;i<n;i++){ scanf("%d%d",&va[i].x,&va[i].y); tx[i]=va[i].x; ty[i]=va[i].y; } sort(tx,tx+n); sort(ty,ty+n); int st=max(n/2-k/2-1,0); int end=min(n/2+k/2+1,n-1); int ans=2000000000; for(i=st;i<=end;i++) { for(j=st;j<=end;j++) { ans=min(ans,cal(i,j)); } } printf("Case #%d: %d\n",cases,ans); } return 0; }
把树转化成1维，然后线段树，转化的方法可以先写ZOJ3686，和ZOJ3686不同的是，更新的值根据层数是递增的，所以直接区间更新明显是不行的，观察发现，树的层数可以保证下面一层是上面一层+1，那么给定一个根节点a,假设操作为A a k，a为根结点的子树的所有节点深度和为S，更新实际增加值为X，那么满足S-(dep[a]-k)*num=X,其中dep[a]表示a的深度，num表示以a为根的子树的节点个数，可以理解为每个节点多加了(dep[a]-k)，这样，我们只需记录每个区间被增加过多少次和多增加的值，就可以区间更新+延迟标记搞了。
UESTC 1653
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; #define maxn 50010 #define lson l,m,root<<1 #define rson m+1,r,root<<1|1 #define INF 0x3f3f3f3f3f3f3f3fll vector<int>road[maxn]; bool mark[maxn]; int l[maxn],r[maxn],dep[maxn],num,addcnt[maxn<<2];//sum 多加的权值 cnt加过的次数 long long depsum[maxn],sum[maxn<<2],addsum[maxn<<2]; void pushup(int root){ sum[root]=sum[root<<1]+sum[root<<1|1]; } void dfs(int pos,int deep){ l[pos]=num++; dep[l[pos]]=deep; int size=road[pos].size(); for(int i=0;i<size;i++) if(!mark[road[pos][i]]){ mark[road[pos][i]]=1; dfs(road[pos][i],deep+1); } r[pos]=num-1; } void pushdown(int root,int l,int r){ int mid=(l+r)>>1; int ls=(root<<1); int rs=(root<<1|1); if(addsum[root]!=INF){ if(addsum[ls]==INF) addsum[ls]=0; if(addsum[rs]==INF) addsum[rs]=0; addsum[ls]+=addsum[root]; addsum[rs]+=addsum[root]; addcnt[ls]+=addcnt[root]; addcnt[rs]+=addcnt[root]; sum[ls]+=addcnt[root]*(depsum[mid]-depsum[l-1])-addsum[root]*(mid-l+1); sum[rs]+=addcnt[root]*(depsum[r]-depsum[mid])-addsum[root]*(r-mid); addcnt[root]=0; addsum[root]=INF; } } void update(int l,int r,int root,int s,int e,int add){ if(s<=l&&e>=r){ sum[root]+=depsum[r]-depsum[l-1]-add*(r-l+1); if(addsum[root]==INF) addsum[root]=0; addsum[root]+=add; addcnt[root]++; return; } int m=(l+r)>>1; pushdown(root,l,r); if(m>=s) update(lson,s,e,add); if(m<e) update(rson,s,e,add); pushup(root); } long long query(int l,int r,int root,int s,int e){ if(s<=l&&e>=r) return sum[root]; double ret=0; int m=(l+r)>>1; pushdown(root,l,r); if(m>=s) ret+=query(lson,s,e); if(m<e) ret+=query(rson,s,e); pushup(root); return ret; } int main(){ int T,temp,i,n,p,a,b,cases=0; char ch[20]; scanf("%d",&T); while(T--){ cases++; scanf("%d%d",&n,&p); memset(mark,0,sizeof(mark)); memset(sum,0,sizeof(sum)); memset(addsum,0x3f,sizeof(addsum)); memset(addcnt,0,sizeof(addcnt)); for(i=0;i<=n;i++) road[i].clear(); for(i=2;i<=n;i++){ scanf("%d",&temp); road[i].push_back(temp); road[temp].push_back(i); } num=1; mark[1]=1; dfs(1,1); depsum[0]=0; for(i=1;i<=n;i++) depsum[i]=depsum[i-1]+dep[i]; printf("Case #%d:\n",cases); while(p--){ scanf("%s",ch); if(ch[0]=='A'){ scanf("%d%d",&a,&b); update(1,n,1,l[a],r[a],dep[l[a]]-b); } else{ scanf("%d",&a); printf("%lld\n",query(1,n,1,l[a],r[a])); } } } return 0; }