摘要：
Pid=5806主题含义：给你一个m和一个k，找出n个元素的数列中有多少个区间的最大值大于或等于m，如果后一个值小于或等于原始k最大值，则k最大值保持不变。但我不知道如何第一次满足要求。已经很久了。无需考虑其他问题。这样，它就成为一种非常标准的规则方法。
原题链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5806
题意：
给你一个m和k，求在n个元素的数列里有多少个区间的第k大的值大于等于m。
分析：
又是区间题，但是这题一看就感觉是尺取法。我们可以发现一个规律，如果一个区间存在第k大大于等于m，那每次加进新的值，也就是扩大区间的时候，如果后一个值小于等于原来的第k大，那么第k大不变。如果插入的数比原来的第k大大，那么新的第k大肯定比原来的第k大大，肯定满足条件，所以说只要枚举每一个起点，找到第一次满足第k大的值大于等于m，后面的剩余的区间都满足。但是感觉不知道怎么跑到第一次满足条件，坑了好久。
无意中听到学长的讨论，才发现自己还是想复杂了，确切的说是思维定势了，其实可以转个弯，要求有多少个区间的第k大值大于等于m，第一次满足条件只需要考虑，存在k个值大于等于m。
其他都无需考虑。这样就变成了一个非常标准的尺取法。代码非常短。
代码：
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<set> 6 #include<map> 7 #include<algorithm> 8 #include<string> 9 #include<queue> 10 #include<cmath> 11 #include<stack> 12 #include<cctype> 13 #include<list> 14 15 16 #define ll long long 17 #define ull unsigned long long 18 19 using namespace std; 20 21 const int maxn=200010; 22 const int inf=1<<30; 23 24 ll num[maxn]; 25 26 27 int main() 28 { 29 //#define DEBUG 30 31 #ifdef DEBUG 32 freopen("in.txt","r",stdin); 33 //freopen("out.txt","w",stdout); 34 #endif 35 36 int t; 37 scanf("%d",&t); 38 while(t--){ 39 int n,m,k; 40 scanf("%d%d%d",&n,&m,&k); 41 for(int i=0;i<n;i++){ 42 scanf("%I64d",&num[i]); 43 } 44 ll ans=0,res=0; 45 int l=0,r=0; 46 if(num[0]>=m)res++; 47 for(;r<n;){ 48 while(res<k){ 49 r++; 50 if(r>=n)break; 51 if(num[r]>=m){ 52 res++; 53 } 54 } 55 while(res>=k){ 56 ans+=n-r; 57 if(num[l]>=m){ 58 res--; 59 } 60 l++; 61 } 62 } 63 printf("%I64d ",ans); 64 } 65 return 0; 66 }