【BZOJ-2223】PATULJCI 可持久化线段树

时间：2023-12-14 19:30:50

2223: [Coci 2009]PATULJCI

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit:
728  Solved: 292
[Submit][Status][Discuss]

Description

【BZOJ-2223】PATULJCI 可持久化线段树

Input

Output

10 3 1 2 1 2 1 2 3 2 3 3 8 1 2 1 3 1 4 1 5 2 5 2 6 6 9 7 10

Sample Input

no
yes 1
no
yes
1
no
yes 2
no
yes 3

Sample Output

HINT

Notice:输入第二个整数是序列中权值的范围Lim，即1<=ai(1<=i<=n)<=Lim。

1<=Lim<=10000

Source

Solution

题面应该是出问题了

方法很简单，主席树的建法，不过询问的是次数，裸题

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-')f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

int n,m,lim;

#define maxn 500001

int sum[maxn*],ll[maxn*],rr[maxn*],root[maxn<<],sz;

void insert(int l,int r,int &now,int fat,int val)

{

    now=++sz; sum[now]=sum[fat]+;

    if (l==r) return;

    ll[now]=ll[fat],rr[now]=rr[fat];

    int mid=(l+r)>>;

    if (val<=mid) insert(l,mid,ll[now],ll[fat],val);

    else insert(mid+,r,rr[now],rr[fat],val);

}

int query(int l,int r,int L,int R)

{

    int LL=root[L-],RR=root[R];

    while (l!=r)

        {

            int mid=(l+r)>>;

            if (sum[RR]-sum[LL]<=(R-L+)/) return ;

            if (sum[ll[RR]]-sum[ll[LL]]>(R-L+)/)

                LL= ll[LL],RR=ll[RR],r=mid;

            else if (sum[rr[RR]]-sum[rr[LL]]>(R-L+)/)

                    LL=rr[LL],RR=rr[RR],l=mid+;

                  else return ;

        }

    return l;

}

int main()

{

    n=read();lim=read();

    for (int a,i=; i<=n; i++)

        a=read(),insert(,lim,root[i],root[i-],a);

    m=read();

    for (int l,r,i=; i<=m; i++)

        {

            l=read(),r=read(); if (l>r) swap(l,r);

            int ans=query(,lim,l,r);

            if (!ans) puts("no");

            else printf("yes %d\n",ans);

        }

    return ;

}

心态爆炸了，做做水题

相关文章