傳送門（bzoj） 傳送門（luogu） 題目： Description 小西有一條很長的彩帶，彩帶上掛著各式各樣的彩珠。已知彩珠有N個，分為K種。簡單的說，可以將彩帶考慮為x軸，每一個彩珠有一個對應的坐標(即位置)。某些坐標上可以沒有彩珠，但多個彩珠也可以出現在同一個位置上。 小布生日快到了，於是 ...
/***************************************/
雖然是個蒟蒻但是轉載還是請註明出處哈
http://www.cnblogs.com/henry-1202/p/8666497.html
/***************************************/
傳送門（bzoj）
傳送門（luogu）
題目：
Description
小西有一條很長的彩帶，彩帶上掛著各式各樣的彩珠。已知彩珠有N個，分為K種。簡單的說，可以將彩帶考慮為x軸，每一個彩珠有一個對應的坐標(即位置)。某些坐標上可以沒有彩珠，但多個彩珠也可以出現在同一個位置上。 小布生日快到了，於是小西打算剪一段彩帶送給小布。為了讓禮物彩帶足夠漂亮，小西希望這一段彩帶中能包含所有種類的彩珠。同時，為了方便，小西希望這段彩帶儘可能短，你能幫助小西計算這個最短的長度麽？彩帶的長度即為彩帶開始位置到結束位置的位置差。Input
第一行包含兩個整數N, K，分別表示彩珠的總數以及種類數。接下來K行，每行第一個數為Ti，表示第i種彩珠的數目。接下來按升序給出Ti個非負整數，為這Ti個彩珠分別出現的位置。Output
應包含一行，為最短彩帶長度。Sample Input
6 31 5
2 1 7
3 1 3 8
Sample Output
3HINT
有多種方案可選，其中比較短的是1~5和5~8。後者長度為3最短。
【數據規模】
對於50%的數據， N≤10000；
對於80%的數據， N≤800000；
對於100%的數據，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。
題解：
寫法大意：單調隊列
sort一遍保證位置的單調性，開一個pos數組存第i種彩帶最後出現的位置，出隊的時候判斷一下那個元素的位置是否與pos數組相同即可（不同才能出隊）
就樣例來模擬一波：
6 3
1 5
2 1 7
3 1 3 8
進行排序以後的f數組：
| f[i].x | 2 | 3 | 3 | 1 | 2 | 3 |
| f[i].y | 1 | 1 | 3 | 5 | 7 | 8 |
（pos數組要先初始化為-1）
（len要初始化為f[n].y-f[1].y，即最壞的情況（否則會有5個點掛掉(luogu會，bzoj沒試過)））
當i=1時
pos[f[i].x]為-1，那麼f[i]入隊，隊列中的珠子多了一個了，cnt++
更新pos[f[i].x]的值為f[i].y
開始出隊操作：
當隊頭head<=隊尾i且隊頭的元素所在位置f[head].y！=該位置珠子最後出現的位置（即pos[f[head].x]）時就可以出隊了！
最後更新一下答案：
當cnt（隊列內珠子種數）=k（珠子種數）時就可以更新答案了！
len=min(len,f[i].y-f[head].y)
這樣從頭枚舉到尾就好了，時間複雜度（nlogn）（排序需要nlogn的時間複雜度）
代碼：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define min(x,y) x<y?x:y
inline void read(ll &x){
x=0;ll f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
using namespace std;
#define N 1000010
struct node{ll x,y;}f[N];
//x表示所屬彩珠類型，y表示w位置
ll n,k,len,pos[N];
bool cmp(node x,node y){return x.y<y.y;}
int main(){
read(n);read(k);ll a,b=0;
for(ll i=1;i<=k;i++){
read(a);pos[i]+=a;
for(ll j=1;j<=a;j++){
read(f[++b].y);
f[b].x=i;
}
}
sort(f+1,f+n+1,cmp);
len=f[n].y-f[1].y;ll head=1,cnt=0;
memset(pos,-1,sizeof(pos));
for(ll i=1;i<=n;i++){
if(pos[f[i].x]==-1)cnt++;
pos[f[i].x]=f[i].y;
while(head<=i&&f[head].y!=pos[f[head].x])head++;
if(cnt==k&&f[i].y-f[head].y<len)len=f[i].y-f[head].y;
}
printf("%d",len);
return 0;
}
