Mango DS Training #48 ---线段树2 解题手记

时间：2022-10-09 07:54:05

Training address： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38966#overview

A.Count Color --- POJ 2777

这题初看不好下手，再想想，T<=30，这时想到颜色可以用二进制来表示，然后父节点颜色种类为子节点的按位或得出的结果中化为二进制时1的个数，然后就是无脑线段树了。。

代码：

#include <iostream>

#include <cstdio>

#include <utility>

#include <cstdlib>

using namespace std;

#define N 100010

struct node

{

    int mark;

    int sum;

}tree[*N];

void pushup(int rt)

{

    tree[rt].sum = tree[*rt].sum | tree[*rt+].sum;

}

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

{

    tree[rt].sum = ;

    tree[rt].mark = ;

    if(l == r)

        return;

    int mid = (l+r)/;

    build(l,mid,*rt);

    build(mid+,r,*rt+);

    pushup(rt);

}

void pushdown(int l,int r,int rt)

{

    if(!tree[rt].mark)

        return;

    if(tree[rt].mark)

    {

        tree[*rt].sum = tree[*rt+].sum = tree[rt].sum;

        tree[*rt].mark = tree[*rt+].mark = tree[rt].mark;

        tree[rt].mark = ;

    }

}

void make(int l,int r,int aa,int bb,int co,int rt)

{

    if(aa<=l && bb>=r)

    {

        tree[rt].mark = ;

        tree[rt].sum = <<(co-);

        return;

    }

    pushdown(l,r,rt);

    int mid = (l+r)/;

    if(aa<=mid)

        make(l,mid,aa,bb,co,*rt);

    if(bb>mid)

        make(mid+,r,aa,bb,co,*rt+);

    pushup(rt);

}

int query(int l,int r,int aa,int bb,int rt)

{

    if(aa>r||bb<l)

        return ;

    if(aa<=l&&bb>=r)

    {

        return tree[rt].sum;

    }

    pushdown(l,r,rt);

    int mid = (l+r)/;

    return query(l,mid,aa,bb,*rt)|query(mid+,r,aa,bb,*rt+);

}

int main()

{

    int n,t,o;

    int i;

    int aa,bb,co;

    char ss[];

    scanf("%d%d%d",&n,&t,&o);

    build(,n,);

    int cnt;

    for(i=;i<o;i++)

    {

        scanf("%s",ss);

        if(ss[] == 'C')

        {

            scanf("%d%d%d",&aa,&bb,&co);

            make(,n,aa,bb,co,);

        }

        else if(ss[] == 'P')

        {

            scanf("%d%d",&aa,&bb);

            int res;

            if(aa<=bb)

                res = query(,n,aa,bb,);

            else

                res = query(,n,bb,aa,);

            cnt = ;

            while(res)

            {

                if(res&)

                    cnt++;

                res>>=;

            }

            printf("%d\n",cnt);

        }

    }

    return ;

}

B.Who Gets the Most Candies --- POJ 2886

(题解借鉴： ahfywff）

本题利用反素数的概念。反素数的定义：对于任何正整数x，其约数的个数记做f(x)。例如f(1)=1,f(6)=4。如果某个正整数x满足：对于任意i(0<i<x)，都有f(i)<f(x)，则称x为反素数。对于本题，设pos为不大于N的反素数，则第pos个出圈的孩子得到的糖果最多，为pos的约数个数。

　　 出圈过程有点类似约瑟夫环。假设当前出圈的是剩余孩子中的第K个，他手中的数字为A。

若A大于零，下一个出圈的就应该是剩余孩子中的第(K-1+A-1)%n+1个；

若A小于零，下一个出圈的就应该是剩余孩子中的第((K-1+A)%n+n)%n+1个。

问题的关键是如何求得出圈孩子的原始位置，线段树的每个节点的sum存储了所在区间还有多少孩子留下，查询节点rt中第num个孩子的原始位置时，如果num<=st[2*rt].sum，则在左孩子节点中查询第num个孩子的原始位置；否则在右孩子节点中查询第num-st[2*rt].sum个孩子的原始位置。

代码：

/*12152 KB    1079 ms*/

#include <iostream>

#include <cstdio>

using namespace std;

#define N 500010

int anti[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,

           ,,,,,,,,};

int factor[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

int tree[*N];

char name[N][];

int num[N];

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

{

    tree[rt] = r-l+;

    if(l == r)

        return;

    int mid = (l+r)/;

    build(l,mid,*rt);

    build(mid+,r,*rt+);

}

int query(int l,int r,int pos,int rt)

{

    tree[rt]--;

    if(l == r)

        return l;

    int mid = (l+r)/;

    if(pos<=tree[*rt])

        return query(l,mid,pos,*rt);

    else

        return query(mid+,r,pos-tree[*rt],*rt+);

}

int main()

{

    int n,k,pos,Maxcandy,i;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        i=;

        int CN = n;

        while(anti[i]<=n)

            i++;

        pos = anti[i-];

        Maxcandy = factor[i-];

        build(,n,);

        for(i=;i<=n;i++)

        {

            scanf("%s %d",name[i],&num[i]);

        }

        int flag;

        for(i=;i<=pos;i++)

        {

            n--;

            flag = query(,CN,k,);

            if(n==)

                break;

            if(num[flag]>)

                k = (k + num[flag] - )%n + ;

            else

                k = ((k + num[flag] - )%n+n)%n + ;

        }

        printf("%s %d\n",name[flag],Maxcandy);

    }

}

G.Fast Matrix Operations ---UVA 11992

这题其实也不太难搞，关键是各方面要维护到，我写了两个多小时啊，最后还是有些地方没有照顾到，哎，太弱咯。。感觉自己在维护值方面还差一点火候。 这题看行数不超过20，想到在每一行都建一颗线段树，然后就搞吧。。代码有点长，将就着看吧。

(A.M : Attention to Maintain)

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <utility>

#include <cstdlib>

#define Mod 1000000007

using namespace std;

#define N 1000010

struct node

{

    int mini,maxi,sum;

    int addmark,setmark;

}tree[][*N];

int i;

void pushup(int i,int rt)

{

    tree[i][rt].sum = tree[i][*rt].sum + tree[i][*rt+].sum;

    tree[i][rt].mini = min(tree[i][*rt].mini,tree[i][*rt+].mini);

    tree[i][rt].maxi = max(tree[i][*rt].maxi,tree[i][*rt+].maxi);

}

void build(int i,int l,int r,int rt)

{

    tree[i][rt].sum = tree[i][rt].mini = tree[i][rt].maxi = ;

    tree[i][rt].setmark = -;

    tree[i][rt].addmark = ;

    if(l == r)

        return;

    int mid = (l+r)/;

    build(i,l,mid,*rt);

    build(i,mid+,r,*rt+);

    pushup(i,rt);

}

void pushdown(int i,int l,int r,int rt)

{

    if(tree[i][rt].setmark == - && tree[i][rt].addmark == )

        return;

    int mid = (l+r)/;

    if(tree[i][rt].setmark >= )

    {

        tree[i][*rt].sum = tree[i][rt].setmark*(mid-l+);

        tree[i][*rt+].sum = tree[i][rt].setmark*(r-mid);

        tree[i][*rt].mini = tree[i][*rt+].mini = tree[i][rt].setmark;  //A.M

        tree[i][*rt].maxi = tree[i][*rt+].maxi = tree[i][rt].setmark;  //A.M

        tree[i][*rt].addmark = tree[i][*rt+].addmark = ;  // 这个要写

        tree[i][*rt].setmark = tree[i][*rt+].setmark = tree[i][rt].setmark;

        tree[i][rt].setmark = -;

    }

    if(tree[i][rt].addmark > )

    {

        tree[i][*rt].sum += tree[i][rt].addmark*(mid-l+);

        tree[i][*rt+].sum += tree[i][rt].addmark*(r-mid);

        tree[i][*rt].maxi += tree[i][rt].addmark;  //A.M

        tree[i][*rt].mini += tree[i][rt].addmark;  //A.M

        tree[i][*rt+].maxi += tree[i][rt].addmark;  //A.M

        tree[i][*rt+].mini += tree[i][rt].addmark;  //A.M

        tree[i][*rt].addmark += tree[i][rt].addmark;

        tree[i][*rt+].addmark += tree[i][rt].addmark;

        tree[i][rt].addmark = ;

    }

}

void add(int l,int r,int aa,int bb,int val,int rt)

{

    if(aa>r||bb<l)

        return;

    if(aa<=l&&bb>=r)

    {

        tree[i][rt].addmark += val;

                                   //tree[i][rt].setmark = -1;  --不要写这个

        tree[i][rt].sum += (r-l+)*val;

        tree[i][rt].maxi += val;

        tree[i][rt].mini += val;

        return;

    }

    pushdown(i,l,r,rt);

    int mid = (l+r)/;

    if(aa<=mid)

        add(l,mid,aa,bb,val,*rt);

    if(bb>mid)

        add(mid+,r,aa,bb,val,*rt+);

    pushup(i,rt);

}

void setval(int l,int r,int aa,int bb,int val,int rt)

{

    if(aa>r||bb<l)

        return;

    if(aa<=l&&bb>=r)

    {

        tree[i][rt].setmark = val;

        tree[i][rt].addmark = ;

        tree[i][rt].sum = val*(r-l+);

        tree[i][rt].maxi = tree[i][rt].mini = val;

        return;

    }

    pushdown(i,l,r,rt);

    int mid = (l+r)/;

    if(aa<=mid)

        setval(l,mid,aa,bb,val,*rt);

    if(bb>mid)

        setval(mid+,r,aa,bb,val,*rt+);

    pushup(i,rt);

}

struct node_ans

{

    int sum;

    int mini,maxi;

};

node_ans query(int l,int r,int aa,int bb,int rt)

{

    node_ans res,ka1,ka2;

    if(aa<=l && bb>=r)

    {

        res.sum = tree[i][rt].sum;

        res.maxi = tree[i][rt].maxi;

        res.mini = tree[i][rt].mini;

        return res;

    }

    pushdown(i,l,r,rt);

    int mid = (l+r)/;

    if(bb<=mid)

        return query(l,mid,aa,bb,*rt);

    else if(aa>mid)

        return query(mid+,r,aa,bb,*rt+);

    else

    {

        ka1 = query(l,mid,aa,bb,*rt);

        ka2 = query(mid+,r,aa,bb,*rt+);

        res.sum = ka1.sum + ka2.sum;

        res.maxi = max(ka1.maxi,ka2.maxi);

        res.mini = min(ka1.mini,ka2.mini);

        return res;

    }

}

int main()

{

    int r,c,m;

    int k,zuo;

    int x1,y1,x2,y2,val;

    int sum,mmax,mmin;

    while(scanf("%d%d%d",&r,&c,&m)!=EOF)

    {

        for(i=;i<=r;i++)

        {

            build(i,,c,);

        }

        for(k=;k<m;k++)

        {

            scanf("%d",&zuo);

            if(zuo == )

            {

                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);

                for(i=x1;i<=x2;i++)

                {

                    add(,c,y1,y2,val,);

                }

            }

            else if(zuo == )

            {

                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);

                for(i=x1;i<=x2;i++)

                {

                    setval(,c,y1,y2,val,);

                }

            }

            else

            {

                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

                node_ans la;

                sum = ;

                mmax = -Mod;

                mmin = Mod;

                for(i=x1;i<=x2;i++)

                {

                    la = query(,c,y1,y2,);

                    sum += la.sum;

                    mmax = max(mmax,la.maxi);

                    mmin = min(mmin,la.mini);

                }

                printf("%d %d %d\n",sum,mmin,mmax);

            }

        }

    }

}

相关文章