Codeforces Educational Codeforces Round 80 (Rated for Div. 2) E - Messenger Simulator（树状数组+思维）

题意：给定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]);
}