題意:給定m個移動,存到a數組裡表示,mi表示要把mi這個數移動到數組最前面,問m次移動中,1到n每個數在移動過程的最小和最大下标。
思路:其實這個思路挺好想的,但是比賽的時候用樹狀數組調處了bug,最後就嗚嗚嗚~~~~
首先,如果有數被移動到最前面,那麼它最小下标一定為1,如果沒有,那麼最小下标就是它一開始的下标(它沒有被移動最前面,那麼它的結果就是要麼不動,要麼被推到後面)。
然後就是最大下标:
觀察一下這m次移動,發現隻會有兩種情況:
1、這個數在之前已經有一次被移動到最前面的,那麼它的最大下标就是上次的位置到這次的位置之間有多少個不重複的數(用樹狀數組維護,求區間不重複的數,op取0),當然這個要和之前已記錄的最大下标要取max。
2、這個數之前沒有被移動到最前面,但現在要移動到最前面的。那麼它的最大下标就是比這個數大的其他數有多少被移動到最前面。(用樹狀數組,求比目前數大的數的個數,op取1)。
這樣就完了?沒有,這樣可能會有一樓,要再全部周遊一遍,比如樣例的2,如果不再周遊一遍的話,2就會被漏掉,重複1和2的過程就行。
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+1;
#define lowbit(i) ((i)&(-i))
int n,m,c[maxn][2],num[maxn],a[maxn],maxx[maxn],minn[maxn];
void add(int x,int val,int op)
{
int t=(op==0)?m:n;
while(x<=t) c[x][op]+=val,x+=lowbit(x);
}
int sum(int x,int op)
{
int res=0;
while(x>0) res+=c[x][op],x-=lowbit(x);
return res;
}
int main()
{
memset(num,0,sizeof(num));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) maxx[i]=minn[i]=i;
for(int i=1;i<=m;++i) scanf("%d",&a[i]),minn[a[i]]=1;
for(int i=1;i<=m;++i)
{
if(!num[a[i]])//情況2
{
add(i,1,0);
add(a[i],1,1);
maxx[a[i]]+=sum(n,1)-sum(a[i],1);
}
else{//情況1
add(num[a[i]],-1,0);
add(i,1,0);
maxx[a[i]]=max(maxx[a[i]],sum(i-1,0)-sum(num[a[i]],0)+1);
}
num[a[i]]=i;
}
for(int i=1;i<=n;++i)//防止遺漏
{
if(!num[i]) maxx[i]+=sum(n,1)-sum(i,1);
else maxx[i]=max(maxx[i],sum(m,0)-sum(num[i],0)+1);
}
for(int i=1;i<=n;++i)
printf("%d %d\n",minn[i],maxx[i]);
}