K大数查询

pikabi · 2020-09-29 16:12:34 · 个人记录

权值线段树套线段树

和其他的差不多，套一下就好了（k 大数要往右边跑不要忘了，一开始打成 k 小数了……）。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cctype>
#define ll long long
#define inf 1023456789

using namespace std;

inline ll read(){
    ll x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}

const int N = 50000;
int n, m, rt[500005], tot; 

struct Segment_Tree{
    ll val, tag;
    int l, r;
}a[20000005];

inline int ls(int p){
    return p << 1;
}

inline int rs(int p){
    return p << 1 | 1;
}

inline void update(int p){
    a[p].val = a[a[p].l ].val + a[a[p].r ].val ;
}

inline void push_up(int &p, int l, int r, ll val){
    if(!p) p = ++tot;
    a[p].val += val * (1ll * r - l + 1);
    a[p].tag += val ;
}

inline void push_down(int p, int l, int r){
    if(!a[p].tag ) return ;
    int mid = l + r >> 1;
    push_up(a[p].l, l, mid, a[p].tag );
    push_up(a[p].r, mid + 1, r, a[p].tag );
    a[p].tag = 0;
}
inline void modify(int &p, int l, int r, int L, int R){
    if(!p) p = ++tot;
//  printf("%d %d %d\n",l, r, p);
    if(L <= l && r <= R){
        a[p].val += 1ll * (r - l + 1);
        a[p].tag ++;
//      printf("%d %d %d\n",l, r, a[p].val );
        return ;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    if(L <= mid) modify(a[p].l ,l, mid, L, R);
    if(mid < R) modify(a[p].r ,mid + 1, r, L, R);
    update(p);
//  printf("%d %d %d\n",l, r, a[p].val );
}

inline ll query(int p, int l, int r, int L, int R){
//  printf("%d %d %d\n",l, r, p);
    if(!p) return 0;
    if(L <= l && r <= R){
//      printf("%d %d %lld\n",l, r, a[p].val );
        return a[p].val ;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    ll res = 0;
    if(L <= mid) res += query(a[p].l , l, mid, L, R);
    if(mid < R) res += query(a[p].r , mid + 1, r, L, R);
    update(p);
    return res;
}

inline void tre_modify(int p, int l, int r, int k, int L, int R){
//  printf("%d %d %d  : ",p, l, r);
    modify(rt[p], 1, n, L, R);
//  printf("%lld\n",rt[p]);
    if(l == r){
        return ;
    }
    int mid = l + r >> 1;
    if(k <= mid) tre_modify(ls(p), l, mid, k, L, R);
    else tre_modify(rs(p), mid + 1, r, k, L, R);
}

int ans;

inline void tre_query(int p, int l, int r, ll k, int L, int R){
    if(l == r){
        ans = l;
        return ;
    }
    int mid = l + r >> 1;
    ll res = query(rt[rs(p)], 1, n, L, R);
//  printf("\n\n%d %d %d %lld\n",ls(p), l, r, res);
    if(res < k) tre_query(ls(p) , l, mid, k - res, L, R);
    else tre_query(rs(p), mid + 1, r, k, L, R);
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= m; i++){
        int opt = read(), x = read(), y = read(), z = read();
        if(opt == 1){
            tre_modify(1, 1, n, z, x, y);
        }
        else {
            tre_query(1, 1, n, z, x, y);
            printf("%d\n",ans);
        }
    }
    return 0;
}