本題我用了一個類似單調隊列的東西...
將數列中每個點的位置和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;
}
