BZOJ 3524: [Poi2014]Couriers
正文索引 [隐藏]
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
3
4
HINT
【数据范围】
n,m≤500000
题解
这题就是可持久化线段树辣！把同构的两颗线段树做差就可以计算区间问题了！
我觉得难点在空间、、我一开始记录了左右区间，要么编译爆掉，要么Re、、
后来就写了个不记录左右区间的，才过、、这真是、、、可怕、、
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<cstdio> using namespace std; const int Maxn=500010; int root[Maxn+5]; int num[Maxn]; struct Btree{ int lx,rx; int sum; Btree(){lx=rx=sum=0;} }; Btree tree[Maxn*20]; int nume; void insert(int &x,int y,int left,int right,int pos){ x=++nume; tree[x].sum=tree[y].sum+1; if (left==right){ //Nothing >.< }else{ tree[x].lx=tree[y].lx; tree[x].rx=tree[y].rx; int mid=(left+right)/2; if (pos<=mid)insert(tree[x].lx,tree[y].lx,left,mid,pos); if (mid<pos) insert(tree[x].rx,tree[y].rx,mid+1,right,pos); } } int query(int x,int y,int left,int right,int limi){ //printf("Limi %d\nSum %d %d=>%d\n",limi,left,right,tree[x].sum-tree[y].sum); if (tree[x].sum-tree[y].sum<=limi) return 0; if (left==right) return left; int mid=(left+right)/2; //printf("Sum %d %d=>%d\n",left,mid,tree[tree[x].lx].sum-tree[tree[y].lx].sum); //printf("Sum %d %d=>%d\n",mid+1,right,tree[tree[x].rx].sum-tree[tree[y].rx].sum); if (tree[tree[x].lx].sum-tree[tree[y].lx].sum>limi) return query(tree[x].lx,tree[y].lx,left,mid,limi); if (tree[tree[x].rx].sum-tree[tree[y].rx].sum>limi) return query(tree[x].rx,tree[y].rx,mid+1,right,limi); return 0; } int n,m; int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&num[i]); for (int i=1;i<=n;i++){ insert(root[i],root[i-1],1,n,num[i]); } for (int i=1;i<=m;i++){ int l,r; scanf("%d%d",&l,&r); //printf("Query=>%d-%d\n",l,r); printf("%d\n",query(root[r],root[l-1],1,n,(r-l+1)/2)); } return 0; } |
双倍经验 => BZOJ 2223
原文链接：BZOJ 3524: [Poi2014]Couriers
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!