信息学院第九届ACM程序设计竞赛题解

信息学院第九届ACM程序设计竞赛题解 A: 信号与系统

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 238 Accepted: 44 Page View: 69

Description

上决╇ф正在学习万恶的信号与系统(SAS),各种卷积、傅里叶等恶心的变化。现在,上决╇ф碰到了一个很简单但是很烦人的问题,又一个离散信号,要求出这个信号最大值和最小值出现的次数。上决╇ф现在很忙,这个问题就交给你了。

Input

第一排一个数T( 0 < T <= 100 ),表示测试组数。
每组测试的第一排一个数n(0 < n <= 100),表示这个信号有n个离散点。
接下一排有n个数,对于每一个数Ai,表示该点的信号值的大小,(-100 <= Ai <= 100)。

Output

对于每一组测试输出一排,格式为:"Case #X: A B"(不包括引号),A表示这个信号最大值出现的次数,B表示最小值出现的次数。X代测试表数据编号。
Sample Input
2
6
1 1 2 2 3 3
5
79 79 79 79 79
Sample Output
Case #1: 2 2
Case #2: 5 5
Status Clarify
膜拜巨巨都学这些了,各种卷积、傅里叶等,Orz
签到题、排序即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int main()
{
int n,T,i,iCase=;
int a[];
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=;i<=n;i++) scanf("%d",&a[i]);
sort(a+,a+n+);
int cnt1=,cnt2=;
for(i=;i<=n;i++)
{
if(a[i]==a[i+]) cnt1++;
else break;
}
for(i=n;i>=;i--)
{
if(a[i]==a[i-]) cnt2++;
else break;
}
printf("Case #%d: %d %d\n",iCase++,cnt2,cnt1);
}
return ;
}

信息学院第九届ACM程序设计竞赛题解 B: 小红开班会

Time Limit: 2000 MS Memory Limit: 65536 KB
Total Submit: 196 Accepted: 24 Page View: 44

Description

小红当了超级一班的辅导员,他召开了一次班会。超级一班共有n个人,但是开完会以后他看了下签到表,上面只有n-1个人的学号。小红想知道哪个人没来,他知道n个人的学号,但是由于人太多,小红找不出来,所以请你帮他找出没来的那个人的学号。

Input

第一行输入一个数字T。表示有T组数据。
每组输入共3行。
第一行1个数n,表示超级一班的人数(2<=n<=100000)
第二行n个数,分别表示n个人的学号(每个数小于2^31,且n个数一定互不相同,两个数字之间以空格隔开)
第三行n-1个数,为签到表上的学号(输入保证每个数都为上一行的n个数之一,且n-1个数一定互不相同)

Output

每组数据输出一行,输出格式为:"Case #x: y"。x表示这是第几组数据。y表示没来参加班会的人的学号。
Sample Input
2
3
1 2 3
2 3
4
20121010 20131320 20121111 20111234
20131320 20111234 20121111
Sample Output
Case #1: 1
Case #2: 20121010
Status Clarify
签到题、
方法1:排序
方法2:异或即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int main()
{
int n,T,i,iCase=;
int a[],b[];
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=;i<=n;i++) scanf("%d",&a[i]);
for(i=;i<n;i++) scanf("%d",&b[i]);
sort(a+,a+n+);
sort(b+,b+n);
int ans;
for(i=;i<=n;i++)
{
if(a[i]!=b[i])
{
ans=a[i];
break;
}
}
printf("Case #%d: %d\n",iCase++,ans);
}
return ;
}

信息学院第九届ACM程序设计竞赛题解 C: 小红去看花卉展

Time Limit: 2000 MS Memory Limit: 65536 KB
Total Submit: 23 Accepted: 0 Page View: 109

Description

春天来了,小红跑去看花卉展。花卉展摆了n排花,每排有m盘花卉,从左到右编号为1到m。每盘花卉都有一个标签,上面标明了这盘花卉的价格。

看到这一排一排的数字小红脑海里突然浮现出一个问题:是否存在一个区间[l,r],使得每排花卉区间[l,r]的花卉的价格和相等?如果存在,那么这样的区间最长为多少?

Input

第一行输入一个数字T,表示输入数据组数。
对于每组数据输入:
第一行两个数:n,m(1<=n<=30,1<=m<=10000)
接下来输入n行,每行m个数字。第i行的第j个数,表示第i排的第j盘花卉的价格(输入保证每个数大于等于0且小于2^31)。

Output

对于每组数据,输出一行"Case #x: y",x表示这是输入的第几组数据,y表示满足条件的最长的区间。如果不存在,y为-1。
Sample Input
2
1 3
1 2 3
2 3
1 2 3
4 3 1
Sample Output
Case #1: 3
Case #2: -1
Status Clarify
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define N 33
#define M 10010 struct Node{
int size;
int a[N];
Node(){}
bool operator <(const Node &p)const{
for(int i=;i<size;i++){
if(a[i]!=p.a[i]) return a[i]<p.a[i];
}
return ;
}
};
int n,m;
int a[N][M];
ll sum[N][M];
ll con[N][M];
map<Node,int> mp; int main()
{
int T,i,j,iCase=;
scanf("%d",&T);
while(T--){
mp.clear();
scanf("%d%d",&n,&m);
for(i=;i<=n;i++){
sum[i][]=;
for(j=;j<=m;j++){
scanf("%d",&a[i][j]);
sum[i][j]=sum[i][j-]+a[i][j];
}
}
for(i=;i<=n;i++){
con[i][]=;
for(j=;j<=m;j++){
con[i][j]=sum[i][j]-sum[][j];
}
} int ans=-;
for(j=;j<=m;j++){
Node t;
t.size=n-;
for(i=;i<=n;i++){
t.a[i-]=con[i][j];
}
if(!mp[t]) mp[t]=j+;
else ans=max(ans,j-mp[t]+);
}
printf("Case #%d: %d\n",iCase++,ans);
}
return ;
}
 

信息学院第九届ACM程序设计竞赛题解 D: islands打炉石传说

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 64 Accepted: 10 Page View: 82

Description

islands最近在完一款游戏“炉石传说”,又名“魔兽英雄传”。炉石传说是一款卡牌类对战的游戏。游戏是2人对战,总的来说,里面的卡牌分成2类,一类是法术牌,另一类是随从牌(所谓随从就是怪物)。

为了简化问题,现在假设随从牌的作用是召唤一个具有一定攻击力的怪物,法术牌的作用是给某个随从增加一定攻击力。随从牌和法术牌的使用都需要消耗一定的法力值。现在islands有10点法力值,手上有n张牌(islands最多有10张牌,否者他将会被爆牌T_T),有些是法术牌,有些是随从牌。islands现在是大劣势,他想要是利用这10点法力值使得召唤出来的所有随从的攻击力总和最高(法力值可以不用完)。注意,任何法术牌都必须使用在某个召唤出来的随从上,也就是如果islands没有召唤过随从,他将不能使用任何法术牌。告诉islands他能召唤的随从的总攻击力最大是多少。

Input

首先输入测试数据组数T(T<=10)
每组数据首先输入一个n(0<=n<=10),表示islands有n张牌接下来n行每行输入3个整数 cost(0<=cost<=10),d(0或者1),w(|w|<=1000)。cost表示该牌的法力值消耗,如果d=0,表示该牌是攻击力为w的随从牌,如果d=1,表示是能给一个随从增加w攻击的法术牌。

Output

对于每组数据输出按照格式“Case #x: a”(不包括冒号)输出一行。其中x表示第x组测试数据,a表示对应的答案。
Sample Input
2
1
1 0 100
1
1 1 100
Sample Output
Case #1: 100
Case #2: 0
Status Clarify
水题、
方法1:暴力
方法2:01背包
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 10000 int n,s;
int w1[],v1[],n1;
int w0[],v0[],n0;
int dp[]; int main()
{
int T,i,j,k,iCase=;
scanf("%d",&T);
while(T--)
{
n0=n1=;
scanf("%d",&n);
for(i=;i<=n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b==)
w0[++n0]=a,v0[n0]=c;
else
w1[++n1]=a,v1[n1]=c;
}
int ans=;
int ww,vv;
for(k=;k<=n0;k++)
{
memset(dp,,sizeof(dp));
dp[]=v0[k];
s=-w0[k];
for(i=;i<=n0+n1;i++)
{
if(i==k) continue;
if(i<=n0) ww=w0[i],vv=v0[i];
else ww=w1[i-n0],vv=v1[i-n0];
for(j=s;j>=ww;j--)
{
dp[j]=max(dp[j],dp[j-ww]+vv);
}
}
int tmp=;
for(j=;j<=;j++) tmp=max(tmp,dp[j]);
ans=max(ans,tmp);
}
printf("Case #%d: %d\n",iCase++,ans);
}
return ;
}

信息学院第九届ACM程序设计竞赛题解 E: 小红学数学

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 184 Accepted: 43 Page View: 59

Description

众所周知,小红是一个不折不扣月收入好几E的大土豪,最近小红来swust学习数学,我上决╇ф这个小diaosi岂能错过抱大腿的机会?为什么小红要来swust学数学呢?毕竟钱多人傻,23333333。小红碰到的问题就是这么简单他都不会,求一个数的质因子个数。想抱大腿么?请继续……

Input

第一排一个数T,为测试组数。
每组一排只有一个数字n,(0< n<=10000),测试组数不超过20组。

Output

每组输出一排,"Case #X: "和n的质因子的个数。X代表测试编号。
Sample Input
2
10
5
Sample Output
Case #1: 2
Case #2: 1

Hint

此题1不属于质数。
质因子:假设A是质数,且B%A==0,那么A就是B的质因子。
Status Clarify
签到题,暴力或者筛素数都行
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 10000 int tot;
int prime[N+];
bool isprime[N+];
void init()
{
tot=;
memset(isprime,,sizeof(isprime));
isprime[]=isprime[]=;
for(int i=;i<=N;i++)
{
if(isprime[i]) prime[tot++]=i;
for(int j=;j<tot;j++)
{
if((ll)i*prime[j]>N) break;
isprime[i*prime[j]]=;
if(i%prime[j]==)
break;
}
}
}
int main()
{
init();
int n,T,i,iCase=;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans=;
for(int i=;i<tot;i++)
{
if(n%prime[i]==)
ans++;
}
printf("Case #%d: %d\n",iCase++,ans);
}
return ;
}

信息学院第九届ACM程序设计竞赛题解 F: 上决╇ф的IDE

Time Limit: 5000 MS Memory Limit: 65536 KB
Total Submit: 27 Accepted: 1 Page View: 25

Description

上决╇ф觉得Code::Blocks的编辑器太难用了,决定自己开发一个编辑器。现在,这个编辑器正处于开发的初期,只能进行剪切和粘贴成对的操作来处理特殊文本。该文本文件共有N行文本,每一行文本仅包含一个自然数,第一行为1、第二行为2,以此类推至N行为自然数N。假设对该文本文件执行一次“剪切和粘贴”操作含义如下:首先选定连续的若干行文本,“剪切”操作将选定的文本从文件中剪下(后面的内容将自动往前移动),而“粘贴”操作将剪切下来的文本插入到文件中的其他地方。上决╇ф想知道,在进行了连续若干次“剪切和粘贴”操作后,文本文件中前十行的内容,以验证这个编辑器的正确性。

Input

第一行一个整数T,表示测试组数。
每组的第一行包含两个用空格隔开的自然数N和K,N表示文件的总行数(10≤N≤100,000),K表示“剪切和粘贴”的总次数(1≤k≤100000)。
下面K行每一行包含一次“剪切和粘贴”操作的执行信息,每行包含三个用空格隔开自然数A,B和C,其中1≤A≤B≤N,0≤C≤N-(B-A+1)。A和B表示选定文本的第一行和最后一行,C表示被剪切下来的文本待插入处的前一行,如果C等于0则被剪切下来的的文本将被插入到文件的开头。

Output

对于每组测试,先输出一行"Case #X:"。X表示测试编号。
接下来10行,为所有的操作都完成后的文本文件中前十行所包含的数字。
Sample Input
2
13 3
6 12 1
2 9 0
10 13 8
10 1
2 4 2
Sample Output
Case #1:
6
7
8
9
10
11
12
2
3
4
Case #2:
1
5
2
3
4
6
7
8
9
10
Status Clarify
方法1:暴力Splay
方法2:从后往前推
代码写得搓,将就一下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define ll __int64
#define N 100010 int n,m;
int ansl;
int ans[N];
struct SplayTree
{
int ch[N][],pre[N],val[N],num[N],rev[N],sz[N];
int top,root; inline void Rotate(int x,int c){
int y=pre[x];
ch[y][!c]=ch[x][c];
if(ch[x][c]) pre[ch[x][c]]=y;
pre[x]=pre[y];
if(pre[y]) ch[pre[y]][ch[pre[y]][]==y]=x;
ch[x][c]=y;
pre[y]=x;
PushUp(y);
if(y==root) root=x;
}
inline void Splay(int x,int f){
while(pre[x]!=f)
{
if(pre[pre[x]]==f) Rotate(x,ch[pre[x]][]==x);
else
{
int y=pre[x],z=pre[y];
int c=(ch[z][]==y);
if(ch[y][c]==x) Rotate(x,!c),Rotate(x,c);
else Rotate(y,c),Rotate(x,c);
}
}
PushUp(x);
if(f==) root=x;
}
inline void SplayKth(int k,int f){
int x=root;
k+=;
while()
{
if(k==sz[ch[x][]]+) break;
else if(k<=sz[ch[x][]]) x=ch[x][];
else k-=sz[ch[x][]]+,x=ch[x][];
}
Splay(x,f);
}
inline void PushUp(int x){
sz[x]=sz[ch[x][]]+sz[ch[x][]]+;
}
inline void NewNode(int &x,int c,int f){
x=++top;
sz[x]=;
ch[x][]=ch[x][]=rev[x]=;
val[x]=c;
pre[x]=f;
}
inline void Build(int &x,int l,int r,int f){
if(l>r) return;
int m=(l+r)>>;
NewNode(x,num[m],f);
Build(ch[x][],l,m-,x);
Build(ch[x][],m+,r,x);
PushUp(x);
}
inline void Init(int n){
top=pre[]=ch[][]=ch[][]=sz[]=rev[]=;
val[]=INF;
for(int i=;i<=n;i++) num[i]=i;
Build(root,,n+,);
}
void Res()
{
int l,r,tt;
scanf("%d%d%d",&l,&r,&tt);
int len=r-l+;
l--;
SplayKth(l,);
SplayKth(r+,root);
int x=ch[ch[root][]][];
ch[ch[root][]][]=;
PushUp(ch[root][]);
PushUp(root);
tt++;
SplayKth(tt-,);
SplayKth(tt,root);
ch[ch[root][]][]=x;
pre[ch[ch[root][]][]]=ch[root][];
PushUp(ch[root][]);
PushUp(root);
}
void Print(int x){
if(ch[x][]) Print(ch[x][]);
if(val[x]>= && val[x]<=n)
ans[++ansl]=val[x];
if(ch[x][]) Print(ch[x][]);
}
}t;
int main()
{
int T,j,iCase=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
t.Init(n);
printf("Case #%d:\n",iCase++);
while(m--) t.Res();
ansl=;
t.SplayKth(t.root,);
t.Print(t.root);
for(int i=;i<=;i++) cout<<ans[i]<<endl;
}
return ;
}

G: islands想吃糖果

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 24 Accepted: 0 Page View: 80

Description

daidao买了很多糖果带到实验室,里面有n颗,islands看到了很高兴马上准备吃。daidao数了一下实验室的人有m个(包括daidao),问islands如果你能告诉我有多少种不同方案把这些糖果分给实验室的m个人,并且每人至少都要分一个,我就给你吃(对于2个方案,只要存在一个或一个以上的人分的数目不同就是2个不同的方案)。旁边的w703710691d说这可难不倒islands,再加上一个条件,要求每个人分的糖果的个数的最大公约数正好为k。(m个数的最大公约数是说有能整除这m个数中的最大的)。由于答案很大,daidao要求答案对1000000007取模。这下islands难住了,你能帮助islands吃到糖果吗。

Input

首先输入一个证书T表示测试数据组数(T<100)
接下来T行每行输入3个正整数,n,m,k。( 0 < n,m,k < = 200)

Output

对于每组数据输出按照格式“Case #x: a”(不包括冒号)输出一行。其中x表示第x组测试数据,a表示对应的答案。 
Sample Input
3
1 1 1
4 2 2
5 3 1
Sample Output
Case #1: 1
Case #2: 1
Case #3: 6
Status Clarify
后面再补,- -
 

H: islands学习几何

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 4 Accepted: 0 Page View: 22

Description

由于实验室的几何大神都纷纷退役了,islands不得不担任起学习几何的重任。

有一天他遇到了这样一道题。如右图,有一个三角形ABC,圆F和线段AB相切,和CA,CB延长线相切。圆E和线段AC相切,和BA,BC延长线相切。圆D和线段BC相切,和AB,AC延长线相切。现在已知三角形ABC的三边长a,b,c。分别求三角形DEF的面积和图中阴影部分的总面积。

信息学院第九届ACM程序设计竞赛题解

Input

首先输入测试组数T.(T<=10000)
接下来每组数据输入2个正整数a,b,c ( 0 < a,b,c <= 1000),表示三角形ABC的三边长吗,输入保证a,b,c能组成三角形。

Output

对于每组测试数据输出一行“Case #x: f1 f2”(不包括冒号),x表示第x组数据,f1表示该组数据三角形DEF的面积,f2表示阴影部分的面积(所有答案四舍五入到小数点后面2位)。
Sample Input
2
3 4 5
10 11 12
Sample Output
Case #1: 30.00 21.62
Case #2: 211.37 144.73
Status Clarify
后面再补,- -
 

I: 小红灌溉

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 17 Accepted: 0 Page View: 104

Description

小红家有n行田地,每行田地由m块大小为1*1的小田地组成。这些田地构成了一个n*m的矩形。小红在某些小田地里种植了蔬菜。现在小红要给蔬菜灌溉。小红每次可以选择给某一行或某一列的田地灌溉。但是一块种植了蔬菜的田地只能被灌溉一次。由于种种原因,灌溉某行或某列的耗电量不同。所以小红想知道,灌溉完所有蔬菜的耗电量最少为多少?

Input

第一行输入一个数字T,表示输入数据组数。
接下来每组数据:
第一行输入两个数n,m(1<=n<=100,1<=m<=100)
接下来输入n行,每行m个数字。第i行的第j个数为0表示第i行的第j块田地为空地,如果为1,表示第i行的第j列种植有蔬菜。
接下来一行输入n个数字,第i个数字,表示灌溉第i行的耗电量。(每个数字大于0小于等于1000)
接下来一行输入m个数字,第i个数字,表示灌溉第i列的耗电量。(每个数字大于0小于等于1000)

Output

输出T行,第i行输出"Case #i: y",y为第i组数据的答案。
Sample Input
1
2 2
1 0
0 1
1 2
2 1
Sample Output
Case #1: 2
Status Clarify
行列建图,对每个连通块二染色取最小
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define N 510
#define M N*N/2 struct Edge
{
int to,next;
}edge[M];
int head[N],tot; int n,m;
int a[N][N];
int cost[N];
int color[N];
int t[]; void init()
{
tot=;
memset(head,-,sizeof(head));
}
void add(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void dfs(int u,int c)
{
color[u]=c;
t[c]+=cost[u];
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(color[v]==-)
dfs(v,!c);
}
}
int main()
{
int T,iCase=;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=;i<=n+m;i++) scanf("%d",&cost[i]);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]){
add(i,j+n);
add(j+n,i);
}
}
}
int ans=;
memset(color,-,sizeof(color));
for(int i=;i<=n+m;i++){
t[]=t[]=;
if(color[i]==-) dfs(i,);
ans+=min(t[],t[]);
}
printf("Case #%d: %d\n",iCase++,ans);
}
return ;
}

信息学院第九届ACM程序设计竞赛题解 J: islands的难题

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 94 Accepted: 7 Page View: 90

Description

最近islands遇到一个难题,他想请人帮他解决。给一个数列a1,a2……an。有m个操作,每个操作是下面2种之一。

第1种操作是询问区间[l,r]上信息学院第九届ACM程序设计竞赛题解的值。

第2种操作是使得第k个数加上v。

Input

首先输入T表示测试数据组数(T<=5)
每组数据第一行输入n,m(n,m<=100000)表示n个数和m个操作。
接下来1行输入n个数,表示ai。(0<=a[i]<=100000)
接下来m行每行输入d(0或者1),l,r。
d=0表示第1操作 ( 0 < l <= r <= n),表示询问[l,r]上的答案。
d=1表示第2种操作( 0 < l <= n, 0 <= r <= 1000),表示a[l]加上r。

Output

对于每组测试数据首先输出一行“Case #x:”(不包括冒号)x表示第x组数据
对于m个操作,如果是1操作输出一行表示对应答案。
Sample Input
1
5 5
1 2 3 4 5
0 1 5
0 3 4
1 5 1
0 1 5
0 3 4
Sample Output
Case #1:
55
11
60
11
Status Clarify
简单线段树,维护区间和和区间权和(不知道咋说,见代码)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define N 100010 ll n,m;
ll a[N];
ll sum1[N<<];
ll sum2[N<<]; void pushup(ll rt)
{
sum1[rt]=sum1[rt<<]+sum1[rt<<|];
sum2[rt]=sum2[rt<<]+sum2[rt<<|];
}
void build(ll l,ll r,ll rt)
{
if(l==r)
{
sum2[rt]=a[l];
sum1[rt]=l*a[l];
return;
}
ll m=(l+r)>>;
build(l,m,rt<<);
build(m+,r,rt<<|);
pushup(rt);
}
void update(ll l,ll r,ll rt,ll pos,ll c)
{
if(l==r)
{
sum1[rt]+=pos*c;
sum2[rt]+=c;
return;
}
ll m=(l+r)>>;
if(pos<=m) update(l,m,rt<<,pos,c);
else update(m+,r,rt<<|,pos,c);
pushup(rt);
}
ll query(ll l,ll r,ll rt,ll L,ll R,ll op)
{
if(l==L && R==r)
{
if(op==) return sum1[rt];
else return sum2[rt];
}
ll m=(l+r)>>;
if(R<=m) return query(l,m,rt<<,L,R,op);
else if(L>m) return query(m+,r,rt<<|,L,R,op);
else return query(l,m,rt<<,L,m,op)+query(m+,r,rt<<|,m+,R,op);
}
int main()
{
ll T,i,j,iCase=;
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
for(i=;i<=n;i++) scanf("%lld",&a[i]);
build(,n,);
printf("Case #%lld:\n",iCase++);
while(m--)
{
ll op,a,b;
scanf("%lld%lld%lld",&op,&a,&b);
if(op==)
printf("%lld\n",query(,n,,a,b,)-(a-)*query(,n,,a,b,));
else
update(,n,,a,b);
}
}
return ;
}
上一篇:Ubuntu kylin 有可能成为未来中国的主流系统吗?


下一篇:爬取博主所有文章并保存到本地(.txt版)--python3.6