#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100001
vector<int>sp;
int a[MAXN];
int res[50001];
struct seg
{
	int s,t;
	int k;
	int ind;
}se[50001];
bool cmp(seg aa,seg bb)
{
	return aa.s<bb.s || aa.s==bb.s && aa.t<bb.t;
}
void vpop(int x)// 2分找到并删除
{
	int sta=0,end=sp.size()-1,mid=0;
	while(sta<=end)
	{
		mid=(sta+end)/2;
		if(x>sp[mid]) sta=mid+1;
		else if(x<sp[mid]) end=mid-1;
		else sp.erase(sp.begin()+mid);
	}
}
void vpush(int x)//2分插入
{
	int sta=0,end=sp.size()-1,mid=0;
	while(sta<=end)
	{
		mid=(sta+end)/2;
		if(x>sp[mid]) sta=mid+1;
		if(x<sp[mid]) end=mid-1;
	}
	sp.insert(sp.begin()+mid+1,x);
}
void out(void)
{
	register int i;
	for(i=0;i<sp.size();i++)
		printf("%2d",sp[i]);
	printf("\n");
}
int main()
{
	register int i,j;
	int n,m;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",a+i);
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&se[i].s,&se[i].t,&se[i].k);
		se[i].ind=i;
	}
	sort(se,se+m,cmp);
	for(i=se[0].s;i<=se[0].t;i++)
		sp.push_back(a[i]);
	sort(sp.begin(),sp.end());
	res[se[0].ind]=sp[se[0].k-1];
	//out();
	for(i=1;i<m;i++)
	{
		if(se[i-1].t<se[i].s)
		{
			for(j=se[i-1].s;j<=se[i-1].t;j++)
			{
				vpop(a[j]);
			//	out();
			}
			for(j=se[i].s;j<=se[i].t;j++)
			{
				vpush(a[j]);
			//	out();
			}
		}
		else
		{
			for(j=se[i-1].s;j<se[i].s;j++)
			{
				vpop(a[j]);
			//	out();
			}
			for(j=se[i-1].t+1;j<=se[i].t;j++)
			{
				vpush(a[j]);
			//	out();
			}
		}
		res[se[i].ind]=sp[se[i].k-1];	
	}
	for(i=0;i<m;i++)
		printf("%d\n",res[i]);
	return 0;
}
		

• 不好意思,改了一点小错误,不过现在还是WA ,继续请大家帮忙!!!!!(内附代码) (1743) elf788544 2006-02-28 18:33:27
  • for循环里面为什么不sort？ (1971) 041221125 2006-02-28 18:44:11
    • Re:for循环里面为什么不sort？ (17) elf788544 2006-02-28 19:25:34
      • Re:for循环里面为什么不sort？ (29) 041221125 2006-02-28 19:37:50
        • 哦，我懂了 (35) 041221125 2006-02-28 19:39:33
          • Re:哦，我懂了 (14) wangyang788544 2006-02-28 19:43:49
            • Re:我正在看…… (18) 041221125 2006-02-28 19:46:03
              • Re:我正在看…… (63) 041221125 2006-02-28 20:02:49
                • 不行不行，tle了 (77) 041221125 2006-02-28 20:25:41
                  • Re:不行不行，tle了 (32) wangyang788544 2006-02-28 20:45:40
                    • 要用平衡树呀，可我一用RBTree就RE，没办法…… (38) 041221125 2006-02-28 20:49:19
                      • Re:要用平衡树呀，可我一用RBTree就RE，没办法…… (17) wangyang788544 2006-02-28 20:50:30
                        • 但是插入时要移动数据，这是O（n）的 (21) 041221125 2006-02-28 21:07:25
  • 我改了然后RE (1971) 041221125 2006-02-28 18:47:25
• Re:请大家帮忙看看2761，我用的2分插入和删除,为什么老是WA呢?(内附代码) (1865) elf788544 2006-02-28 19:36:07