fzu 1656 How many different numbers(线段树)

时间:2022-12-17 09:19:05

题意:询问不同区间不同值的个数

//思路1 700+ms
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define CL(a,b) memset(a,b,sizeof(a))
const int M(100010);
const int N(1020);
int f[N],r[M];
struct data{
	int x,sub;
}a[M];
struct dat{
	int l,r;
	int sub;
}ans[N];
int vis[M];
bool cmp(data x,data y)
{
	return x.x<y.x;
}
bool cm(dat x,dat y )
{
	return x.l<y.l||(x.l==y.l&&x.r<y.r);
}
int main()
{
	int m,i,n,j,q;
	while(scanf("%d",&m)!=EOF)
	{
		for(i=1;i<=m;i++)
		{
			scanf("%d",&a[i].x);
			a[i].sub=i;
		}
		sort(a+1,a+m+1,cmp);
		r[a[1].sub]=0;
		for(i=2,j=0;i<=m;i++)//离散化
		{
			if(a[i-1].x==a[i].x)
				r[a[i].sub]=j;
			else
			{
				j++;
				r[a[i].sub]=j;
			}
		}
		scanf("%d",&q);
		for(i=0;i<q;i++)
		{
			scanf("%d%d",&ans[i].l,&ans[i].r);
			ans[i].sub=i;
		}
		sort(ans,ans+q,cm);
		CL(f,0); CL(vis,0);//vis记录出现个数
		for(i=0;i<q;i++)
		{
		
			if(i==0)
			{
				CL(vis,0);
				for(j=ans[i].l;j<=ans[i].r;j++)
				{
					if(!vis[r[j]])
						f[ans[i].sub]++;
					vis[r[j]]++;
				}
				continue;
			}	
			if(ans[i].r<ans[i-1].r)
			{
				if((ans[i].l-ans[i-1].l+ans[i-1].r-ans[i].r)>(ans[i].r-ans[i].l))
				{
					CL(vis,0);
					for(j=ans[i].l;j<=ans[i].r;j++)
					{
						if(!vis[r[j]])
							f[ans[i].sub]++;
						vis[r[j]]++;
					}
				}
				else
				{
					f[ans[i].sub]=f[ans[i-1].sub];
					for(j=ans[i-1].l;j<ans[i].l;j++)
					{
						vis[r[j]]--;
						if(vis[r[j]]==0)
							f[ans[i].sub]--;
					}
					for(j=ans[i].r+1;j<=ans[i-1].r;j++)
					{
						vis[r[j]]--;
						if(vis[r[j]]==0)
							f[ans[i].sub]--;
					}
				}
			}
			else 
			{
				if((ans[i].l-ans[i-1].l)>(ans[i-1].r-ans[i].l))
				{
					CL(vis,0);
					for(j=ans[i].l;j<=ans[i].r;j++)
					{	
						if(!vis[r[j]])
							f[ans[i].sub]++;
						vis[r[j]]++;
					}
				}
				else
				{
					f[ans[i].sub]=f[ans[i-1].sub];
					for(j=ans[i-1].l;j<ans[i].l;j++)
					{
						vis[r[j]]--;
						if(vis[r[j]]==0)
							f[ans[i].sub]--;
					}
					for(j=ans[i-1].r+1;j<=ans[i].r;j++)
					{	
						if(!vis[r[j]])				
							f[ans[i].sub]++;
						vis[r[j]]++;
					}
				}
			}
		}
		for(i=0;i<q;i++)
			printf("%d\n",f[i]);
	}
	
}
//参考: http://blog.csdn.net/sqplfh/article/details/6840996

具体思路:先把N个保存下来,进行离散,然后用就可以用flag记录某个数前面出现的位置,再把询问保存下来,按右端点排序。

对N个数依次处理,删除该数前面出现的,在当前位置插入该数。当处理到第i个位置的数,且询问的右端点也为i是,统计个数。

// 300+ms 线段树优化
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define CL(a,b) memset(a,b,sizeof(a))
#define MID(a,b) (a+b)>>1
const int M(100010);
const int N(1020);
int tree[M<<2],r[M],f[N];
struct data{
	int x,sub;
}a[M];
struct dat{
	int l,r;
	int sub;
}ans[N];
int vis[M];
bool cmp(data x,data y)
{
	return x.x<y.x;
}
bool cm(dat x,dat y )
{
	return x.r<y.r;
}
inline void pushup(int t)
{
	tree[t]=tree[t<<1]+tree[t<<1|1];
}
void insert(int t,int x,int val,int l,int r)
{
	if(l==r)
	{
		tree[t]=val;
		return;
	}
	int mid=MID(l,r);
	if(x<=mid)
		insert(t<<1,x,val,l,mid);
	if(x>mid)
		insert(t<<1|1,x,val,mid+1,r);
	pushup(t);
}
int query(int t,int ql,int qr,int l,int r)
{
	if(ql<=l&&qr>=r)
		return tree[t];
	int mid=MID(l,r);
	if(qr<=mid)
		return query(t<<1,ql,qr,l,mid);
	else if(ql>mid)
		return query(t<<1|1,ql,qr,mid+1,r);
	else
		return query(t<<1,ql,qr,l,mid)+query(t<<1|1,ql,qr,mid+1,r);
}
int main()
{
	int m,i,n,j,q;
	while(scanf("%d",&m)!=EOF)
	{
		for(i=1;i<=m;i++)
		{
			scanf("%d",&a[i].x);
			a[i].sub=i;
		}
		sort(a+1,a+m+1,cmp);
		r[a[1].sub]=0;
		for(i=2,j=0;i<=m;i++)
		{
			if(a[i-1].x==a[i].x)
				r[a[i].sub]=j;
			else
			{
				j++;
				r[a[i].sub]=j;
			}
		}
		scanf("%d",&q);
		for(i=0;i<q;i++)
		{
			scanf("%d%d",&ans[i].l,&ans[i].r);
			ans[i].sub=i;
		}
		sort(ans,ans+q,cm);
		CL(vis,-1); CL(tree,0);
		for(i=1,j=0;i<=m&&j<q;i++)
		{
			if(vis[r[i]]!=-1)
			{
				insert(1,vis[r[i]],0,1,m);
			}
			insert(1,i,1,1,m);
			vis[r[i]]=i;
			while(i==ans[j].r)
			{
				f[ans[j].sub]=query(1,ans[j].l,ans[j].r,1,m);
				j++;
				//printf("%d\n",tree[1]);
			}
			
		}
		for(i=0;i<q;i++)
			printf("%d\n",f[i]);
	}
	
}