【vijos】P1448 校门外的树

【题意】两种操作，[L,R]种新的树（不覆盖原来的），或查询[L,R]树的种类数。n<=50000。

【算法】树状数组||线段树

【题解】这题可以用主席树实现……不过因为不覆盖原来的，所以有更简单的方法。

括号法，对于每个K=1的操作标记左右括号的位置。

对于每个K=2的操作，答案就是right前面的左括号数量-(left-1)前面的右括号数量、

用树状数组或线段树优化。

注意数组在传递给函数时是传递地址，即在函数中修改即相当于修改原数组。

线段树：

#include<cstdio>

const int maxn=;

struct treess{int l,r,sum[];}t[maxn*];

int n,m,a,b,c;

void build(int k,int l,int r)

{

    t[k].l=l;t[k].r=r;

    if(l!=r)

     {

        int mid=(l+r)>>;

        build(k<<,l,mid);

        build(k<<|,mid+,r);

     }

}

void insert(int k,int x,int kind)

{

    int left=t[k].l,right=t[k].r;

    if(left==right)t[k].sum[kind]++;

     else

      {

          int mid=(left+right)>>;

          if(x<=mid)insert(k<<,x,kind);

           else insert(k<<|,x,kind);

          t[k].sum[kind]=t[k<<].sum[kind]+t[k<<|].sum[kind];

      }

}

int ask(int k,int l,int r,int kind)

{

    int left=t[k].l,right=t[k].r;

    if(l<=left&&right<=r)return t[k].sum[kind];

    int mid=(left+right)>>,ans=;

    if(l<=mid)ans=ask(k<<,l,r,kind);

    if(r>mid)ans+=ask(k<<|,l,r,kind);

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    build(,,n);

    for(int i=;i<=m;i++)

     {

         scanf("%d%d%d",&a,&b,&c);

         if(a==)

          {

              insert(,b,);

              insert(,c,);

         }

        else printf("%d\n",ask(,,c,)-ask(,,b-,));

     }

    return ;

}

树状数组：

#include<cstdio>

#define lowbit(x) x&-x

const int maxn=;

int left[maxn],right[maxn],n,m,a,b,c;

void add(int a[],int x)

{for(int i=x;i<=n;i+=lowbit(i))a[i]++;}

int search(int a[],int x)

{

    int ans=;

    for(int i=x;i>;i-=lowbit(i))ans+=a[i];

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

     {

         scanf("%d%d%d",&a,&b,&c);

         if(a==)

          {

              add(left,b);

              add(right,c);

         }

        else printf("%d\n",search(left,c)-search(right,b-));

     }

    return ;

}

巴特西

【vijos】P1448 校门外的树

最新文章

热门文章