CodeForces Round #120 (190D) - Non-Secret Cypher

本题我用了一个类似单调队列的东西...
     将数列中每个点的位置和a记录..并优先级按先a再位置排序~~这样会得到相同a的点在一起..并且是按初始位置从小到大再一起...这样很容易观察到,当题目是要求子序列中至少k个相同时..若point[i]的a == point[i+k-1]的a并且point[i] 标记的原始位置~ point[i+k-1] 标记的原始位置是一个可行区间...找出这些区间..记录这些区间的起点和终点..这类区间的特点是从起点到终点恰有k个起点的a ...
     剩下的就是遍历原数列了...显然是需要符合条件的区间终点最小的..这里符合条件的意思是区间起点在当前点或者当前点后面..把这些区间按优先级先终点从小到大..否则起点从小到大...并用个指针指向排好序的区间的头..当前不符合条件..也就是某个区间的起点小于当前点..那后面必然也是无效的了..所以先从队头将无效的区间弹掉..直到当前区间的起点在当前点或者当前点后面...此时就可以找到从当前点能到达最近的点而符合k个相同了..那么显然从当前点出发到这区域终点后面一块也是满足要求的(包括了这个区域)..so..结果就出来了..
     似乎这么阐述思路还是有点混乱~~看代码吧~~蛮清晰的..

Program:
[cpp] 
#include<iostream> 
#include<algorithm> 
#include<stdio.h> 
#include<string.h> 
#include<cmath> 
#include<queue> 
#define oo 2000000000 
#define ll long long 
using namespace std; 
struct node 
{ 
       int w,d;  
}point[500000]; 
struct node1 
{ 
       int s,e; 
}h[500000]; 
ll ans; 
bool cmp1(node a,node b) 
{ 
       if (a.d!=b.d) return a.d<b.d; 
       return a.w<b.w; 
} 
bool cmp2(node1 a,node1 b) 
{ 
       if (a.e!=b.e) return a.e<b.e; 
       return a.s<b.s; 
} 
int main() 
{        
       int i,k,n,x,m; 
       scanf("%d%d",&n,&k); 
       for (i=1;i<=n;i++)  
       { 
              point[i].w=i; 
              scanf("%d",&point[i].d); 
       } 
       sort(point+1,point+1+n,cmp1); 
       m=0; 
       for (i=1;i<=n;i++) 
       { 
              x=i+k-1; 
              if (x<=n && point[x].d==point[i].d) 
              { 
                    m++; 
                    h[m].s=point[i].w; 
                    h[m].e=point[x].w; 
              } 
       } 
       sort(h+1,h+1+m,cmp2); 
       ans=0; 
       x=1; 
       for (i=1;i<=n;i++) 
       { 
              while (h[x].s<i && x<=m) x++; 
              if (x>m) break; 
              ans+=n-h[x].e+1;    
       } 
       printf("%I64d/n",ans); 
       return 0; 
}