藍(lán)橋杯練習(xí)題庫 3算法訓(xùn)練題

1、算法訓(xùn)練 圖形顯示  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個(gè)程序，首先輸入一個(gè)整數(shù)，例如5，然后在屏幕上顯示如下的圖形（5表示行數(shù)）：* * * * * * * * * * *#include<stdio.h>int main()int i,j,a100100,n; while(scanf("%d",&n)!=EOF) for(i=0;i<n;i+) for(j=0;j<n-i;j+) printf("*"

2、;); if(j!=n-i-1) printf(" "); if(j=n-1-i) printf("n");   算法訓(xùn)練 排序  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個(gè)程序，輸入3個(gè)整數(shù)，然后程序?qū)?duì)這三個(gè)整數(shù)按照從大到小進(jìn)行排列。輸入格式：輸入只有一行，即三個(gè)整數(shù)，中間用空格隔開。輸出格式：輸出只有一行，即排序后的結(jié)果。輸入輸出樣例樣例輸入9 2 30樣例輸出30 9 2#include<stdio.h>#in

3、clude<stdlib.h>#define num 100int main(void)int i,j,t,a3=0;for (i=0;i<3;i+)scanf("%d",&ai);for (i=0;i<3;i+)for (j=i;j<3;j+)if (ai<=aj)t=ai;ai=aj;aj=t;for (i=0;i<3;i+)printf("%d",ai);if(i!=2) printf(" ");printf("n");return 0;  算法訓(xùn)練

4、 2的次冪表示  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述任何一個(gè)正整數(shù)都可以用2進(jìn)制表示，例如：137的2進(jìn)制表示為10001001。將這種2進(jìn)制表示寫成2的次冪的和的形式，令次冪高的排在前面，可得到如下表達(dá)式：137=27+23+20現(xiàn)在約定冪次用括號(hào)來表示，即ab表示為a（b）此時(shí)，137可表示為：2（7）+2（3）+2（0）進(jìn)一步：7=22+2+20 （21用2表示）3=2+20 所以最后137可表示為：2（2（2）+2+2（0）+2（2+2（0）+2（0）又如：1315=21

5、0+28+25+2+1所以1315最后可表示為：2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0）輸入格式正整數(shù)（1<=n<=20000）輸出格式符合約定的n的0，2表示（在表示中不能有空格）樣例輸入137樣例輸出2(2(2)+2+2(0)+2(2+2(0)+2(0)樣例輸入1315樣例輸出2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2(0)+2+2(0)提示用遞歸實(shí)現(xiàn)會(huì)比較簡(jiǎn)單，可以一邊遞歸一邊輸出#include <stdio.h>int l=0;char temp1000=0;void show(int n)

6、 if(n=0) templ='0'l+;return ; if(n=2) templ='2',l+;return ; int a15=0,i=0,j; while(n!=0) ai=n%2; n/=2; i+; for(j=i-1;j>=0;j-) if(aj=1) if(j=1) if(templ-1=')' | templ-1='2' ) templ='+'l+;templ='2'l+; else if(templ-1=')' | templ-1='2'

7、) templ='+'l+;templ='2'l+;templ='('l+; show(j); templ=')'l+; int main()int n;scanf("%d",&n);show(n);printf("%s",temp); return 0;算法訓(xùn)練 前綴表達(dá)式  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個(gè)程序，以字符串方式輸入一個(gè)前綴表達(dá)式，然后計(jì)算它的

8、值。輸入格式為：“運(yùn)算符 對(duì)象1 對(duì)象2”，其中，運(yùn)算符為“+”（加法）、“-”（減法）、“*”（乘法）或“/”（除法），運(yùn)算對(duì)象為不超過10的整數(shù)，它們之間用一個(gè)空格隔開。要求：對(duì)于加、減、乘、除這四種運(yùn)算，分別設(shè)計(jì)相應(yīng)的函數(shù)來實(shí)現(xiàn)。輸入格式：輸入只有一行，即一個(gè)前綴表達(dá)式字符串。輸出格式：輸出相應(yīng)的計(jì)算結(jié)果（如果是除法，直接采用c語言的“/”運(yùn)算符，結(jié)果為整數(shù)）。輸入輸出樣例樣例輸入+ 5 2樣例輸出7#include<stdio.h>int main() int a2; int i,j; char c=getchar(); for(i=0;i<2;i+) scanf(&

9、quot;%d",&ai); if(c='+') j=a0+a1; else if(c='-') j=a0-a1; else if(c='*') j=a0*a1; else if(c='/') j=a0/a1; printf("%d",j); return 0;算法訓(xùn)練 Anagrams問題  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述Anagrams指的是具有如下特性的兩個(gè)單詞：在這兩

10、個(gè)單詞當(dāng)中，每一個(gè)英文字母（不區(qū)分大小寫）所出現(xiàn)的次數(shù)都是相同的。例如，“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。編寫一個(gè)程序，輸入兩個(gè)單詞，然后判斷一下，這兩個(gè)單詞是否是Anagrams。每一個(gè)單詞的長(zhǎng)度不會(huì)超過80個(gè)字符，而且是大小寫無關(guān)的。輸入格式：輸入有兩行，分別為兩個(gè)單詞。輸出格式：輸出只有一個(gè)字母Y或N，分別表示Yes和No。輸入輸出樣例樣例輸入U(xiǎn)nclearNuclear樣例輸出Y#include <stdio.h>void sort(char a,int len)int i,j,max;for(i=0;i<le

11、n;i+)max=i;for(j=i+1;j<len;j+)if(aj>amax) max=j;j=ai;ai=amax;amax=j;void strtoupper(char a,int len)int i;for(i=0;i<len;i+)if(ai>='a' && ai<='z') ai-=32;int mystrcmp(char a,int l1,char b,int l2)if(l1!=l2) return 0;int i;for(i=0;i<l1;i+)if(ai!=bi) return 0;ret

12、urn 1;int mystrlen(char *p)int l=0;while(*p+!=0)l+;return l;int main()char s11000=0,s21000=0;int l1,l2;scanf("%s%s",s1,s2);l1=mystrlen(s1);l2=mystrlen(s2);strtoupper(s1,l1);strtoupper(s2,l2);sort(s1,l1);sort(s2,l2); if(mystrcmp(s1,l1,s2,l2) printf("Y"); else printf("N")

13、;return 0;算法訓(xùn)練 出現(xiàn)次數(shù)最多的整數(shù)  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個(gè)程序，讀入一組整數(shù)，這組整數(shù)是按照從小到大的順序排列的，它們的個(gè)數(shù)N也是由用戶輸入的，最多不會(huì)超過20。然后程序?qū)?duì)這個(gè)數(shù)組進(jìn)行統(tǒng)計(jì)，把出現(xiàn)次數(shù)最多的那個(gè)數(shù)組元素值打印出來。如果有兩個(gè)元素值出現(xiàn)的次數(shù)相同，即并列第一，那么只打印比較小的那個(gè)值。輸入格式：第一行是一個(gè)整數(shù)N，N £ 20；接下來有N行，每一行表示一個(gè)整數(shù)，并且按照從小到大的順序排列。輸出格式：輸出只有一行，即出現(xiàn)

14、次數(shù)最多的那個(gè)元素值。輸入輸出樣例樣例輸入5100150150200250樣例輸出150#include <stdio.h>int main()int n,i,j,t,max=1,num=0;scanf("%d",&n);if(n>0)int an;for(i=0;i<n;i+)scanf("%d",a+i);j=num=a0;t=1;for(i=1;i<n;i+)if(ai=j)+t;if(t>max)max=t;num=ai; elset=1;j=ai;printf("%d",num);

15、return 0;  算法訓(xùn)練 字串統(tǒng)計(jì)  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述給定一個(gè)長(zhǎng)度為n的字符串S，還有一個(gè)數(shù)字L，統(tǒng)計(jì)長(zhǎng)度大于等于L的出現(xiàn)次數(shù)最多的子串（不同的出現(xiàn)可以相交），如果有多個(gè)，輸出最長(zhǎng)的，如果仍然有多個(gè)，輸出第一次出現(xiàn)最早的。輸入格式第一行一個(gè)數(shù)字L。第二行是字符串S。L大于0，且不超過S的長(zhǎng)度。輸出格式一行，題目要求的字符串。輸入樣例1：4bbaabbaaaaa輸出樣例1：bbaa輸入樣例2：2bbaabbaaaaa輸出樣例2：aa數(shù)據(jù)規(guī)模和約定n

16、<=60S中所有字符都是小寫英文字母。提示枚舉所有可能的子串，統(tǒng)計(jì)出現(xiàn)次數(shù)，找出符合條件的那個(gè)#include<stdio.h>#include<string.h>int main()char S1000,str10001000,temp100,out100;int L,i=0,s,otongji=0,ttongji,a,b,c;scanf("%d%c%c",&L,&S0,&S0);while(Si!='n') scanf("%c",&Si+1); i+; Si = '

17、0' for(s=i+1;L<=s;L+) for(a=0;a<s+1-L;a+)/賦值 for(b = 0;b < L;b+) strab=Sa+b; strab = '0' for(i = 0;i < a-1;)/比較 for(b = 0;b<a;b+) if(strb0!='0') for(c = 0;c<L;c+) tempc=strbc; tempc = '0' ttongji = 1; i+; strb0 = '0' break; for(b+;b<a;b+) if(!

18、strcmp(strb,temp) ttongji+; i+; strb0 = '0' if(ttongji > otongji|(ttongji=otongji&&strlen(temp)>strlen(out) strcpy(out,temp); otongji = ttongji; i = 0; while(outi != '0') printf("%c",outi); i+; getchar();return 0;算法訓(xùn)練 矩陣乘法  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB&#

19、160;     查看參考代碼 錦囊1錦囊2錦囊3問題描述輸入兩個(gè)矩陣，分別是m*s，s*n大小。輸出兩個(gè)矩陣相乘的結(jié)果。輸入格式第一行，空格隔開的三個(gè)正整數(shù)m,s,n（均不超過200）。接下來m行，每行s個(gè)空格隔開的整數(shù)，表示矩陣A（i，j）。接下來s行，每行n個(gè)空格隔開的整數(shù)，表示矩陣B（i，j）。輸出格式m行，每行n個(gè)空格隔開的整數(shù)，輸出相乘後的矩陣C（i，j）的值。樣例輸入2 3 21 0 -11 1 -30 31 23 1樣例輸出-3 2-8 2提示矩陣C應(yīng)該是m行n列，其中C(i,j)等于矩陣A第i行行向量與矩陣B第j列列向量的內(nèi)積。例如樣例中C(1,1)=(1

20、,0,-1)*(0,1,3) = 1 * 0 +0*1+(-1)*3=-3 # include<stdio.h>int main()int m,s,n,i,j,k,a200200,b200200,c200200;scanf("%d%d%d",&m,&s,&n);for(i=1;i<=m;i+)for(j=1;j<=s;j+)scanf("%d",&aij);for(i=1;i<=s;i+)for(j=1;j<=n;j+)scanf("%d",&bij);for

21、(i=1;i<=m;i+)for(j=1;j<=n;j+)cij=0;for(i=1;i<=m;i+)for(j=1;j<=n;j+)for(k=1;k<=s;k+)cij=cij+aik*bkj;for(i=1;i<=m;i+)for(j=1;j<=n;j+)printf("%d ",cij);printf("n");return 0;算法訓(xùn)練 大小寫轉(zhuǎn)換  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫

22、一個(gè)程序，輸入一個(gè)字符串（長(zhǎng)度不超過20），然后把這個(gè)字符串內(nèi)的每一個(gè)字符進(jìn)行大小寫變換，即將大寫字母變成小寫，小寫字母變成大寫，然后把這個(gè)新的字符串輸出。輸入格式：輸入一個(gè)字符串，而且這個(gè)字符串當(dāng)中只包含英文字母，不包含其他類型的字符，也沒有空格。輸出格式：輸出經(jīng)過轉(zhuǎn)換后的字符串。輸入輸出樣例樣例輸入AeDb樣例輸出aEdB#include <stdio.h>int main()int i;char ch100;gets(ch);i=0;while(chi!='0')if(chi<='z'&&chi>='a

23、9;)chi-=32;else chi+=32;i+;puts(ch);return 0;算法訓(xùn)練 動(dòng)態(tài)數(shù)組使用  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3從鍵盤讀入n個(gè)整數(shù)，使用動(dòng)態(tài)數(shù)組存儲(chǔ)所讀入的整數(shù)，并計(jì)算它們的和與平均值分別輸出。要求盡可能使用函數(shù)實(shí)現(xiàn)程序代碼。平均值為小數(shù)的只保留其整數(shù)部分。樣例輸入53 4 0 0 2樣例輸出9 1樣例輸入73 2 7 5 2 9 1樣例輸出29 4#include <stdio.h>int main()int i,n,a100,b100

24、,sum=0,avg=0;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&bi);ai=bi;sum=sum+ai;avg=sum/n;printf("%d %dn",sum,avg);return 0;算法訓(xùn)練 刪除數(shù)組零元素  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3從鍵盤讀入n個(gè)整數(shù)放入數(shù)組中，編寫函數(shù)CompactIntegers，刪除數(shù)組中所有值為0的元素，其后元素向

25、數(shù)組首端移動(dòng)。注意，CompactIntegers函數(shù)需要接受數(shù)組及其元素個(gè)數(shù)作為參數(shù)，函數(shù)返回值應(yīng)為刪除操作執(zhí)行后數(shù)組的新元素個(gè)數(shù)。輸出刪除后數(shù)組中元素的個(gè)數(shù)并依次輸出數(shù)組元素。樣例輸入: （輸入格式說明：5為輸入數(shù)據(jù)的個(gè)數(shù)，3 4 0 0 2 是以空格隔開的5個(gè)整數(shù)）53 4 0 0 2樣例輸出:（輸出格式說明：3為非零數(shù)據(jù)的個(gè)數(shù)，3 4 2 是以空格隔開的3個(gè)非零整數(shù)）33 4 2樣例輸入70 0 7 0 0 9 0樣例輸出27 9樣例輸入30 0 0樣例輸出0算法訓(xùn)練 最小乘積(基本型)  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB   

26、  查看參考代碼 錦囊1錦囊2錦囊3問題描述給兩組數(shù)，各n個(gè)。請(qǐng)調(diào)整每組數(shù)的排列順序，使得兩組數(shù)據(jù)相同下標(biāo)元素對(duì)應(yīng)相乘，然后相加的和最小。要求程序輸出這個(gè)最小值。例如兩組數(shù)分別為:1 3-5和-2 4 1那么對(duì)應(yīng)乘積取和的最小值應(yīng)為：(-5) * 4 + 3 * (-2) + 1 * 1 = -25輸入格式第一個(gè)行一個(gè)數(shù)T表示數(shù)據(jù)組數(shù)。后面每組數(shù)據(jù)，先讀入一個(gè)n，接下來兩行每行n個(gè)數(shù)，每個(gè)數(shù)的絕對(duì)值小于等于1000。n<=8,T<=1000輸出格式一個(gè)數(shù)表示答案。樣例輸入231 3 -5-2 4 151 2 3 4 51 0 1 0 1樣例輸出-256#include&l

27、t;stdio.h>void sort1(int *a,int n)int i,j;int tmp;for(i=0;i<n-1;i+)for(j=0;j<n-1-i;j+)if(aj>aj+1)tmp=aj;aj=aj+1;aj+1=tmp;void sort2(int *a,int n)int i,j;int tmp;for(i=0;i<n-1;i+)for(j=0;j<n-1-i;j+)if(aj<aj+1)tmp=aj;aj=aj+1;aj+1=tmp;int main(void)int T;int n,i;int total;int a8,b8

28、,c8;scanf("%d",&T);while(T)total=0;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&ai);for(i=0;i<n;i+)scanf("%d",&bi);sort1(a,n);sort2(b,n);for(i=0;i<n;i+)ci=ai*bi;for(i=0;i<n;i+)total+=ci;printf("%dn",total);T-;return 0;算法訓(xùn)練 To

29、rry的困惑(基本型)  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述Torry從小喜愛數(shù)學(xué)。一天，老師告訴他，像2、3、5、7這樣的數(shù)叫做質(zhì)數(shù)。Torry突然想到一個(gè)問題，前10、100、1000、10000個(gè)質(zhì)數(shù)的乘積是多少呢？他把這個(gè)問題告訴老師。老師愣住了，一時(shí)回答不出來。于是Torry求助于會(huì)編程的你，請(qǐng)你算出前n個(gè)質(zhì)數(shù)的乘積。不過，考慮到你才接觸編程不久，Torry只要你算出這個(gè)數(shù)模上50000的值。輸入格式僅包含一個(gè)正整數(shù)n，其中n<=100000。輸出格式輸出一行，即

30、前n個(gè)質(zhì)數(shù)的乘積模50000的值。樣例輸入1樣例輸出2#include<stdio.h>int pr100010;int top;int isPrime(int n)int i;for(i = 0; i < top; i+)if(n % pri = 0)return 0;return 1;int findNextPrime(void)int n = prtop - 1 + 1;while(!isPrime(n)n+;prtop+ = n;return n;int main(void)int i, n;int result = 2;scanf("%d", &

31、amp;n);pr0 = 2;top = 1;for(i = 1; i < n; i+)int x = findNextPrime();result *= x;result %= 50000;printf("%d", result);return 0;算法訓(xùn)練 尋找數(shù)組中最大值  時(shí)間限制：1.0s   內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述對(duì)于給定整數(shù)數(shù)組a,尋找其中最大值，并返回下標(biāo)。輸入格式整數(shù)數(shù)組a,數(shù)組元素個(gè)數(shù)小于1等于100。輸出數(shù)據(jù)分作兩行：第一行只有一個(gè)數(shù)，表示數(shù)組

32、元素個(gè)數(shù)；第二行為數(shù)組的各個(gè)元素。輸出格式輸出最大值，及其下標(biāo)樣例輸入33 2 1樣例輸出3 0#include <stdio.h>int main()int n,i,k,max;scanf ("%d",&n);int an;for(i=0;i<n;i+)scanf("%d",&ai);max=a0;for(i=0;i<n;i+)if(ai>=max)max=ai;k=i;printf("%d %d",max,k);return 0;算法訓(xùn)練 關(guān)聯(lián)矩陣  時(shí)間限制：1.0s &#

33、160; 內(nèi)存限制：512.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述有一個(gè)n個(gè)結(jié)點(diǎn)m條邊的有向圖，請(qǐng)輸出他的關(guān)聯(lián)矩陣。輸入格式第一行兩個(gè)整數(shù)n、m，表示圖中結(jié)點(diǎn)和邊的數(shù)目。n<=100,m<=1000。接下來m行，每行兩個(gè)整數(shù)a、b，表示圖中有(a,b)邊。注意圖中可能含有重邊，但不會(huì)有自環(huán)。輸出格式輸出該圖的關(guān)聯(lián)矩陣，注意請(qǐng)勿改變邊和結(jié)點(diǎn)的順序。樣例輸入5 91 23 11 52 52 32 33 24 35 4樣例輸出1 -1 1 0 0 0 0 0 0-1 0 0 1 1 1 -1 0 00 1 0 0 -1 -1 1 -1 0

34、0 0 0 0 0 0 0 1 -10 0 -1 -1 0 0 0 0 1#include<stdio.h>int main()int i, ii,n,m, a10002;scanf("%d%d", &n, &m);for ( i = 0; i < m; i+)scanf("%d%d", &ai0, &ai1);for ( i = 1; i <=n; i+)for (ii = 0; ii < m; ii+)if (i=aii0)printf("1 ");elseif (i=

35、aii1)printf("-1 ");elseprintf("0 ");printf("n");return 0;算法訓(xùn)練 操作格子  時(shí)間限制：1.0s   內(nèi)存限制：256.0MB      查看參考代碼 錦囊1錦囊2錦囊3問題描述有n個(gè)格子，從左到右放成一排，編號(hào)為1-n。共有m次操作，有3種操作類型：1.修改一個(gè)格子的權(quán)值，2.求連續(xù)一段格子權(quán)值和，3.求連續(xù)一段格子的最大值。對(duì)于每個(gè)2、3操作輸出你所求出的結(jié)果。輸入格式第一行2個(gè)整數(shù)n，m。接下來一行n個(gè)整數(shù)表示n個(gè)格子的初

36、始權(quán)值。接下來m行，每行3個(gè)整數(shù)p,x,y，p表示操作類型，p=1時(shí)表示修改格子x的權(quán)值為y，p=2時(shí)表示求區(qū)間x,y內(nèi)格子權(quán)值和，p=3時(shí)表示求區(qū)間x,y內(nèi)格子最大的權(quán)值。輸出格式有若干行，行數(shù)等于p=2或3的操作總數(shù)。每行1個(gè)整數(shù)，對(duì)應(yīng)了每個(gè)p=2或3操作的結(jié)果。樣例輸入4 31 2 3 42 1 31 4 33 1 4 樣例輸出63 數(shù)據(jù)規(guī)模與約定對(duì)于20%的數(shù)據(jù)n <= 100，m <= 200。對(duì)于50%的數(shù)據(jù)n <= 5000，m <= 5000。對(duì)于100%的數(shù)據(jù)1 <= n <= 100000，m <= 100000，0 <= 格

37、子權(quán)值 <= 10000。錦囊1使用線段樹。 錦囊2線段樹的每個(gè)結(jié)點(diǎn)記錄下這一段區(qū)間所有數(shù)的和以及最大值即可。 #include <stdio.h>#define N 100000#define A 1000#define B 100int sum(int* a, int m, int n) int i, s = 0; for (i = m; i <= n; i+) s += ai; return s;int max(int* a, int m, int n) int i, s = am; for (i = m + 1; i <= n; i+) if (s <

38、; ai) s = ai; return s;int main() int i, j, k, m, n; int a100000, b1000003, cA2 = 0; scanf("%d%d", &n, &m); for (i = 0; i < n; i+) scanf("%d", &ai); for (i = 0; i < m; i+) for (j = 0; j < 3; j+) scanf("%d", &bij); for (i = 0; i < (n + B - 1)

39、/ B; i+) ci0 = ci1 = ai * B; for (j = i * B + 1; j < i * B + B && j < n; j+) ci0 += aj; if (ci1 < aj) ci1 = aj; for (i = 0; i < m; i+) if (bi0 = 1) c(bi1 - 1) / B0 += bi2 - abi1 - 1; k = (bi1 - 1) / B; if (ck1 <= bi2) ck1 = bi2; else if (abi1 - 1 = ck1) abi1 - 1 = bi2; ck1 = m

40、ax(a, k * B, k * B + B > n ? n - 1 : k * B + B - 1); abi1 - 1 = bi2; else if (bi0 = 2) int s = 0; bi1-, bi2-; int o = bi2 / B - bi1 / B; if (o < 2) s = sum(a, bi1, bi2); else s = sum(a, bi1, (bi1 + B) / B * B - 1); s += sum(a, bi2 / B * B, bi2); for (j = bi1 / B + 1; j < bi2 / B; j+) s += c

41、j0; printf("%dn", s); else if (bi0 = 3) int s = 0, t; bi1-, bi2-; int o = bi2 / B - bi1 / B; if (o < 2) s = max(a, bi1, bi2); else s = max(a, bi1, (bi1 + B) / B * B - 1); t = max(a, bi2 / B * B, bi2); if (s < t) s = t; for (j = bi1 / B + 1; j < bi2 / B; j+) if (s < cj1) s = cj1

42、; printf("%dn", s); return 0;/ test/ 1.cpp/* ID: Firwaless LANG: C+ TASK: */#include <cstdio>#include <algorithm>struct Tree int sum, max;Tree tree1 << 18;void scan(int &n) char c; c = getchar(); if (c = EOF) return ; while (c < '0' | c > '9') c

43、= getchar(); n = c - '0' while (c = getchar(), c >= '0' && c <= '9') n *= 10; n += c - '0' void put(int n) int cnt = 0; char s16; if (n = 0) putchar('0'); return ; for( ; n; n /= 10) scnt+ = n % 10 + '0' while (cnt-) putchar(scnt); void u

44、pdate(int n, int v) for (n += (1 << 17),treen.sum = treen.max = v, n >>= 1; n; n >>= 1) treen.max = std:max(treen + n.max, treen + n + 1.max); treen.sum = treen + n.sum + treen + n + 1.sum; int query(int s, int t, int func) int sum = 0, max = 0; for (s += (1 << 17) - 1, t +=

45、(1 << 17) + 1; s t 1; s >>= 1, t >>= 1) if (s & 1) sum += trees 1.sum; max = std:max(max, trees 1.max); if (t & 1) sum += treet 1.sum; max = std:max(max, treet 1.max); return func ? max : sum;int main() int n, m, i, a, b, c; scan(n);scan(m); for (i = 1; i <= n; +i) scan(a); update(i, a); while (m-) scan(c);scan(a);scan(b); c = 1 && (update(a, b), 0); c = 2 &am