C++之路进阶——bzoj3524（Couriers）

F.A.Qs	Home	Discuss	ProblemSet	Status	Ranklist	Contest	ModifyUser gryz2016	Logout	捐赠本站

Notice:由于本OJ建立在Linux平台下，而许多题的数据在Windows下制作，请注意输入、输出语句及数据类型及范围，避免无谓的RE出现。

3524: [Poi2014]Couriers

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 1058 Solved: 363
[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

代码：

 1 #include<cstdio>
 2 #include<iostream>
 3  
 4 using namespace std;
 5  
 6 int n,m,sz;
 7 int root[500010],ls[10000010],rs[10000010],sum[10000010];
 8  
 9 void update(int l,int r,int x,int &y,int v)
10 {
11     y=++sz;
12     sum[y]=sum[x]+1;
13     if(l==r)return;
14     ls[y]=ls[x];
15     rs[y]=rs[x];
16     int mid=(l+r)>>1;
17     if(v<=mid) update(l,mid,ls[x],ls[y],v);
18     else update(mid+1,r,rs[x],rs[y],v);
19 }
20  
21 int que(int L,int R)
22  {
23     int l=1,r=n,mid,x,y,tmp=(R-L+1)>>1;
24     x=root[L-1];y=root[R];
25     while(l!=r)
26     {
27         if(sum[y]-sum[x]<=tmp)return 0;
28         mid=(l+r)>>1;
29         if(sum[ls[y]]-sum[ls[x]]>tmp)
30          {
31            r=mid;
32            x=ls[x];
33            y=ls[y];
34           } else
35         if(sum[rs[y]]-sum[rs[x]]>tmp)
36         {
37            l=mid+1;
38            x=rs[x];
39            y=rs[y];
40         }
41         else return 0;
42     }
43     return l;
44  }
45  
46 int main()
47 {
48     scanf("%d%d",&n,&m);
49     for(int i=1;i<=n;i++)
50     {
51         int x;
52         scanf("%d",&x);
53         update(1,n,root[i-1],root[i],x);
54     }
55     for(int i=1;i<=m;i++)
56     {
57         int l,r;
58         scanf("%d%d",&l,&r);
59         printf("%d
",que(l,r));
60     }
61     return 0;
62 }