icontofig | 发布于 2017-01-15 14:31:30 | 阅读量 188 | 整体二分 线段树
发布于 2017-01-15 14:31:30 | 整体二分 线段树

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M 接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3

Sample Output

1 2 1

HINT

【样例说明】第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。
N,M<=50000,N,M<=50000a<=b<=N1 操作中abs(c)<=N2操作中c<=Maxlongint

题解

二分:当遇到的操作是询问操作时,查询线段树里的当前区间,并将当前区间所包含的数的个数as与查询的第k大相比较,如果小于k,那么把当前询问分到左边去,并统计影响k-=as,反之,将它分到右边;当遇到的操作是加入操作时,把要加入的数和mid比较,如果大于mid,那么就把当前操作统计进去,而且当前操作会对右边产生影响,所以要分到右边去,虽然对左边也有影响,但在处理询问时已经处理,就不用考虑了。
数的统计:线段树维护,记录每个区间当前有多少个大于mid的数,“加入”操作里的“统计进去”即是更新当前区间的数的个数(注:不要把线段树的区间和上面把操作分到左右区间混淆,这是不相干的概念,上面分到左右只是为了维护整体二分的序列的有序性)
每次操作完,都要以区间序号为关键字重新排序。
细节:线段树维护时,要考虑线段树每一次二分时,之前的标记等都是不能再使用的,所以要重置,但因为数组过大,如果每一次memset,必然TLE。所以设一个标记数组,每次pushdown前,都要判断当前点的标记是否是1,若是1,把当前点置0,并把当前点的左右儿子重置。这样,每次二分重置时,只用重置根节点即可。
数据范围过大,可能超int。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return(flag ? -1 : 1) * num;
}
const int maxn = 50010;
struct cdq{
    int opt,l,r,k,num,sum;
}a[maxn];
struct sgt{
    int l,r;
    ll delta,val;
    bool p;
}tr[maxn<<2];
ll ans[maxn];
int n,m;
bool cmp(cdq a,cdq b){
    return a.sum < b.sum;
}
void push_up(int now){
    tr[now].val = tr[now<<1].val + tr[now<<1|1].val;
    return;
}
void push_down(int now){
    if(tr[now].p && tr[now].l != tr[now].r){
        tr[now<<1].val = tr[now<<1|1].val = 0;
        tr[now<<1].delta = tr[now<<1|1].delta = 0;
        tr[now<<1].p = tr[now<<1|1].p = 1;
        tr[now].p = 0;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(tr[now].delta != 0 && tr[now].l != tr[now].r){
        tr[now<<1].val += (mid - tr[now].l + 1) * tr[now].delta;
        tr[now<<1|1].val += (tr[now].r - mid) * tr[now].delta;
        tr[now<<1].delta += tr[now].delta;
        tr[now<<1|1].delta += tr[now].delta;
        tr[now].delta = 0;
    }
}
void update(int now,int l,int r,int k){
    push_down(now);
    if(l <= tr[now].l && tr[now].r <= r){
        tr[now].val += k * (tr[now].r - tr[now].l + 1);
        tr[now].delta += k;
        return;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(l <= mid)update(now<<1,l,r,k);
    if(r > mid)update(now<<1|1,l,r,k);
    push_up(now);
    return;
}
ll query(int now,int l,int r){
    push_down(now);
    if(l <= tr[now].l && tr[now].r <= r)
        return tr[now].val;
    ll ans1 = 0;
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(l <= mid)ans1 += query(now<<1,l,r);
    if(r > mid)ans1 += query(now<<1|1,l,r);
    return ans1;
}
void build(int now,int l,int r){
    tr[now].l = l;
    tr[now].r = r;
    tr[now].val = tr[now].delta = 0;
    tr[now].p = 0;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
}
void cdq1(int l,int r,int x,int y){
    if(l == r){
        for(int i = x;i <= y;++i)
            if(a[i].opt == 2)ans[a[i].num] = l;
        return;
    }
    int mid = (l + r) >> 1,xl,xr;
    tr[1].delta = tr[1].val = 0;
    tr[1].p = 1;
    xl = 0;xr = y - x + 1;
    for(int i = x;i <= y;++i){
        if(a[i].opt == 1){
            if(a[i].k <= mid)a[i].sum = ++xl;
            else{
                update(1,a[i].l,a[i].r,1);
                a[i].sum = ++xr;
            }
        }
        else{
            ll as = query(1,a[i].l,a[i].r);
            if(as < a[i].k){
                a[i].sum = ++xl;
                a[i].k -= as;
            }
            else a[i].sum = ++xr;
        }
    }
    sort(a + x,a + y + 1,cmp);
    cdq1(l,mid,x,x + xl - 1);
    cdq1(mid + 1,r,x + xl,y);
}
int main(){
    n = get_num();
    m = get_num();
    for(int i = 1;i <= m;++i){
        a[i].opt = get_num();
        a[i].l = get_num();
        a[i].r = get_num();
        a[i].k = get_num();
        a[i].num = i;
    }
    build(1,1,n);
    cdq1(0,n,1,m);
    for(int i = 1;i <= m;++i)
        if(ans[i])printf("%lld\n",ans[i]);
    return 0;
}
​

 


内容更新于: 2017-01-15 14:31:40
链接地址: http://blog.leanote.com/post/icontofig/6b38ca0642a1

上一篇: bzoj 2683 简单题【CDQ分治+树状数组】

下一篇: 【BZOJ3507【CQOI】通配符匹配DP+Hash

188 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航