3524: [Poi2014]Couriers
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 869 Solved: 286
[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
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
Sample Output
1
0
3
0
4
0
3
0
4
HINT
【数据范围】
n,m≤500000
Source
主席树模板。。。好像又叫什么可持久化线段树。。函数式线段树。。。为什么一个数据结构有这么多的名字。。。#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
struct Tree{int ls,rs,val;} tree[10000010];
int rt[N],x,y,n,m,treesize;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Insert(int l,int r,int x,int &y,int val){
y = ++treesize;
tree[y].val = tree[x].val+1;
if (l==r) return;
tree[y].ls = tree[x].ls;tree[y].rs = tree[x].rs;
int mid = (l+r)>>1;
if (val<=mid) Insert(l,mid,tree[x].ls,tree[y].ls,val);
else Insert(mid+1,r,tree[x].rs,tree[y].rs,val);
}
int Query(int l,int r){
int L = 1,R = n,nd = (r-l+1)>>1;
int x = rt[l-1],y = rt[r];
while (L!=R){
if (tree[y].val-tree[x].val<=nd) return 0;
int mid = (L+R)>>1;
if (tree[tree[y].ls].val-tree[tree[x].ls].val>nd) {R = mid;x = tree[x].ls;y = tree[y].ls;}
else if (tree[tree[y].rs].val-tree[tree[x].rs].val>nd) {L = mid+1;x = tree[x].rs;y = tree[y].rs;}
else return 0;
}
return L;
}
int main(){
n = read();m = read();
for (int i=1;i<=n;i++){x = read();Insert(1,n,rt[i-1],rt[i],x);}
for (int i=1;i<=m;i++){
x = read();y = read();
printf("%d\n",Query(x,y));
}
}
评论 (0)
