Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:我想自杀...写了N天,居然是如此之小的一个错误...离散化+树状数组,果然是名不虚传~

Posted by superDD at 2009-09-14 22:51:05 on Problem 2761
In Reply To:我想自杀...写了N天,居然是如此之小的一个错误...离散化+树状数组,果然是名不虚传~ Posted by:DestinyDesigner at 2009-09-14 10:58:22
我也离散化+树状数组+二分查找,复杂度2*n*logn+m*logn*logn的。。tle了。。。



#include<iostream>
#include<algorithm>
using namespace std;
int a[100006],sum[100006];
int index[100006];
int data[100006];
struct interval
{
	int l,r,k;
}in[50005];
inline bool operator<(const interval &a,const interval &b)
{
	return a.l!=b.l?a.l<b.l:a.r<=b.r;
}
inline int lowbit(int t)
{
	return t&(-t);
}
void update(int i,int s,int ind)
{
	while(i<=ind)
	{
		sum[i]+=s;
		i+=lowbit(i);
	}
	return ;
}
int getsum(int i)
{
	int ans=0;
	while(i>=1)
	{
		ans+=sum[i];
		i-=lowbit(i);
	}
	return ans;
}
int find(int d,int ind)
{
	int left=1,right=ind,mid;
	if(index[left]==d)
		return left;
	if(index[right]==d)
		return right;
	while(1)
	{
		mid=(left+right)>>1;
		if(index[mid]==d)
			break;
		if(index[mid]>d)
			right=mid;
		else
			left=mid;
	}
	return mid;
}
int process(int k,int ind)
{
	int left=1,right=ind,mid;
	int p;
	p=getsum(left);
	if(a[left]&&p>=k&&p-a[left]<=k)
		return left;
	p=getsum(right);
	if(a[right]&&p>=k&&p-a[right]<=k)
		return right;
	while(1)
	{
		mid=(left+right)>>1;
		p=getsum(mid);
		if(a[mid]&&p>=k&&p-a[mid]<=k)
			break;
		if(p>=k)
			right=mid;
		else 
			left=mid;
	}
	return mid;
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",data+i);
		memcpy(index,data,sizeof(data));
		memset(a,0,sizeof(a));
		memset(sum,0,sizeof(sum));
		sort(index+1,index+1+n);
		int ind=1;
		for(int i=1;i<n;i++)
			if(index[i]!=index[i+1])
				index[ind++]=index[i];
		index[ind]=index[n];

		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&in[i].l,&in[i].r,&in[i].k);
		sort(in+1,in+1+m);
		int ttt=0;
		for(int i=in[1].l;i<=in[1].r;i++)
		{
			int p=find(data[i],ind);
			update(p,1,ind);
			a[p]++;
			ttt=max(ttt,p);
		}
		for(int i=1;i<=m;i++)
		{
			if(i!=1)
			{
				int s=min(in[i].l,in[i-1].r);
				s+=(s==in[i-1].r?1:0);
				for(int j=in[i-1].l;j<s;j++)
				{
					int p=find(data[j],ind);
					update(p,-1,ind);
					a[p]--;
				}
				int t=max(in[i].l,in[i-1].r);
				for(int j=t+(t==in[i-1].r?1:0);j<=in[i].r;j++)
				{
					int p=find(data[j],ind);
					update(p,1,ind);
					a[p]++;
					ttt=max(ttt,p);
				}
			}
			printf("%d\n",index[process(in[i].k,ttt)]);
		}
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator