额额额~主席树

标签：额额额 cnt int 个数 sum tr 区间 主席

题意：

给定一个长度为n的序列和一个正整数m，有若干个询问，每次询问一个区间[l, r]，请问区间是否存在k个数的和 >= m。

写的时候：没注意到是不用连续的k个数，用前缀和写样例过了，但是后面的测试有错 正解： 要使区间内满足k个数>=m，我们只需要挑出最大的k的数即可。如何维护区间最大k个数呢？这不是主席树的板子嘛！不了解板子的可以看这篇 [https://zhuanlan.zhihu.com/p/558921818](https://zhuanlan.zhihu.com/p/558921818)

struct Node
{
    int l, r;
    int cnt;
    int sum;
}tr[N << 5];
int n, m, idx , root[N], a[N], k, x;

void pushup(int u)
{
    tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}

void insert(int &u, int v, int l, int r, int x)
{
    u = ++ idx;
    tr[u] = tr[v];
    tr[u].cnt ++ ;
    tr[u].sum += x;
    if(l == r) return ;
    int mid = l + r >> 1;
    if(x <= mid) insert(tr[u].l, tr[v].l, l, mid, x);
    else insert(tr[u].r, tr[v].r, mid + 1, r, x);
    pushup(u);
}

int query(int p, int q, int l, int r, int k)
{
    if(l == r) return l;
    int cnt = tr[tr[q].r].cnt - tr[tr[p].r].cnt;
    int mid = l + r >> 1;
    if(k <= cnt) return query(tr[p].r, tr[q].r, mid + 1, r, k);
    if(k > cnt) return tr[tr[q].r].sum - tr[tr[p].r].sum + query(tr[p].l, tr[q].l, l, mid, k - cnt);
}

int main()
{
    cin >> n >> m >> k >> x;
    for(int i = 1 ; i <= n ; i ++ )
    {
        cin >> a[i];
        insert(root[i], root[i - 1], 0, INF, a[i]);
    }
    
    for(int i = 1 ; i <= m ; i ++ )
    {
        int l, r;
        cin >> l >> r;
        cout << (query(root[l - 1], root[r], 0, INF, k) >= x ? "Y" : "N") << endl;
    }
    
    return 0;
}

标签：额额额,cnt,int,个数,sum,tr,区间,主席
From： https://www.cnblogs.com/win-dy/p/16640206.html