从昨天到今天。。。。
我不明白。。为什么一直错。。。我现在还是不明白。。
这是我写这类问题。。似乎都会出现的问题。。要把数组开单很多很多倍。。我到现在还是不明白这是为什么
还是第一次能在第一页的呢。。呵呵。。小安慰一下
#include<iostream>
#include<algorithm>
#define MaxN 300005
#define MaxM 200005
using namespace std;
int N,M,res[MaxM];
struct node
{
int pri,n;
friend bool operator<(node a,node b)
{
return a.pri<b.pri;
}
}index[MaxN],ii[MaxN];
struct line
{
int b,e,k,n,ans;
friend bool operator<(line a,line b)
{
return a.b<b.b;
}
}Line[MaxM];
int cc[MaxN];
void inser_del(int key,int flag)
{
int L=0,R=N-1,mid,v=1;
while(L<R)
{
cc[v]+=flag;
mid=(L+R)/2;
v*=2;
if(key<=mid)
R=mid;
else
{
v++;
L=mid+1;
}
}
cc[v]+=flag;
}
int solve(int k)
{
int L=0,R=N-1,mid,v=1;
while(L<R)
{
mid=(L+R)/2;
if(cc[2*v]>=k)
{
R=mid;
v*=2;
}
else
{
L=mid+1;
k-=cc[2*v];
v=2*v+1;
}
}
return index[L].pri;
}
int main()
{
int i,j;
scanf("%d%d",&N,&M);
for(i=0;i<N;index[i].n=i++)
scanf("%d",&index[i].pri);
for(i=0;i<M;Line[i].n=i++)
{
scanf("%d%d%d",&Line[i].b,&Line[i].e,&Line[i].k);
if(Line[i].b>Line[i].e)swap(Line[i].b,Line[i].e);
--Line[i].b;
--Line[i].e;
}
//初始化-->cc为0
sort(index,index+N);
sort(Line,Line+M);
for(i=0;i<N;i++)
{
ii[index[i].n].pri=index[i].pri;
ii[index[i].n].n=i;
}
for(i=Line[0].b;i<=Line[0].e;i++)
inser_del(ii[i].n,1);
for(i=1;i<M;i++)
{
Line[i-1].ans=solve(Line[i-1].k);
if(Line[i - 1 ].e>=Line[i].b)
{for (j = Line[i - 1 ].b; j < Line[i].b; j ++ )
inser_del(ii[j].n,-1);
for (j = Line[i - 1 ].e + 1 ; j <= Line[i].e; j ++ )
inser_del(ii[j].n,1);
}
else
{
for(j=Line[i - 1].b;j<=Line[i - 1 ].e;j ++ )
inser_del(ii[j].n,-1);
for (j = Line[i].b; j <= Line[i].e; j ++ )
inser_del(ii[j].n,1);
}
}
Line[i-1].ans=solve(Line[i-1].k);
for(i=0;i<M;i++)
res[Line[i].n]=Line[i].ans;
for(i=0;i<M;i++)
printf("%d\n",res[i]);
return 0;
}
posted on 2008-07-15 13:46
zoyi 阅读(374)
评论(0) 编辑 收藏 引用 所属分类:
acm 、
数据结构