Codeforces-840D - Destiny(主席树上二分,思维)

题目大意:

给你一个序列,一些查询

每次查询区间[L,R]中出现次数大于T的最小的a[i]是多少

题目思路:

一眼主席树

但是这个题目在于如何用好Codeforces-840D - Destiny(主席树上二分,思维)这个条件

2 ≤ k ≤ 5

假设这个序列长度是1000,k=5

那么就是找出现次数大于200的,但是这样的数字最多有多少个呢?  很明显 

不会超过k个

然后我查询一个区间的数字个数的和的时候,如果小于T,直接退出

然后继续搜下去(这里不会有k<=5的限制,会退出的很快)

这里因为要求最小值

所以每次先搜左边再搜右边

搜到答案直接退出就ok了

CODE:

Codeforces-840D - Destiny(主席树上二分,思维)
ll n, val[maxn], qq, indexx, ans,rt[maxn];
struct node
{
    ll ls, rs, num;
} a[maxn * 32];
void insert(ll pre, ll &now, ll l, ll r, ll pos)
{
    now = ++indexx;
    a[now] = a[pre], a[now].num++;
    if(l == r) return ;
    ll mid = (l + r) >> 1;
    if(pos <= mid) insert(a[pre].ls, a[now].ls, l, mid, pos);
    else insert(a[pre].rs, a[now].rs, mid + 1, r, pos);
}
void  query(ll v, ll u, ll l, ll r, ll k)
{
    if(ans != -1) return ;
    ll num = a[u].num - a[v].num;
    if(num < k) return ;
    if(l == r)
    {
        if(num >= k) ans = l;
        return ;
    }
    ll mid = (l + r) >> 1ll;
    query(a[v].ls, a[u].ls, l, mid, k);
    query(a[v].rs, a[u].rs, mid + 1, r, k);

}
int main()
{
    n = read(), qq = read();
    rep(i, 1, n) val[i] = read(), insert(rt[i - 1], rt[i], 1, 300000, val[i]);
    while(qq--)
    {
        ll L, R, T;
        L = read(), R = read(), T = read();
        ll temp = (R - L + 1) / T;
        ans = -1;
        query(rt[L - 1], rt[R], 1, 300000, temp + 1);
        out(ans);
        puts("");
    }
    return  0 ;
}
View Code

 

上一篇:排序算法在matlab中的可视化(一)


下一篇:JS中如何得到触发事件的属性?