POJ 2104 区划树学习基础题

POJ 2104 划分树学习基础题

题意：给出n个数字，和m次询问，每次询问区间【a,b】中第k大的数字，并且输出。

这里用到了一种数据结构，划分树。

划分树指的是，每一个节点保存区间[l,r]所有元素，元素排列顺序与原数组相同，但是两个子树的元素为该节点所有元素排序后前(r-l+1)/2个进入左子树，其余的到右子树，同时维护一个sum域，sum[i]表示l--i这些点中有多少个进入了左子树。

关于其查找，在[l,r]区间内，查找第k大数，t是该节点，tree[t].l,tree[t].r是该节点的左右区间。mid是区间中值。

1、sum[r]-sum[l-1]>=k，查找LL(t),区间对应为[ tree[t].l+sum[l-1] , tree[t].l+sum[r]-1 ]
2、sum[r]-sum[l-1]<k,查找RR(t)，区间对应为[ mid+1+l-tree[t].l-sum[l-1] , mid+1+r-tree[t].l-sum[r] ]

具体见代码

#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <vector>#include <stack>#include <map>#include <iomanip>#define PI acos(-1.0)#define Max 100005#define inf 1<<28#define LL(x) (x<<1)#define RR(x) (x<<1|1)#define FOR(i,s,t) for(int i=(s);i<=(t);++i)#define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define mp(a,b) make_pair(a,b)using namespace std;int lessmid[20][Max];//在区间内小于mid值的个数。int seg[20][Max];int num[Max];struct seg_tree{    int l ,r ;} tree[Max*4];void build_tree(int l,int r, int u,int d){    tree[u].l = l, tree[u].r = r;    if(l == r)return ;    int mid = l + r >> 1;    int issame = mid - l + 1;//左边一共可以有多少元素    for (int i = l ; i <= r ; i ++)        if(seg[d][i] < num[mid])//小于中间值的全部放在左边            issame --;//issame-- ,表示这个值可以放在左边，那么左边的剩余总数减少。            //最终issame总数是表示放等于中值的数字的个数。    int lpos = l ,rpos = mid + 1;    for (int i = l ; i <= r ; i ++)    {        if( i == l )            lessmid[d][i] = 0;//lessmid[d][i]记录在第d层,[l,i]之间小于等于中值的数的个数。        else            lessmid[d][i] = lessmid[d][i-1];        if(seg[d][i] < num[mid])        {            lessmid[d][i] ++;//小于中值，计数加            seg[d+1][lpos++] = seg[d][i];//将此数放到左边        }        else if(seg[d][i] > num[mid])        {            seg[d+1][rpos++] = seg[d][i];//同理        }        else//若相等，则需用到上面的issame元素.        {            if(issame > 0)//如果issame > 0 ，那么左边还没放满，则可以将等于中值的数放到左边。            {                issame --;                lessmid[d][i]++;//这里加的就是等于中值的个数。                seg[d+1][lpos++] = seg[d][i];            }            else                seg[d+1][rpos++] = seg[d][i];        }    }    build_tree(l,mid,LL(u),d+1);    build_tree(mid+1,r,RR(u),d+1);}int update(int l,int r,int u,int d,int cnt){    if(l == r)return seg[d][l];    int num1 ,num2;    if(l == tree[u].l)    {        num1 = lessmid[d][r];        num2 = 0;    }    else    {        num1 = lessmid[d][r] - lessmid[d][l-1];//[l,r]的小于等于中值的个数，放到左边        num2 = lessmid[d][l-1];//[tree[u].l,l-1]的小于等于中值的个数,放到左边    }    if(num1 >= cnt)    {        return update(tree[u].l + num2,tree[u].l + num1 + num2 - 1,LL(u),d+1,cnt);    }    else    {        int mid = tree[u].l + tree[u].r >> 1;        int num4 = l - tree[u].l - num2;//[tree[u].l , l - 1]放到右边的总数。        int num3 = r - l + 1- num1 ;//[l,r]放到右边的总数。        return update(mid + num4 + 1 , mid + num3 +num4 ,RR(u),d+1 ,cnt - num1);    }}int main(){    int n , m ;    cin >> n >> m ;    for (int i = 1 ; i <= n ; i ++)    {        scanf("%d",&num[i]);        seg[1][i] = num[i];    }    sort(num + 1,num + n + 1 );    build_tree(1,n,1,1);    while(m --)    {        int a, b ,c;        scanf("%d%d%d",&a,&b,&c);        printf("%d\n",update(a,b,1,1,c));    }    return 0;}