Potentiometers （树状数组）

Potentiometers （树状数组）

A potentiometer, or potmeter for short, is an electronic device with a variable electric resistance. Ithas two terminals and some kind of control mechanism (often a dial, a wheel or a slide) with which theresistance between the terminals can be adjusted from zero (no resistance) to some maximum value.Resistance is measured in Ohms, and when two or more resistors are connected in series (one after theother, in a row), the total resistance of the array is the sum of the resistances of the individual resistors.In this problem we will consider an array of N potmeters, numbered 1 to N from left to right. Theleft terminal of some potmeter numbered x is connected to the right terminal of potmeter x − 1, andits right terminal to the left terminal of potmeter x + 1. The left terminal of potmeter 1 and the rightterminal of potmeter N are not connected.Initially all the potmeters are set to some value between 0 and 1000 Ohms. Then we can do twothings:• Set one of the potmeters to another value.• Measure the resistance between two terminals anywhere in the array.InputThe input consists less than 3 cases. Each case starts with N, the number of potmeters in the array,on a line by itself. N can be as large as 200000. Each of next N lines contains one numbers between 0and 1000, the initial resistances of the potmeters in the order 1 to N. Then follow a number of actions,each on a line by itself. The number of actions can be as many as 200000. There are three types ofaction:• “S x r” - set potmeter x to r Ohms. x is a valid potmeter number and r is between 0 and 1000.• “M x y” - measure the resistance between the left terminal of potmeter x and the right terminalof potmeter y. Both numbers will be valid and x is smaller than or equal to y.• “END” - end of this case. Appears only once at the end of a list of actions.A case with N = 0 signals the end of the input and it should not be processed.OutputFor each case in the input produce a line ‘Case n:’, where n is the case number, starting from 1.For each measurement in the input, output a line containing one number: the measured resistancein Ohms. The actions should be applied to the array of potmeters in the order given in the input.Print a blank line between cases.Warning: Input Data is pretty big (∼ 8 MB) so use faster IO.Sample Input3100100100M 1 1M 1 3S 2 200M 1 2S 3 0M 2 3END1012345678910M 1 10END0Sample OutputCase 1:100300300200Case 2:55

题目大概：

给你n个数，不定条询问，询问可以单点更新，也可以区间求和。

思路：

树状数组，单点更新，区间求和的模板题。

代码：

#include using namespace std;const int maxn=2e5+10;int c[maxn];int N;int lowbit(int x){ return x&(-x);}void add(int x,int v){ while(x<=N) { c[x]+=v; x+=lowbit(x); }}int sum(int x){ int sum=0; while(x>0) { sum+=c[x]; x-=lowbit(x); } return sum;}int main(){ int ans=0; while(~scanf("%d",&N)&&N) { memset(c,0,sizeof(c)); int u; for(int i=1;i<=N;i++) { scanf("%d",&u); add(i,u); } char q[5]; if(ans)printf("\n"); printf("Case %d:\n",++ans); while(scanf("%s",q)) { if(q[0]=='E')break; if(q[0]=='S') { int id,w2; scanf("%d%d",&id,&w2); int w=sum(id)-sum(id-1); int cha=w2-w; add(id,cha); } else { int l,r; scanf("%d%d",&l,&r); int w=sum(r)-sum(l-1); printf("%d\n",w); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。