3524: [Poi2014]Couriers
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 899 Solved: 300
[Submit][Status][Discuss]
Description
给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。
Input
第一行两个数n，m。
第二行n个数，a[i]。
接下来m行，每行两个数l,r，表示询问[l,r]这个区间。
Output
m行，每行对应一个答案。
Sample Input
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
Sample Output
1
0
3
0
4
HINT
【数据范围】
n,m≤500000
Source
一道裸的可持久化线段树。询问时，如果左儿子的区间数字出现数大于(r-l+1)/2，那么右儿子的的区间数字出现数不会达到(r-l+1)/2，因此也不存在数出现数大于(r-l+1)/2，所以只要去访问左儿子就可以了，同理，如果右儿子的区间数字出现数大于(r-l+1)/2，就去访问右儿子，如果两者都不满足，就返回0。
解决啦！！
代码：
/**************************************************************
Problem: 3524
User: yeweining
Language: C++
Result: Accepted
Time:6248 ms
Memory:121900 kb
****************************************************************/
#include<cstdio>
using namespace std;
int n,m,a[500010],root[500010],l,r,cnt,tmp;
struct node{int l,r,sum;}tr[10000010];
void change(int l,int r,int &p,int x)
{
tr[++cnt]=tr[p];p=cnt;tr[p].sum++;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) change(l,mid,tr[p].l,x);else change(mid+1,r,tr[p].r,x);
}
int ask(int l,int r,int p1,int p2)
{
if (l==r) return l;
int mid=(l+r)>>1;
if (tr[tr[p2].l].sum-tr[tr[p1].l].sum>tmp) return ask(l,mid,tr[p1].l,tr[p2].l);else
if (tr[tr[p2].r].sum-tr[tr[p1].r].sum>tmp) return ask(mid+1,r,tr[p1].r,tr[p2].r);else return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
{
root[i]=root[i-1];
change(1,n,root[i],a[i]);
}
while (m--)
{
scanf("%d%d",&l,&r);
tmp=(r-l+1)>>1;
printf("%d\n",ask(1,n,root[l-1],root[r]));
}
}
评论 (0)
