P6503 [COCI 2010/2011 #3] DIFERENCIJA题目描述给出一个长度为n nn的序列a i a_iai​求出下列式子的值∑ i 1 n ∑ j i n ( max ⁡ i ≤ k ≤ j a k − min ⁡ i ≤ k ≤ j a k ) \sum_{i1}^{n} \sum_{ji}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k)i1∑n​ji∑n​(i≤k≤jmax​ak​−i≤k≤jmin​ak​)即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。输入格式输入第一行一个整数n nn表示序列的长度。接下来的n nn行每行一个整数a i a_iai​描述这个序列。输出格式输出一行一个整数表示式子的答案。输入输出样例 #1输入 #13 1 2 3输出 #14输入输出样例 #2输入 #24 7 5 7 5输出 #212输入输出样例 #3输入 #34 3 1 7 2输出 #331说明/提示数据规模与约定对于100 % 100\%100%的数据保证2 ≤ n ≤ 3 × 10 5 2\le n\le 3\times 10^52≤n≤3×1051 ≤ a i ≤ 10 8 1\le a_i\le 10^81≤ai​≤108。说明题目译自 COCI2010-2011 CONTEST #3T5 DIFERENCIJA。C实现#includeiostream#defineintlonglongusingnamespacestd;constintN3e59;intans0,mid;inta[N];intn;intq[N],head1;intstk[N];intcalc(){head1;intnow0;intsum0;for(inti1;in;i){while(head1a[q[head]]a[i]){now-(q[head]-q[head-1])*a[q[head]];head--;//不为最大值不扩展了}now(i-q[head])*a[i];//求出这个可以做多长时间的最大值sumnow;q[head]i;//添进去}returnsum;}signedmain(){scanf(%lld,n);for(inti1;in;i)scanf(%lld,a[i]);anscalc();for(inti1;in;i)a[i]*(-1);anscalc();//最小值变成最大值printf(%lld\n,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容