数据结构维护序列_插入首部与维护位置

发表于 分类于 阅读次数： Changyan：

维护序列:插入首部问题

经常能做到一些数据结构维护的，将一个序列中的某个位置的东西插入首部的问题。有些只需要简单用set或者其他基本的数据结构维护一下信息就行了，但是有些需要经过一些变化，一般需要树状数组或者线段树在变换后的基础上进行维护。

例如：

E. Messenger Simulator

大意就是一个n排列，m次操作把排列中的某个数字放到开头，你要维护每一个数字在序列中出现过的最左端和最右端。

方法：

预先留出n+m个空，n排列初始化到n+m最后n个位置。然后用BIT维护每个位置上是否有东西。每次更新的时候只需要修改左端点并查询当前位置前面有数的个数和右端点取max即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N=600010,M=N*2,mod=1e9+7;
int n,m,k,a[N],l[N],r[N],pos[N];
struct BIT{
	#define lowbit(x) ((x)&(-x))
	int tr[N],n;
	void resize(int _n){n=_n;}
	inline void add(int x,int d){for(;x<=n;x+=lowbit(x)) tr[x]+=d;}
	inline int ask(int x){int ans=0;for(;x;x-=lowbit(x)) ans+=tr[x];return ans;}
}T;

void solve(){
	n=read(),m=read();
	rep(i,1,n) l[i]=r[i]=i,pos[i]=m+i;
	T.resize(n+m+2);
	rep(i,1,n) T.add(i+m,1);
	for(int i=m;i>=1;--i){
		int x=read();
		l[x]=1;
		int pl=pos[x];
		int num=T.ask(pl);
		r[x]=max(r[x], num);
		T.add(pl,-1);
		pos[x]=i;
		T.add(i, 1);
	}
	for(int i=1;i<=n;++i){
		int pl=pos[i];
		int num=T.ask(pl);
		r[i]=max(r[i], num);
	}
	rep(i,1,n) printf("%d %d\n",l[i],r[i]);
}