hud 6058 Kanade’s sum 题目大意：给你一个数组 a ，要求你求出a的所有子区间中第k大值的和。 解题思路：要找每个区间的第k大值，数据比较大，直接找肯定超时，所以我们不妨可可反着想，考虑一下每个值作为第k大有多少种情况，这样只需一次线性扫描就可以了，时间复杂度是O（n）。那么如何找呢？ 我们只要求出对于一个数x左边最近的k个比他大的和右边最近k个比他大的，扫一下就可以知道有几个区间的k大值是x. 具体代码如下：
#include <bits/stdc++.h> #define read(a) scanf("%d",&a) using namespace std; int a[500005],L[500005],R[500005]; ///L，R分别记录左边比它大的区间有多少个和右边比它大的区间有多少个 int main() { int T;read(T); while(T--) { int n,k; long long int ans = 0; read(n);read(k); for(int i=0;i<n;i++) read(a[i]); for(int i=0;i<n;i++) { int x = a[i],lcnt = 1,rcnt = 1,j; for(j = i + 1; j < n; j ++){///找x右边比它大的k个数 if(rcnt > k) break; if(a[j] > x) R[rcnt++] = j - i; } if(j == n)///如果不足k个的话说明知道最后一个数的第k大值 R[rcnt] = n - i; for(j = i - 1; j >= 0; j --) { if(lcnt > k) break; if(a[j] > x) L[lcnt++] = i - j; } if(j < 0) L[lcnt] = i + 1; // cout<<"lcnt: "<<lcnt<<" rcnt: "<<rcnt<<endl; // for(int ii = 1; ii <= lcnt; ii++) // cout<<L[ii]<<' '; // cout<<endl; // for(int ii = 1; ii <= rcnt; ii++) // cout<<R[ii]<<' '; // cout<<endl; for( j = 0; j < lcnt; j ++) { if(rcnt + j + 1 <= k) continue; int lnum = L[j + 1] - L[j]; int rnum = R[k - j] - R[k - j - 1]; // cout<<"a[i]:"<<a[i]<<" lnum: "<< lnum << " rnum: "<<rnum<<endl; ans += (long long)a[i] * lnum * rnum; } } printf("%lld\n",ans); } return 0; }