首页 > 代码库 > FZU2171:防守阵地 II(线段树)
FZU2171:防守阵地 II(线段树)
Problem Description
部队中总共有N个士兵,每个士兵有各自的能力指数Xi,在一次演练中,指挥部确定了M个需要防守的地点,指挥部将选择M个士兵依次进入指定地点进行防守任务,获得的参考指数即为M个士兵的能力之和。随着时间的推移,指挥部将下达Q个指令来替换M个进行防守的士兵们,每个参加完防守任务的士兵由于疲惫等原因能力指数将下降1。现在士兵们排成一排,请你计算出每次进行防守的士兵的参考指数。
Input
输入包含多组数据。
输入第一行有两个整数N,M,Q(1<=N<=100000,1<=M<=1000,1<=Q<=100000),第二行N个整数表示每个士兵对应的能力指数Xi(1<=Xi<=1000)。
接下来Q行,每行一个整数X,表示在原始队列中以X为起始的M个士兵替换之前的士兵进行防守。(1<=X<=N-M+1)
对于30%的数据1<=M,N,Q<=1000。
Output
输出Q行,每行一个整数,为每次指令执行之后进行防守的士兵参考指数。
Sample Input
5 3 3 2 1 3 1 4 1 2 3
Sample Output
6 3 5
这道题与杭电一道题几乎是一样的,详细可看我另外一个阶梯报告:
http://blog.csdn.net/libin56842/article/details/13614183
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int maxn = 100000+10;int n,m,sum;struct node{ int l,r; int n,sum;} a[maxn<<2];void init(int l,int r,int i){ a[i].l = l; a[i].r = r; a[i].n = 0; a[i].sum = 0; if(l!=r) { int mid = (l+r)>>1; init(l,mid,2*i); init(mid+1,r,2*i+1); }}void insert(int i,int l,int r,int m){ a[i].n+=(r-l+1)*m; if(a[i].l >= l && a[i].r <= r) a[i].sum+=m; else { int mid = (a[i].l+a[i].r)>>1; if(r<=mid) insert(2*i,l,r,m); else if(l>mid) insert(2*i+1,l,r,m); else { insert(2*i,l,mid,m); insert(2*i+1,mid+1,r,m); } }}int find(int i,int l,int r){ if(a[i].l == l && a[i].r == r) return a[i].n; else { int mid = (a[i].l+a[i].r)>>1; if(a[i].sum) { a[2*i].sum += a[i].sum; a[2*i].n+=a[i].sum*(a[2*i].r-a[2*i].l+1); a[2*i+1].sum += a[i].sum; a[2*i+1].n+=a[i].sum*(a[2*i+1].r-a[2*i+1].l+1); a[i].sum = 0; } if(r<=mid) return find(2*i,l,r); else if(l>mid) return find(2*i+1,l,r); else { return find(2*i,l,mid)+find(2*i+1,mid+1,r); } }}int main(){ int i,j,x,y,q; int k; char str[5]; while(~scanf("%d%d%d",&n,&m,&q)) { init(1,n,1); for(i = 1; i<=n; i++) { scanf("%d",&k); insert(1,i,i,k); } while(q--) { scanf("%d",&x); printf("%d\n", find(1,x,x+m-1)); insert(1,x,x+m-1,-1); } } return 0;}
FZU2171:防守阵地 II(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。