2014 UESTC Training for Data Structures B - 母仪天下

富庶的建业城中，有一条格格不入的长街，名曰跳蚤街，被战争所致的孤儿，聚集于此。全国的经济都在为战争服务之时，也无人顾得了这里了。

除了两位夫人。

大乔小乔每天都会带着一些食物来到跳蚤街，分给某一位孩子。为了避免分配不均，她们时常会询问一个区域内食物的总量，然后进行调整以保证每个孩子都有足够的食物。

Input

第一行两个整数n，m，表示跳蚤街住着n户孩子，大乔小乔一共分发或询问了m次。

第二行n个整数，第i个数ai表示第i户孩子已有ai的食物。

接下来m行，每行开始先读入一个整数si，指明这是一次询问还是一次分发。

si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问[li，ri]区间中的孩子们一共有多少食物。

si=1，表明这是一次分发，然后读入两个整数xi,wi，表示对第xi户孩子分发了wi的食物。

1≤n,m≤100000,0≤ai≤100000,1≤xi≤n,0≤wi≤10000,1≤li≤ri≤n

Output

有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。

Sample input and output

Sample InputSample Output

5 4 1 2 3 4 5 1 2 3 0 2 4 1 4 1 0 1 5	12 19

 

纯裸的线段树，没什么好说的。。关于线段树大家可以百度一下或者google一下，会有很多文章有介绍。

我这段程序是按jianshu（建树），suan（给线段树赋初值，即一开始的i孩子有ai食物），found（数的区间查找）|done（树的维护）的顺序写的。

 

#include <iostream> #include<stdio.h> #include<string.h> using namespace std; int q[100005],shu[400005][3]; void jianshu(int g,int h,int l) {shu[l][1]=g;shu[l][2]=h;if (g==h) {shu[l][0]=q[g];return;}jianshu(g,(g+h)/2,l*2);jianshu((g+h)/2+1,h,l*2+1); } int suan(int j) {if (shu[j][1]==shu[j][2]) return shu[j][0];return shu[j][0]=suan(j*2)+suan(j*2+1); } int found(int l,int g,int h) {if (g==shu[l][1] && h==shu[l][2]) return shu[l][0];int z=(shu[l][1]+shu[l][2])/2;if (g<=z && h>=z+1) return found(l*2,g,z)+found(l*2+1,z+1,h);if (h<=z) return found(l*2,g,h);else return found(l*2+1,g,h); } void done(int l,int g,int h) {shu[l][0]+=h;if (shu[l][1]==shu[l][2]) return;if (g<=(shu[l][1]+shu[l][2])/2) done(l*2,g,h);else done(l*2+1,g,h); } int main() {int n,m,j,l,g,h;cin>>n>>m;memset(q,123,sizeof(q));memset(shu,0,sizeof(shu));for (j=1;j<=n;j++) scanf("%d",&q[j]);jianshu(1,n,1);suan(1);for (j=1;j<=m;j++){scanf("%d%d%d",&l,&g,&h);if (l==0) printf("%d\n",found(1,g,h));if (l==1) done(1,g,h);}return 0; }

 

转载于:https://www.cnblogs.com/Atlantis67/p/3675430.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的2014 UESTC Training for Data Structures B - 母仪天下的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。