P8563 Magenta Potion
题目描述
给定一个长为nnn的整数序列aaa，其中所有数的绝对值均大于等于222。有qqq次操作，格式如下：
1 i k\texttt{1 i k}1 i k，表示将aia_iai修改为kkk。保证 $k $ 的绝对值大于等于222。
2 l r\texttt{2 l r}2 l r，考虑[l,r][l,r][l,r]的子区间（包括本身）中乘积最大的的区间乘积MMM。如果M>230M>2^{30}M>230，输出Too large，否则输出MMM。特别地，空区间的元素乘积定义为111。
输入格式
第一行两个正整数表示n,qn,qn,q。
第二行输入nnn个整数表示aia_iai。
接下来qqq行，每行三个整数表示一次询问，格式见上。
输出格式
对于每次2\tt22操作输出一行表示询问的答案。
输入输出样例 #1
输入 #1
5 7 2 2 3 4 5 2 1 5 1 3 -3 2 1 5 2 3 3 1 1 100000 1 2 100000 2 1 2输出 #1
240 20 1 Too large说明/提示
对于所有的数据，2≤∣ai∣,∣k∣≤1092\le |a_i|,|k| \le 10^92≤∣ai∣,∣k∣≤109，1≤n,q≤2×1051 \le n,q \le 2\times 10^51≤n,q≤2×105，1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n。
测试点编号 n,q≤ 特殊限制 1∼2103∼61007∼105×10311∼13A14∼16B17∼20 \def\arraystretch{1.5} \begin{array}{c|c|c}\hline \textbf{测试点编号}&\bm{~~~~~~~~n,q\le~~~~~~~~}&~~~~\textbf{特殊限制}~~~~\cr\hline \textsf1\sim \sf2 & 10& \cr\hline \sf3\sim 6 & 100& \cr\hline \sf7\sim 10 & 5 \times 10^3&\cr\hline \sf 11\sim 13 & &\sf A\cr\hline \sf14\sim 16 & & \sf B\cr\hline \sf17\sim 20 & &\cr\hline \end{array}测试点编号1∼23∼67∼1011∼1314∼1617∼20n,q≤101005×103特殊限制AB
A\textsf AA：保证ai,k≥2a_i,k \ge 2ai,k≥2。
B\textsf BB：保证对于每一组询问，对应的r−l≥100r-l \ge 100r−l≥100。
C++实现
#include<bits/stdc++.h>#definelllonglong#defineinf1<<30usingnamespacestd;intn,q;ll arr[200005];intmain(){cin>>n>>q;for(inti=1;i<=n;i++)cin>>arr[i];while(q--){intop,x,y;cin>>op>>x>>y;if(op==1)arr[x]=y;else{if(x==y&&arr[x]<0)cout<<1<<endl;else{if(y-x+1>61)cout<<"Too large"<<endl;else{intcnt=0;for(inti=x;i<=y;i++)if(arr[i]<0)cnt++;if(cnt%2==0){ll res=1;for(inti=x;i<=y&&res<=inf;i++)res*=abs(arr[i]);if(res>inf)cout<<"Too large"<<endl;elsecout<<res<<endl;}else{intl=x,r=y;while(arr[l]>0&&l<=y)l++;while(arr[r]>0&&r>=x)r--;ll res1=1,res2=1;for(inti=l+1;i<=y&&res1<=inf;i++)res1*=abs(arr[i]);for(inti=x;i<r&&res2<=inf;i++)res2*=abs(arr[i]);if(res1>inf||res2>inf)cout<<"Too large"<<endl;elsecout<<max(res1,res2)<<endl;}}}}}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
