zoj 3633 Alice's present
10473 단어 ICE
두 가지 해법:
자신의 해법 은 당시 visit 배열 10 을 여 는 31 자가 너무 크다 는 점 을 고려 해 먼저 주어진 수 를 분 산 된 다음 범위 내 에 있 는 모든 수 와 그 가 있 는 배열 의 아래 표 시 를 연결 하 는 것 이다.
물 어 볼 때 조회 범 위 를 옮 겨 다 니 며 모든 숫자 에 대해 이 숫자 가 연 결 된 변 에 이 숫자 가 표시 되 어 있 고 조회 범위 내 에 있 으 면 이 수 를 출력 하면 됩 니 다.
**********시작 할 때 ok 은 소문 자로 만 들 었 고 와 는 피 를 토 할 때 까지...
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#define maxn 500100
using namespace std;
struct node0
{
long long key;
int id;
}node[maxn];
vector<int>line[maxn];
int n;
int m;
long long number[maxn];
bool cmp1(struct node0 a,struct node0 b)
{
return a.key<b.key;
}
bool cmp2(struct node0 a,struct node0 b)
{
return a.id<b.id;
}
int main()
{
long long max;
while(cin>>n)
{
memset(number,0,sizeof(number));
memset(node,0,sizeof(node));
for(int i=0;i<=n;i++)
line[i].clear();
for(int i=0;i<n;i++)
{
cin>>node[i].key;
number[i]=node[i].key;
node[i].id=i;
}
sort(node,node+n,cmp1);//
//
int temp=node[0].key;
node[0].key=0;
line[0].push_back(node[0].id);
for(int i=1;i<n;i++)
{
if(node[i].key==temp)
node[i].key=node[i-1].key,line[node[i].key].push_back(node[i].id);//
else
temp=node[i].key,node[i].key=node[i-1].key+1,line[node[i].key].push_back(node[i].id);//
}
sort(node,node+n,cmp2);// 。
cin>>m;
while(m--)
{
int st,en;
int flage=0;
cin>>st>>en;
int id;
for(int i=en-1;i>=st-1;i--)
{
for(int j=0;j<line[node[i].key].size();j++)
{
if(line[node[i].key][j]>=i+1&&line[node[i].key][j]<=en-1)//
if(line[node[i].key][j]!=i)
{
flage=1;id=i;break;
}
}
if(flage)break;
}
if(flage)
cout<<number[id]<<endl;
else
cout<<"OK"<<endl;
}
cout<<endl;
}
return 0;
}
인터넷 에 떠 도 는 방법 은 선분 나무 입 니 다.생각해 보 니 자신 도 그 당시 에 생각 하지 못 했 습 니 다.이 숫자 를 얻 기 전에 그 와 같은 수의 하 표를 얻 었 습 니 다.온라인 세그먼트 트 리 에 maxd 속성 을 추가 하면 현재 구간 의 모든 수 중 하나 가 있 고 이 수의 것 과 같 으 며 이 수의 앞 에 있 는 아래 표 시 는 이 구간 의 다른 수의 이 속성 보다 크다 는 것 을 나타 낸다.
그리고 나 면 됩 니 다.되 돌아 오 는 아래 표 가 구간 내 에 있 는 지 아 닌 지 를 판단 해 야 합 니 다.
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <vector>
#include<map>
#define maxn 500100
using namespace std;
int visit[100];
struct node0
{
int l;
int r;
int maxd;
}node[maxn];
int dis[maxn];
int number[maxn];
void build(int root,int l,int r)
{
node[root].l=l;
node[root].r=r;
if(l==r)
{
node[root].maxd=dis[l];
return ;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
node[root].maxd=max(node[root<<1].maxd,node[root<<1|1].maxd);
return ;
}
int query(int root,int l,int r)
{
//cout<<root<<" "<<node[root].l<<" "<<node[root].r<<" "<<node[root].maxd<<endl;
if(node[root].l==l&&node[root].r==r)
return node[root].maxd;
//if(l==r)return 0;
int mid=(node[root].l+node[root].r)>>1;
if(r<=mid)
return query(root<<1,l,r);
else
if(l>mid)
return query(root<<1|1,l,r);
else
{
return max(query(root<<1,l,mid),query(root<<1|1,mid+1,r));
}
}
void output(int root)
{
if(!visit[root]);
cout<<node[root].l<<" "<<node[root].r<<" "<<node[root].maxd<<" "<<root<<endl;;
visit[root]=1;
if(node[root].l==node[root].r)return ;
output(root<<1);
output(root<<1|1);
}
int main()
{
int n,m;
int st,en;
while(cin>>n)
{
map<long long,int>v;
for(int i=1;i<=n;i++)
{
cin>>number[i];
dis[i]=v[number[i]];
v[number[i]]=i;
}
build(1,1,n);
// output(1);
cin>>m;
while(m--)
{
cin>>st>>en;
int temp=query(1,st,en);
if(temp>=st&&temp<=en)
cout<<number[temp]<<endl;
else
cout<<"ok"<<endl;
}
cout<<endl;
}
return 0;
}라인 트 리 는 자기 것 보다 빨 라 요.
좋은 웹페이지 즐겨찾기
